23

10 ～ 100k の要素を含むリストで、何百万もの要素 (20 ～ 30 文字の文字列) の存在を確認する必要があります。Pythonでそれを行うより速い方法はありset()ますか?

import sys
#load ids
ids = set( x.strip() for x in open(idfile) )

for line in sys.stdin:
    id=line.strip()
    if id in ids:
        #print fastq
        print id
        #update ids
        ids.remove( id )
4

4 に答える 4

30

setそれが得るのと同じくらい速いです。

ただし、コードを書き直してset一度作成し、変更しない場合は、frozenset組み込み型を使用できます。不変以外はまったく同じです。

それでも速度の問題がある場合は、cPython の代わりにPyPyを使用するなど、他の方法でプログラムを高速化する必要があります。

于 2011-08-18T15:49:19.677 に答える
14

sys.stdin私のコメントで指摘したように、おそらく速度を落としているのは、「マスター」セットのメンバーシップから各行を順番にチェックしていることです。これは非常に遅くなり、セット操作の速度を利用することはできません。例として：

#!/usr/bin/env python

import random

# create two million-element sets of random numbers
a = set(random.sample(xrange(10000000),1000000))
b = set(random.sample(xrange(10000000),1000000))
# a intersection b
c = a & b
# a difference c
d = list(a - c) 
print "set d is all remaining elements in a not common to a intersection b"
print "length of d is %s" % len(d)

上記は、私の 5 年前のマシンで ~6 ウォールクロック秒で実行され、必要以上に大きなセットのメンバーシップをテストしています (誤解していない限り)。その時間のほとんどは実際にはセットの作成に費やされるため、そのようなオーバーヘッドはありません。参照する文字列が長いという事実は、ここでは関係ありません。agf が説明したように、セットを作成するとハッシュ テーブルが作成されます。メンバーシップテストを行う前にすべての入力データをセットに入れることができれば、一度に1つのアイテムで読み取るのとは対照的に、はるかに高速になると思います（ただし、質問からは明らかではありません）。時間、セットメンバーシップのチェック

于 2011-08-18T18:32:49.147 に答える
0

検索を高速化するには、データを分割するようにしてください。ツリー構造を使用すると、データが存在するかどうかを非常にすばやく見つけることができます。

たとえば、最初の文字とその文字で始まるすべてのキーをリンクする単純なマップから始めます。したがって、すべてのキーを検索する必要はなく、キーのごく一部だけを検索する必要があります。

これは次のようになります：

ids = {}
for id in open(idfile):
    ids.setdefault(id[0], set()).add(id)

for line in sys.stdin:
    id=line.strip()
    if id in ids.get(id[0], set()):
       #print fastq
       print id
       #update ids
       ids[id[0]].remove( id )

作成は少し遅くなりますが、検索ははるかに速くなるはずです（キーの最初の文字が十分に分散されていて、常に同じであるとは限らない場合、20倍速くなると思います）。

これは最初のステップです。2番目の文字でも同じことができます。以下同様に、検索は各文字でツリーを歩くだけです...

于 2011-08-18T17:17:56.823 に答える
-3

urschrei が述べたように、小切手を「ベクトル化」する必要があります。1 つの要素を 100 万回チェックするよりも、(C で行われるように) 100 万の要素の存在を 1 回チェックする方が高速です。

于 2013-04-03T12:13:53.000 に答える