Pythonの大規模配列の比較

Question

URLを含む大きな配列（100,000のURL文字列を含むことができます）があり、実際のURLが配列のURLの1つであるかどうかを知りたいと思います。そのためには、配列内のすべてのURL文字列と実際のURL文字列を比較する必要があります。この大きな配列と比較する方法はありますか？今の時間よりも時間はかかりますか？今のところそれはです：

error = 0 
for oldUrl in urlList: 
    error = 1 if oldUrl == actualUrl else error 

Answer 1

としては、あなたがin演算子を使用することができますlistsまたはsetsのいずれかでメンバーシップを確認してください。たとえば、

found = x in some_list 
if found: 
    #do stuff 
else: 
    #other stuff 

ただし、スピードが問題であると述べました。 TL; DR-setsは、setがすでに存在する場合は高速です。 https://wiki.python.org/moin/TimeComplexityからin演算子を使用してメンバーシップをチェックすると、listの場合はO（n）、setの場合はO（1）（@enderlandのように指摘されます）です。

100,000アイテム、または1回のみのチェックでは、使用する違いはほとんどありませんが、多くのチェックを行うアイテムや状況が多い場合は、おそらくsetを使用します。私は通訳からテストのカップルを行なったし、これは私が（Pythonの2.7、i3のWindowsの10 64ビット）見つけたものです：100万のエントリの場合

import timeit 
#Case 1: Timing includes building the list/set 
def build_and_check_a_list(n): 
    a_list = [ '/'.join(('http:stackoverflow.com',str(i))) for i in xrange(1,n+1) ] 
    check = '/'.join(('http:stackoverflow.com',str(n))) 
    found = check in a_list 
    return (a_list, found) 

def build_and_check_a_set(n): 
    a_set = set([ '/'.join(('http:stackoverflow.com',str(i))) for i in xrange(1,n+1) ]) 
    check = '/'.join(('http:stackoverflow.com',str(n))) 
    found = check in a_set 
    return (a_set, found) 

timeit.timeit('a_list, found = build_and_check_a_list(100000)', 'from __main__ import build_and_check_a_list', number=50) 
3.211972302022332 

timeit.timeit('a_set, found = build_and_check_a_set(100000)', 'from __main__ import build_and_check_a_set', number=50) 
4.5497120006930345 

#Case 2: The list/set already exists (timing excludes list/set creation) 
check = '/'.join(('http:stackoverflow.com',str(100000))) 

timeit.timeit('found = check in a_list', 'from __main__ import a_list, check', number=50) 
0.12173540635194513 

timeit.timeit('found = check in a_set', 'from __main__ import a_set, check', number=50) 
1.01052391983103e-05 

、構築および/または自分のコンピュータ上でメンバーシップを確認するには：

#Case 1: list/set creation included 
timeit.timeit('a_list, found = build_and_check_a_list(1000000)', 'from __main__ import build_and_check_a_list', number=50) 
35.71641090788398 

timeit.timeit('a_set, found = build_and_check_a_set(1000000)', 'from __main__ import build_and_check_a_set', number=50) 
51.41244436103625 

#Case 2: list/set already exists 
check = '/'.join(('http:stackoverflow.com',str(1000000))) 

timeit.timeit('found = check in a_list', 'from __main__ import a_list, check', number=50) 
1.3113457772124093 

timeit.timeit('found = check in a_set', 'from __main__ import a_set, check', number=50) 
8.180430086213164e-06 

Answer 2

listがitemが含まれている場合は、使用を確認するには：item in listを。

だから、あなたが書くことができます。

error = oldUrl in urlList 

Answer 3

を、このためにリストを使用しないでください。リストのルックアップは、O（n）の最悪の複雑さを有する。

代わりに、他のメタデータがある場合はセット（または辞書）を使用してください。これは大まかにO（1）のルックアップを持っています。セット、辞書、およびリストの比較については、hereを参照してください。セットを使用して

、検索が簡単です：

urls = set(['url1', 'url2', 'url3']) 

print ('url2' in urls) 
print ('foobar' in urls) 

それともあなたのケースでは、あなたのリストオブジェクトがセットとして変換します。

urlListSet = set(urlList) 
print(oldUrl in urlListSet) 

あなたはまた、あなたのセットに新しいURLを追加することができます。すでに@Laurentで述べたと@sisanared

urlListSet.add(newurl) 
urlListSet.update(listOfNewUrls)