2

これが私たちが解決しようとしている問題です。多数のアイテムの膨大なストリーミングデータを扱っています。事前定義されたアイテムのリストもあります。ストリーム内の各アイテムが、非常に巨大な（約400万アイテム）事前定義されたリストに属しているかどうかを確認する必要があります。ルックアップ/チェックアップ操作は可能な限り効率的である必要があります

ここの人々が私がこの問題に正しい方法で取り組むために読むことができる論文/アルゴリズムへのポインタを与えるのを手伝ってくれるなら素晴らしいでしょう。

ありがとう、

4

1 に答える 1

0

解決策にたどり着く前に、いくつかの仮定を絞り込むことをお勧めします

  • 定義済みのリストはメイン メモリに収まりますか?
  • アクセスパターンはどのようになりますか? ストリーミングされたアイテムのほとんどは同じタイプですか、それともすべてのタイプが同じように表現されますか?
  • あなたのアイテムは小さいですか (整数/短い文字列)? そうでない場合、それぞれに一意の識別子が付けられていますか?
  • 事前定義されたリストは静的ですか、それとも変更されますか? どのくらいの頻度ですか？

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

さらに読むために、ウィキペディアのデータ構造とBig-O記法の記事を紹介します。

編集： Pythonでハッシュルックアップのパフォーマンスを測定するために、この簡単なプログラムをハックしました：

#!/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)

結果：

3.660000s (238.100000 - 241.760000)

Python では、4 秒未満で 1000 万のユーザー名をチェックできます。これは、17MB/秒を超えるストリーミングに相当します。本当に必要な速度はどれくらいですか？:)

于 2012-04-26T07:29:50.230 に答える