チェック

Question

これは、我々が解決しようとしている問題です。 私たちは、多数のアイテムの膨大なストリーミングデータを扱っています。あらかじめ定義されたアイテムのリストもあります。ストリームの各アイテムが、あらかじめ定義された非常に巨大なリスト（約400万アイテム）に属しているかどうかを確認する必要があります。ルックアップ/チェック操作は、ここの人々は、私は右の方法でこの問題にアプローチするために読むことができる論文/アルゴリズムへのポインタを与えることに私を助けることができればそれは素晴らしいことだ

できるだけ効率的にする必要があります。

おかげで、

Answer 1

あなたは、メインメモリ内のあなたの定義済みリストフィットするソリューションに

• を来る前に、いくつかの前提条件を絞り込むこともできますか？
• アクセスパターンはどのように見えますか？ストリーミングされたアイテムのほとんどは同じタイプであるか、すべてのタイプが同じように表現されますか？
• アイテム小さな（整数/短い文字列）はありますか？そうでない場合、それぞれに固有の識別子が付けられていますか？
• 事前定義リストは静的であるか、または変更されますか？どのくらいの頻度ですか？

一般に、オブジェクト（またはそれらのオブジェクトを表す一意のキー）のハッシュテーブルを維持し、ストリームを介して入ってくる各オブジェクトをルックアップすることが必要です。ハッシュテーブルは速い検索を提供し、あなたのデータセットが静的である場合、彼らはあなたが記述ユースケースに最適です。しかし、他のソリューションがより良いパフォーマンスを発揮できる状況がいくつかありますが、上記の質問は、これが当てはまるかどうかを明らかにする必要があります。

私はウィキペディアにData StructuresとBig-O表記の記事の方にあなたを指しますさらに読書のために

編集：

#!/usr/bin/python 

import random 
import string 
import time 

# return a random username, all lowercase, between n and m characters long 
def generate_username(min_length = 5, max_length = 10): 
    n = random.randint(min_length, max_length) 
    return ''.join(random.sample(string.ascii_lowercase, n)) 

# Build a hash table of 4mil usernames (the 'predefined items') 
users = set() 
for i in xrange(4000000): 
    users.add(generate_username()) 

# Build a 'stream' of usernames to check against the hash table 
stream = [] 
for i in xrange(10000000): 
    stream.append(generate_username()) 

# Measure performance of hash lookups for 10mil usernames 
start = time.clock() 
for name in stream: 
    if name in users: 
     pass #print "%s is present" % name 
end = time.clock() 

print "%fs (%f - %f)" % (end - start, start, end) 

結果：は、私が一緒にPythonでハッシュ検索のパフォーマンスを測定するために、この迅速なプログラムをハッキング：

3.660000s (238.100000 - 241.760000) 

だから、Pythonでは10mストリーミング> 17MB /秒に相当する4秒以内にユーザーの名前を入力します。どのくらい速くそれが本当に必要ですか？ :)ご返信用