11

抽象的問題：約250,000ノードのグラフがあり、平均接続数は約10です。ノードの接続を見つけるのは長いプロセスです（たとえば、10秒）。ノードをデータベースに保存するのにも約10秒かかります。ノードがデータベースにすでに存在するかどうかを非常にすばやく確認できます。同時実行を許可しますが、一度に10を超える長いリクエストがない場合、グラフをトラバースして、最高のカバレッジを最も速く取得するにはどうすればよいでしょうか。

具体的な問題：ウェブサイトのユーザーページをスクレイプしようとしています。新しいユーザーを見つけるために、私は既知のユーザーから友達リストを取得しています。グラフの約10％を既にインポートしましたが、サイクルでスタックしたり、ノードが多すぎてメモリを使いすぎたりします。

私の現在の実装：

def run() :
    import_pool = ThreadPool(10)
    user_pool = ThreadPool(1)
    do_user("arcaneCoder", import_pool, user_pool)

def do_user(user, import_pool, user_pool) :
    id = user
    alias = models.Alias.get(id)

    # if its been updates in the last 7 days
    if alias and alias.modified + datetime.timedelta(days=7) > datetime.datetime.now() :
        sys.stderr.write("Skipping: %s\n" % user)
    else :
        sys.stderr.write("Importing: %s\n" % user)
        while import_pool.num_jobs() > 20 :
            print "Too many queued jobs, sleeping"
            time.sleep(15)

        import_pool.add_job(alias_view.import_id, [id], lambda rv : sys.stderr.write("Done Importing %s\n" % user))

    sys.stderr.write("Crawling: %s\n" % user)
    users = crawl(id, 5)
    if len(users) >= 2 :
        for user in random.sample(users, 2) :
            if (user_pool.num_jobs() < 100) :
                user_pool.add_job(do_user, [user, import_pool, user_pool])

def crawl(id, limit=50) :
    '''returns the first 'limit' friends of a user'''
    *not relevant*

現在の実装の問題：

  • すでにインポートしたクリークでスタックするため、時間が無駄になり、インポートするスレッドがアイドル状態になります。
  • 彼らが指摘されるにつれて、さらに追加されます。

したがって、完全な書き直しだけでなく、わずかな改善も歓迎します。ありがとう！

4

4 に答える 4

7

すでに訪問したユーザーの ID を記憶するには、250,000 整数の長さのマップが必要です。それは「やりすぎ」には程遠い。そのようなマップを維持し、まだ発見されていないユーザーにつながるエッジのみを通過し、そのようなエッジを見つけた時点でそのユーザーをそのマップに追加します。

私が見る限り、幅優先探索 (BFS) の実装に近づいています。このアルゴリズムの詳細については、Google を確認してください。もちろん、mutex も忘れないでください。必要になります。

于 2009-08-24T06:15:54.690 に答える
2

ノードをDBに追加するのに10秒かかる理由について、私は本当に混乱しています。それは問題のように聞こえます。どのデータベースを使用していますか? プラットフォームに厳しい制限がありますか?

最新のシステムと大量のメモリを使用する場合は、何らかの単純なキャッシュを使用することをお勧めします。ユーザー情報の非常に迅速なキャッシュを作成できるため、作業の繰り返しを避けることができます。すでにノードに遭遇したら、処理を停止します。これにより、クリークで永久に循環することが回避されます。

しばらくしてから既存のノードを再ハッシュできるようにする必要がある場合は、dB のグローバル値である last_visit_number を使用できます。ノードにその番号がある場合、このクロールはそれに遭遇したものです。ノードを自動的に再訪問したい場合は、クロールを開始する前に last_visit_number を増やす必要があります。

あなたの説明では、どのように動けなくなっているのかよくわかりません。

編集-----具体的な質問があることに気づきました。新しいデータを取り込む速度を上げるために、データ内で特定のユーザーがリンクされた回数 (インポート済みまたは未インポート) を追跡します。クロールするユーザーを選ぶときは、リンクの数が少ないユーザーを選びます。具体的には、リンクの数が最も少ないか、リンクの数が最も少ないユーザーの中からランダムに選択します。

ジェイコブ

于 2009-08-24T06:15:06.737 に答える
2

グラフの構築を最初から最適化するのに役立つ特定のアルゴリズムはありません。いずれにせよ、少なくとも 1 回は各ノードにアクセスする必要があります。この深さを優先するか幅を優先するかは、速度の観点からは無関係です。テラングラフ全体が完了する前に、より近いノードを最初に探索することにより、幅優先検索がすぐに、より有用なグラフを提供する可能性があることを下のコメントで正しく指摘しています。これはあなたにとって関心があるかもしれませんし、そうでないかもしれません。彼はまた、深さ優先検索の最も適切なバージョンは再帰を使用して実装されていることにも言及していますが、これは潜在的に問題になる可能性があります。ただし、再帰は必須ではないことに注意してください。不完全に探索されたノードをスタックに追加し、必要に応じて線形に処理できます。

新しいノードの単純な存在チェックを行う場合 (ルックアップにハッシュを使用する場合は O(1))、サイクルはまったく問題になりません。サイクルは、完全なグラフを保存しない場合にのみ問題になります。グラフを介して検索を最適化できますが、構築ステップ自体には常に線形時間がかかります。

グラフのサイズが問題にならないという他のポスターに同意します。250,000 はあまり大きくありません。

同時実行について; グラフはすべてのスレッドによって更新されるため、同期されたデータ構造である必要があります。これは Python であるため、Queueモジュールを使用して、スレッドによって処理される新しいリンクを保存できます。

于 2009-08-24T06:30:09.933 に答える
0

友達リストを取得するのにかなりの時間がかかる (10 秒以上) とおっしゃっていますが、古き良き Dijkstra のアルゴリズムの変形が機能する可能性があります。

  1. 任意のノードを取得します。
  2. ロード済みの任意のノードから接続を取得します。
  3. もう一方の端がまだロードされていない場合は、ノードをグラフに追加します。
  4. 手順 2 に進みます。

秘訣は、ステップ 2 でロードした接続をスマートな方法で選択することです。これについてのいくつかの短いコメント:

  • 同じ接続が 2 回以上ロードされるのを何らかの方法で防止する必要があります。ランダムな接続を選択し、既にロードされている場合は破棄することは、すべての接続を調べている場合、非常に非効率的です。
  • 最終的にすべての接続をロードする場合は、ノードのすべての接続を同時にロードします。

効率について実際に何かを言うために、データ構造に関する詳細を提供してください。

于 2009-08-24T07:04:43.283 に答える