優れたグラフ走査アルゴリズム

Question

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

具体的な問題:Webサイトのユーザーページをスクレイピングしようとしています。新しいユーザーを発見するために、既知のユーザーから友達リストを取得しています。すでにグラフの約 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*

現在の実装の問題点:

• すでにインポートしたクリークにはまってしまい、時間が無駄になり、インポート中のスレッドがアイドル状態になります。
• 指摘され次第追加します。

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

Answer 1

あなたはすでに訪問したユーザーのIDを覚えているために、あなたは25万整数の長さのマップを必要とします。それは、「あまり」からは程遠いです。このようなエッジを見つけるの点でそのマップに追加するだけで、このようなマップを維持し、すでに未知のユーザーにつながる縁を横断

私の知る限り見ることができる、あなたは幅優先探索（BFS）を実装するのに近いです。このアルゴリズムの詳細についてはGoogleのを確認してください。そして、もちろん、ミューテックスを忘れないでください - 。あなたがそれらをする必要があります。

Answer 2

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

最近のシステム、およびメモリのそのどっさりで、私はいくつかの種類の素敵な簡単なキャッシュをお勧めします。あなたが繰り返し作業を避けるためにできるようになり、ユーザー情報の非常に迅速なキャッシュを作成することができるはずです。すでにノードに遭遇した場合は、処理を停止します。これは派閥に永遠に循環を回避します。

あなたはしばらく後に既存のノードを焼き直しを可能にする必要がある場合は、

、あなたはdBでグローバル値になりlast_visit_numberを使用することができます。ノードは、その番号を持っている場合、このクロールがそれに遭遇したものです。あなたは、自動的にすべてのノードを再訪したい場合は、あなただけのクロールを開始する前にlast_visit_numberをバンプする必要があります。

あなたの説明では、私はあなたが立ち往生しているか非常にわかりません。

編集------ 私はちょうどあなたが具体的な質問を持っていた気づきました。あなたが新しいデータでプルどのように迅速に増加させるためには、私は与えられたユーザーがデータ（インポートまたはまだインポートされません）ににリンクされた回数を追跡します。クロールするユーザーを選択するとき、私はリンクの数が少ないを持っているユーザーを選ぶだろう。私は、特にリンクの最低数やリンクの最低数とユーザーの間でランダムな選択のいずれかのために行くだろう。

ヤコブ

Answer 3

あなたが最初からグラフの構築を最適化するのに役立ちます特別なアルゴリズムはありません。一つの方法または別では、あなたは少なくとも一度、各ノードを訪問する必要があるとしています。あなたはこの深最初のか<のhref = "HTTPを行うかどうかは、：// EN。 wikipedia.org/wiki/Breadth-first_search」REL = 『nofollowをnoreferrer』>幅優先の速度の観点からは無関係です。 Theran を正しく最初に近いノードを探索することにより、その幅優先探索以下のコメントで指摘して、あなたにもっと便利を与える可能性グラフすぐに、グラフ全体が完了する前に、これは、またはあなたのための関心事であってもなくてもよいです。彼はまた、深さ優先探索のneatestバージョンは潜在的にあなたのための問題になる可能性が再帰を使用して実装されていることを指摘しています。しかし、再帰が必要とされていないことに注意してください。あなたがスタックに不完全探検ノードを追加し、必要に応じて直線的にそれらを処理することができます。

あなたは新しいノード（O（1）あなたは、ルックアップのためにハッシュを使用している場合）のためのシンプルな存在チェックを行う場合は、

、その後のサイクルは全く問題になることはありません。サイクルは、あなたが完全グラフを格納しない場合にのみ懸念されます。あなたは、グラフによる検索を最適化することができますが、建設段階自体は常に線形時間がかかります。

私はあなたのグラフのサイズが問題になることはありません他のポスターに同意します。 250,000非常に大きいではありません！

同時実行に関しては、グラフは、すべてのスレッドによって更新されるので、同期されたデータ構造にする必要があります。これは、Pythonであるので、あなたはまだ新しいリンクを保存するためにhref="http://docs.python.org/library/queue.html" rel="nofollow noreferrer">キューのモジュール

Answer 4

友人リストの取得には長い時間がかかる (10 秒以上) と言っていますが、古き良きダイクストラのアルゴリズムの変形が機能する可能性があります。

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

コツは、ステップ 2 でロードする接続を賢明な方法で選択することです。これについての短いコメントは次のとおりです。

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

効率について実際に何かを言うには、データ構造についてさらに詳しく説明してください。