2013-02-12 41 views
1

我在寫代理服務器。它將不同的規則應用於列表中匹配的網站。例如,我們可以阻止列表A和使用其他代理獲取的名單B.匹配(搜索)C列表中的URL(實施白名單或黑名單)的最佳方法?

例如內容,列表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 

B組:

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

也就是說,迭代兩個列表文件,逐行讀取,使用strcasestrfnmatch匹配一個URL。

它工作正常。但是,如果列表變得越來越大,比如說每個列表和5個列表有10000行,那麼我認爲它不是一個有效的解決方案,因爲它是一個O(N)算法。

我正在考慮爲每條比賽線添加一個計數器。通過排序匹配線可以減少平均搜索長度。像這樣:

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

有沒有其他的想法呢?

+0

這不是關於解析URL。這是關於如何有效地匹配URL列表。 – strongwillow 2013-02-12 09:08:46

+1

您可能想要查看哈希表來存儲URL或某種搜索樹。 – 2013-02-12 09:16:39

+0

謝謝大家。我終於整理出來了。無論使用散列表還是搜索樹,都可以使用它的域(xxx.xx)。一旦我們找到節點(也是鏈表的頭部),迭代列表並將其與** fnmatch **和** strstr **進行匹配。 – strongwillow 2013-02-13 06:58:34

回答

0

有兩種方法可以提高性能。

第一種方式是爲了以某種方式URL列表,因此,你可以優化它搜索。 Quicksort是那裏最快的算法。

Bubble sort更容易實現。

然後,您可以使用binary search在列表中進行搜索。 二進制搜索具有對數性能,而您的循環具有線性,因此在大型列表中它將顯着更快。

如果你的URL列表是靜態的,你可以使用一個叫做flex專用工具,它使您通過閱讀它來解析字符串。

這也意味着,當你的一些URL列表被更新時,你必須編寫新的代碼來解析或創建代碼生成器。

這是更有效的解析方式,然後是任何類型的排序,因爲它只需要N個步驟,當N是您要解析的URL的長度時,因此無論您的列表多長時間,只要你可以寫入正確的掃描儀輸入。