1

我正在写一个代理服务器。它对列表中匹配的网站应用不同的规则。例如，我们可以阻止 List A 并使用另一个代理来获取 List B 的内容。

例如，列表 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;
}

即迭代两个列表文件，逐行读取，使用strcasestr和fnmatch匹配单个URL。

它工作正常。但是如果列表变得越来越大，比如每个列表有 10,000 行和 5 个列表，我想这不是一个有效的解决方案，因为它是一个 O(N) 算法。

我正在考虑为每条比赛线添加一个命中计数器。通过对匹配行进行排序，它可以减少平均搜索长度。像这样：

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

有没有其他想法？

4

1 回答 1

0

有两种方法可以提高性能。

1

第一种方法是以某种方式对 URL 列表进行排序，因此您可以在其中优化搜索。 快速排序是目前最快的算法。

冒泡排序更容易实现。

然后您可以使用二进制搜索在列表中进行搜索。二进制搜索具有对数性能，而您的循环具有线性性能，因此在大型列表上它会明显更快。

2

如果您的 URL 列表是静态的，您可以使用名为flex的特殊工具，它使您能够通过读取字符串来解析它。

这也意味着，当您的某些 URL 列表更新时，您必须编写新代码进行解析或创建代码生成器。

这是一种更有效的解析方式，然后是任何一种排序，因为它只需要 N 步，当 N 是你正在解析的 URL 的长度时，所以你的列表有多长并不重要，只要你能为输入编写正确的扫描仪。

于 2013-02-12T09:27:18.733 回答