Лучший способ сопоставления (поиска) URL-адреса в списке на C (реализация белого списка или черного списка)?

Question

Я пишу прокси-сервер. Он применяет различные правила к сайтам, которые соответствуют спискам. Например, мы можем блокировать List A и использовать другой прокси-сервер для извлечения содержимого в список Б.

Например, список А:

.google.com 
blogger.com 
sourceforge.net 
ytimg.com 
http://media-cache-*.pinterest.com/* 
images-amazon.com 
*.amazonaws.com 
twitter.com 
fbcdn.net 
google-analytics.com 
staticflickr.com 

Список Б:

ytimg.com 
youtube.com 

В настоящее время матч функция:

struct proxy_t * 
match_list(char *url) { 
    // 2KB line should be enough 
    char buf[2048]; 
    int pos = 0, size; 

    struct acllist *al = config->acl_h; 
    struct acl *node = al->data; 

    while (node != NULL) { // iterate list 
    pos = 0; // position in list file 

    size = strlen(node->data); // node->data holds a URL list 

    while (1) { // iterate each line in list 

     readline(buf, node->data, &pos, size); 

     if (buf[0] == 0) break; 

     if (strcasestr(url, buf) != NULL 
     || !fnmatch(buf, url, FNM_CASEFOLD)) { 

      return node->proxy; 
     } 
    } 
    node = node->next; 
    } 


    printf("Not Matched\n"); 

    return config->default_proxy; 
} 

То есть, перебирать два списка файлов, построчно читать, использовать strcasestr и fnmatch в соответствии с одним URL.

Он отлично работает. Но если списки становятся больше и больше, скажем, 10 000 строк в списке и 5 списках, я полагаю, что это не будет эффективным решением, так как это алгоритм O (N).

Я подумываю о добавлении счетчика попаданий в каждую строку матча. При заказе строк соответствия это может уменьшить среднюю длину поиска. Например:

.google.com|150 
blogger.com|76 
sourceforge.net|43 
ytimg.com|22 

Есть ли другие идеи?

Answer 1

Есть два способа улучшить производительность.

Первый способ заказать списки URL каким-то образом, и поэтому вы можете оптимизировать поиск в нем. Quicksort - самый быстрый алгоритм.

Bubble sort проще в применении.

Затем вы можете использовать binary search для поиска в списке. Двоичный поиск имеет логарифмическую производительность, в то время как ваш цикл имеет линейный, поэтому он будет значительно быстрее в больших списках.

Если ваши списки адресов являются статическими, вы можете использовать специальный инструмент под названием flex, который позволяет разобрать строку, просто прочитав его.

Это также означает, что когда некоторые из ваших списков URL обновлены, вам необходимо написать новый код для синтаксического анализа или создания генератора кода.

Это гораздо более эффективный способ синтаксического анализа, а затем любой вид сортировки, потому что ему нужны только N шагов, когда N - длина URL-адреса, которую вы обрабатываете, поэтому не имеет значения, как долго ваш список, так как если вы можете написать правильный сканер для ввода.