寻找元组匹配算法

Question

我需要在C中实现内存中的字符串元组匹配功能.将有大量的元组列表与不同的操作相关联,并且要与列表匹配大量事件.

元组列表:

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

事件("一","二","三","四")应匹配列表项("一","四")和("一")和("三")但不匹配("四", "五"而不是("六")

我当前的方法使用所有元组字段值的映射作为使用该值的每个元组的列表的键.有很多冗余哈希和列表插入.

有没有正确或经典的方法来做到这一点？

Answer 1

如果您只有少量可能的元组值，那么编写某种哈希函数是有意义的，该函数可以将它们转换为整数索引以进行快速搜索。

如果值 < 32 个，您可以使用位掩码执行某些操作：

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
}

如果值太多而无法进行位掩码解决方案，则可以使用链表数组。浏览事件中的每个项目。如果该项与 key_one 匹配，则使用第一个键遍历元组并检查第二个键的事件：

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;

这段代码没有经过任何测试，可能有很多小错误，但您应该明白。（已纠正的一个错误是元组匹配的测试条件）

如果事件处理速度至关重要，那么迭代所有构造的元组、计算出现次数并可能重新排序每个元组的键一/键二是有意义的，以便首先列出最唯一的值。