tìm kiếm thuật toán đối sánh tuple

Question

Tôi cần triển khai tính năng đối sánh bộ nhớ trong chuỗi trong C. Sẽ có danh sách lớn các bộ dữ liệu được kết hợp với các hành động khác nhau và số lượng sự kiện lớn được đối sánh với danh sách .

Danh sách các bộ:

("one", "four") 
("one") 
("three") 
("four", "five") 
("six")  

sự kiện ("một", "hai", "ba", "tứ đại gia") phải phù hợp với mục danh sách ("một", "tứ đại gia") và ("một ") và (" ba ") nhưng không phải (" bốn "," năm ") và không (" sáu ")

phương pháp hiện tại của tôi sử dụng bản đồ của tất cả các giá trị trường tuple làm khóa cho danh sách của mỗi bộ sử dụng giá trị. có rất nhiều băm thừa và chèn danh sách.

có cách nào hay cổ điển để thực hiện việc này?

Answer 1

Nếu bạn chỉ có một số lượng nhỏ giá trị tuple có thể, bạn nên viết một số hàm băm có thể biến chúng thành chỉ mục nguyên để tìm kiếm nhanh.

Nếu có < 32 giá trị mà bạn có thể làm điều gì đó với bitmasks:

unsigned int hash(char *value){...} 

typedef struct _tuple { 
    unsigned int bitvalues; 
    void * data 
} tuple; 

tuple a,b,c,d; 
a.bitvalues = hash("one"); 
a.bitvalues |= hash("four"); 
//a.data = something; 

unsigned int event = 0; 
//foreach value in event; 
event |= hash(string_val); 

// foreach tuple 
if(x->bitvalues & test == test) 
{ 
    //matches 
} 

Nếu có quá nhiều giá trị để làm một giải pháp bitmask bạn có thể có hàng loạt các danh sách liên kết. Đi qua từng mục trong sự kiện. Nếu mục phù hợp key_one, đi bộ qua các bộ dữ liệu với phím đó đầu tiên và kiểm tra sự kiện cho chìa khóa thứ hai:

typedef struct _tuple { 
    unsigned int key_one; 
    unsigned int key_two; 
    _tuple *next; 
    void * data; 
} tuple; 

tuple a,b,c,d; 
a.key_one = hash("one"); 
a.key_two = hash("four"); 

tuple * list = malloc(/*big enough for all hash indexes*/ 
memset(/*clear list*/); 

//foreach touple item 
if(list[item->key_one]) 
    put item on the end of the list; 
else 
    list[item->key_one] = item; 


//foreach event 
    //foreach key 
     if(item_ptr = list[key]) 
     while(item_ptr.next) 
      if(!item_ptr.key_two || /*item has key_two*/) 
       //match 
      item_ptr = item_ptr.next; 

Mã này là không có cách nào kiểm tra và có lẽ có nhiều lỗi nhỏ nhưng bạn nên có được ý tưởng. (Một lỗi đã được sửa chữa là điều kiện thử nghiệm cho trận đấu tuple)

---

Nếu tốc độ xử lý sự kiện là vô cùng quan trọng nó sẽ làm cho tinh thần để lặp qua tất cả các bộ xây dựng của bạn, đếm số lần xuất hiện và đi qua có thể sắp xếp lại khóa/khóa chính của mỗi tuple để giá trị duy nhất được liệt kê đầu tiên.

Answer 2

Tôi không biết về bất kỳ cách cổ điển hoặc phải để làm điều này, vì vậy đây là những gì tôi sẽ làm gì: P

Dường như bạn muốn quyết định nếu A là một superset của B, sử dụng lý thuyết tập hợp biệt ngữ. Một cách bạn có thể làm là sắp xếp A và B, và thực hiện thao tác sắp xếp hợp nhất trên A và B, trong đó bạn cố gắng tìm vị trí trong A giá trị trong B. Những phần tử B đó cũng có trong A, sẽ có bản sao và các phần tử khác sẽ không. Bởi vì cả hai A và B được sắp xếp, điều này không nên quá khủng khiếp. Ví dụ, bạn lấy giá trị đầu tiên của B, và đi bộ A cho đến khi bạn tìm thấy nó trùng lặp trong A. Sau đó, bạn lấy giá trị thứ hai của B, và bắt đầu đi bộ A từ nơi bạn rời đi trước đó. Nếu bạn nhận được kết thúc của A mà không tìm thấy một trận đấu, thì A không phải là một siêu của B, và bạn trở về sai.

Nếu các bộ dữ liệu này có thể được sắp xếp, thì chi phí sắp xếp chỉ phát sinh một lần.

Answer 3

Nếu bạn có số lượng nhỏ các chuỗi có thể, bạn có thể gán chỉ mục cho từng chuỗi và sử dụng bitmap. Bằng cách đó một cách đơn giản bitwise và sẽ cho bạn biết nếu có chồng lên nhau.

Nếu điều đó không thực tế, thiết lập chỉ mục đảo ngược của bạn có thể sẽ khó khớp với tốc độ, đặc biệt nếu bạn chỉ phải xây dựng nó một lần.(danh sách các bộ dữ liệu thay đổi theo thời gian chạy?)

Answer 4

public static void Main() 
    { 
     List<List<string>> tuples = new List<List<string>>(); 

     string [] tuple = {"one", "four"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string [] {"one"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string [] {"three"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string[]{"four", "five"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string[]{"six"}; 
     tuples.Add(new List<string>(tuple)); 

     tuple = new string[] {"one", "two", "three", "four"}; 

     List<string> checkTuple = new List<string>(tuple); 

     List<List<string>> result = new List<List<string>>(); 

     foreach (List<string> ls in tuples) 
     { 
      bool ok = true; 
      foreach(string s in ls) 
       if(!checkTuple.Contains(s)) 
       { 
        ok = false; 
        break; 
       } 
      if (ok) 
       result.Add(ls); 
     } 
    } 

Answer 5

Một giải pháp có thể là gán một số nguyên tố duy nhất cho mỗi từ.

Sau đó, nếu bạn nhân các từ với nhau trong mỗi bộ, thì bạn có một số đại diện cho các từ trong danh sách.

Chia danh sách này sang danh sách khác và nếu bạn nhận được số dư còn lại, thì danh sách này được chứa trong danh sách còn lại.