6

RDF データの大きなブロックをフィルタリングするアルゴリズムを Python で構築しようとしています。

のようにフォーマットされた約 70,000 のアイテムからなる 1 つのリストがあり<"datum">ます。

次に、次のようにフォーマットされた約6GB相当のアイテム（トリプル）があります<"A"> <"B"> <"C">

最初のリストのアイテムを含むすべてのトリプルを抽出し、最初の抽出から個々のアイテムを含むトリプルを抽出します (最終的な効果は、1 つのステップでシードに接続されたグラフのパーティションを形成することです)。最初のリストから）。

このための優れたアルゴリズムを思いつくことができませんでした (正式な CS トレーニングを受けていないという事実は助けにはなりませんでした)。

これまでに思いついた最善の方法は、大きなリストのトリプルを 3 つの項目リストのリストに分割することから始めること[<"A">, <"B">, <"C">]です。次に、それをチャンクに分割し、マルチプロセッシングを使用して、完全な小さなリストと大きなリストのチャンクを取得するプロセスを作成し、...

for line in big list:
    for item in small list:
      if item in line:
       bucket.append(line)

このアルゴリズムにはかなり時間がかかります。

これを行うより速い方法はありますか？特定のアルゴリズムがある場合は、その名前を教えていただければ、その実装方法を見つけます。

ありがとう！

コメントごとの説明:

  1. すべてのデータ項目は文字列です。したがって、小さなリストには含まれる可能性が["Mickey", "Mouse", "Minny", "Cat"]あり、大きなリストには含まれる可能性があります[["Mickey","Pluto","Bluto"],["John", "Jane", "Jim]...]

  2. 小さなリストをカウントするには、大きなリスト トリプルごとに 1 つのアイテムだけがアイテムと一致する必要があります。

  3. 小さなリストのアイテムはすべて実際にはユニークなので、とにかくそれらをセットに変換することは考えていませんでした. しかし、私はそれを試してみます。

  4. 必要な中間構造を作成できます。現在、シェルブを使用して構築された逆インデックスを試しています。

4

1 に答える 1

5

おそらく最初に小さなリストをセットに格納して、ルックアップが高速になるようにする必要があります。これにより、big_list 内のすべての項目について 70,000 回の反復を回避できます。

small_list_set = set(small_list)
for line in big_list:
    for item in line:
        if item in small_list_set:
            bucket.append(line)
于 2012-05-03T02:37:11.857 に答える