0

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

#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;
            }
        }
    }
}
4

2 回答 2

2

您不能map在 C 中使用 stl，否则这将是实现m*log(n)整体复杂性的最简单方法，其中 m = 事件数和 n = 所有过滤器的最大长度。现在实现的下一个最简单的方法m*log(n)是使用Trie 树。您将在此处找到一个现成的 trie 树实现。该实现的可能用法可能如下所示（我没有尝试编译它）：

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);
于 2013-04-01T06:13:43.467 回答
1

“最好的”没有很好的定义。如果您有大量项目，您将看到通过使用标准 C 的qsort和bsearch显着提高性能，而对您的代码进行必要的更改或更改最少。这很整洁，但我不知道它是否符合您对best的定义。有关排除此代码的“最佳”的定义，请参阅此答案评论：

#include <stddef.h>
#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;
    Size_t item_count = 0;

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

    /* just preparing data so far */    
    strcpy(events[item_count++], "first_event");
    strcpy(events[item_count++], "second_event");
    strcpy(events[item_count++], "third_event");
    strcpy(events[item_count++], "foo");

    qsort(events, item_count, sizeof *events, strcmp);

    for (j = 0; j < 2; j++) {
        char *pass = bsearch(filter[j], events, item_count, sizeof *events, strcmp);
        If (pass != NULL) {
            printf("pass -> %s\n", pass);
            continue;
        }
    }
}
于 2013-04-01T06:16:41.087 回答