1

私はプロキシサーバーを書いています。リストで一致する Web サイトに異なるルールを適用します。たとえば、リスト A をブロックし、別のプロキシを使用してリスト 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;
}

つまり、2 つのリスト ファイルを繰り返し、1 行ずつ読み取り、strcasestrとfnmatchを使用して 1 つの URL を照合します。

それは正常に動作します。しかし、リストがどんどん大きくなり、リストごとに 10,000 行、リストが 5 つになると、それは O(N) アルゴリズムであるため、効率的な解決策にはならないと思います。

各マッチラインにヒットカウンターを追加することを考えています。マッチ ラインを並べ替えると、平均検索長が短くなる場合があります。このような：

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

それについて他のアイデアはありますか？

4

1 に答える 1

0

パフォーマンスを向上させる方法は 2 つあります。

1

最初の方法は、何らかの方法で URL リストを並べ替えることです。これにより、検索を最適化できます。 クイックソートは最速のアルゴリズムです。

バブルソートは実装が簡単です。

次に、バイナリ検索を使用してリストを検索できます。ループが線形であるのに対し、二分探索は対数パフォーマンスを備えているため、大きなリストでは大幅に高速になります。

2

URL のリストが静的である場合は、flexという特別なツールを使用できます。このツールを使用すると、文字列を読み取るだけで解析できます。

これは、URL リストの一部が更新されたときに、解析用の新しいコードを作成するか、コード ジェネレーターを作成する必要があることも意味します。

これは、解析する URL の長さを N とすると、N ステップしか必要ないため、あらゆる種類の並べ替えよりもはるかに効果的な解析方法です。したがって、可能な限り、リストの長さは関係ありません。入力用の正しいスキャナを書きます。

于 2013-02-12T09:27:18.733 に答える