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

C でstl を使用することはできません。それ以外の場合は、m=イベント数、n=すべてのフィルターの最大長である全体的な複雑さmapを実現する最も簡単な方法です。m*log(n)次に達成する最も簡単な方法は、 Trie treem*log(n)を使用することです。すぐに使用できるトライ ツリーの実装が見つかります。その実装の可能な使用法は次のようになります (コンパイルは試していません)。

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 に答える