4

問題：約250000個の整数ユーザーIDのセットと、約1テラバイトのJSON形式の1行に1つのレコードがある場合、ユーザーIDがデータベースと一致するレコードをロードします。

すべてのレコードの約1％のみが250000のユーザーIDと一致します。長い時間がかかる各レコードをJSONでデコードするのではなく、文字列照合を使用して、ユーザーIDが生のJSONに含まれているかどうかを判断しようとしています。一致する場合は、JSONがデコードされ、レコードがチェックされてから挿入されます。

問題は、生のJSONの1つの文字列を約25万の文字列エントリを含むセットと照合するのが遅いことです。

これまでのコードは次のとおりです。

// get the list of integer user IDs
cur.execute('select distinct user_id from users')

// load them as text into a set
users = set([])
for result in cur.fetchall():
    users.add(str(result[0]))

// start working on f, the one-json-record-per-line text file
for line in f:
    scanned += 1
    if any(user in line for user in users):
        print "got one!"
        // decode json
        // check for correct decoded user ID match
        // do insert

私はこれに正しい方法でアプローチしていますか？これらの文字列を照合するためのより高速な方法は何ですか？現在、非常に多くのユーザーIDを探す場合、これは3GHzマシンで1秒間に最大2つのエントリを管理します（あまり良くありません）。ユーザーIDのリストが非常に短い場合、1秒あたり最大200000エントリを管理します。

4

3 に答える 3

3

エイホ-コラシックはこの目的のために建てられたようです。そのための便利なPythonモジュールもあります（easy_install ahocorasick）。

import ahocorasick

# build a match structure
print 'init empty tree'
tree = ahocorasick.KeywordTree()

cur.execute('select distinct user_id from users')

print 'add usernames to tree'
for result in cur.fetchall():
   tree.add(str(result[0]))

print 'build fsa'
tree.make()

for line in f:
     scanned += 1
     if tree.search(line) != None:
         print "got one!"

これは、1秒あたり約450エントリに達します。

于 2012-11-19T17:03:05.137 に答える
0

Try inverting the matching algorithm:

for digit_sequence in re.findall('[0-9]+', line):
    if digit_sequence in users:
        ...
于 2012-11-19T16:58:28.200 に答える
0

私はC++のフリーランサーであり、クライアントは通常、Python / java / .net / etcのコードが遅いスタートアップであり、より高速に実行することを望んでいます。私は通常それを100倍速くすることができます。つい最近、私は質問タスクに似ていました。テラバイトのテキストデータで500万のサブストリングの検索を実装することです。

私はいくつかのアルゴリズムをテストしました。Aho–Corasickには、オープンソースのhttp://sourceforge.net/projects/multifast/を使用しました。最速のアルゴリズムではありませんでした。最速は、ハッシュテーブルと、ラビン-カープ検索アルゴリズムから得られたいくつかのアイデアを組み合わせて作成したアルゴリズムでした。この単純なアルゴリズムは、ACのx5倍高速で、x5倍少ないメモリを使用しました。サブストリングの平均長は32バイトでした。したがって、ACはこのための最速のアルゴリズムではない可能性があります。

于 2014-02-19T14:14:31.477 に答える