c - 在 C 中实现(包含)过滤器的最佳方式

Question

场景如下:我有一大堆需要解析的事件，只让我需要的那些通过。实现这一目标的最佳方法是什么？到目前为止，我的代码如下所示:

#include <stdio.h>
#include <string.h>

int main (int argc, char **argv) {

    int i, j;
    char events[4][15]; /* for the sake of the test only*/
    char *ptr;

    /* probably loaded from a config file */
    const char *filter[] = {"first_event", "third_event"};

    /* just preparing data so far */    
    strcpy(events[0], "first_event");
    strcpy(events[1], "second_event");
    strcpy(events[2], "third_event");
    strcpy(events[3], "foo");

    /* my approach is to have two iterations */
    for (j = 0; j < 2; j++) {
        for (i = 0; i < 3; i++) {
            if (strcmp(filter[j], events[i]) == 0) {
                printf("pass -> %s\n", events[i]);
                continue;
            }
        }
    }
}

Answer 1

您不能在 C 中使用 STL map，否则这将是实现 m*log(n) 整体复杂度的最简单方法，其中 m=事件数和n=所有过滤器的最大长度。现在实现 m*log(n) 的下一个最简单的方法是使用 Trie tree .您会发现一个随时可用的 trie 树实现 Here . 该实现的可能用法可能如下所示(我没有尝试编译它):

Trie *ttree = trie_new();

for(i=0; i<numberOfFilter; i++) {
    trie_insert(ttree, filter[i], (void *) 1); //insert your filters in the tree
}

for (i=0; i<numberOfEvents; i++) {
    if (trie_lookup(ttree, events[i]) != TRIE_NULL ) { //check whether i'th event matches with any of the filters
        printf("pass -> %s\n", events[i]);
    }
}

trie_free(ttree);