2

500M の 2 桁の Unicode 文字をメモリ (RAM) に格納する必要があります。

私が使用するデータ構造は次のとおりです。

Worst Case Space Complexity: O(n)
Worst Case Time Complexity: O(1) <-- insertion, read, update, deletion

Python でのハッシュの実装である dict を選択することを考えていましたが、問題は、最悪の場合よりも平均的な場合にのみ、必要な操作に対して O(1) の時間の複雑さを保証することです。

エントリ数がわかれば、最悪のシナリオでも O(1) の時間計算量を達成できると聞きました。

どうやってするか？

場合によっては、それは Python では不可能です。Python コードで直接メモリ アドレスとデータにアクセスできますか? はいの場合、どのように？

4

3 に答える 3

4

ほとんどの場合、パフォーマンスヒット（通常は衝突時に発生）は、すべての呼び出しで償却されます。したがって、最も現実的な使用法では、O(n)すべての呼び出しに対応することはできません。実際、すべての呼び出しでヒットが発生する唯一のケースはO(n)、すべてのキーのハッシュが既存のキーのハッシュ値と衝突する病理学的ケースです（つまり、ハッシュテーブルの可能な限り最悪の（または最も不幸な）使用法）。

たとえば、キーのセットを事前に知っていて、それらにハッシュ衝突がないことがわかっている場合（つまり、すべてのハッシュが一意である場合）、衝突のケースに悩まされることはありません。他の主要なO(n)操作はハッシュテーブルのサイズ変更ですが、これの頻度は実装（拡張係数/ハッシュ関数/衝突解決スキームなど）に依存し、入力セットに応じて実行ごとに異なります。

いずれの場合も、すべてのキーをdictに事前入力できれば、実行時の突然の速度低下を回避できます。値はNoneに設定するだけで、後で実際の値を入力できます。これにより、最初にキーでdictを「プライミング」するときに、唯一の顕著なパフォーマンスヒットが発生するはずであり、将来の値の挿入は一定の時間である必要があります。

まったく別の質問は、構造をどのように読み取ったり照会したりするつもりなのかということです。個別の値を添付し、キーを介してそれらにアクセスする必要がありますか？注文する必要がありますか？マッピングは実際には必要ないため、おそらくasetよりも適切な場合があります。dictkey:value

アップデート：

コメントの説明に基づくと、一時的なセットを使用している場合でも、これはデータベースが実行する作業のように聞こえ始めています。インメモリリレーショナルデータベースを使用できます（SQLiteなど）。さらに、SQLAlchemyのようなORMを使用して、SQLを記述せずに、よりPython的にデータベースと対話できます。

そもそもデータベースからデータを読み取っているように聞こえますが、それをさらに活用できるのではないでしょうか。

一意にキー設定された大量の型付きレコードの保存/クエリ/更新は、まさにRDBMSが何十年にもわたる開発と研究に特化してきたことです。既存のリレーショナルデータベース（SQLiteなど）のインメモリバージョンを使用することは、おそらくより実用的で持続可能な選択になるでしょう。

Pythonの組み込みsqlite3モジュールを使用してみて":memory:"、構築時にdbファイルパスとして提供することにより、メモリ内バージョンを試してください。

con = sqlite3.connect(":memory:")
于 2013-03-03T23:14:24.847 に答える
2

辞書には技術的にはO（n）の最悪のケースがありますが、発生する可能性は非常に低く、あなたのケースでは発生しない可能性があります。私は辞書を使おうとしますが、それがあなたのやりたいことに対して十分でない場合にのみ、別の実装に切り替えます。

これは主題に関する有用なスレッドです

于 2013-03-03T23:07:46.597 に答える
2

平均的なパフォーマンスではなく、最悪の場合のパフォーマンスを気にする理由はありますか？妥当なハッシュテーブルであれば、O（N）の平均パフォーマンスが得られます。

O（1）の最悪の場合のパフォーマンスが本当に必要な場合は、次の2つのアプローチが考えられます。

  1. エントリのベクトルをmax(charCode)-min(charCode)用意し、Unicode文字コードから必要な値を直接検索します。これは、キーがRAMに収まるほどコンパクトな範囲にある場合にうまく機能します。

  2. ブルートフォースアプローチを使用してハッシュ関数またはディクショナリサイズを選択し（これを制御できるディクショナリのカスタム実装を使用）、衝突のないものが得られるまで新しい関数やサイズを試し続けます。これには非常に長い時間がかかると予想してください。 これはお勧めしません。

編集：

表示される最小の文字コードが1234であり、表示される最大の文字コードが98765であることがわかっているとします。さらに、98765-1234要素を保持するのに十分なRAMがあるとします。numpyまた、ライブラリまたはその他の効率的な配列実装を使用しても構わないと思っていることを前提としています。その場合、次のように値をベクトルに格納できます。

# configuration info
max_value = 98765 # replace with your number
min_value = 1234  # replace with your number
spread = (max_value - min_value)
dtype = object # replace with a primitive type if you want to store something simpler

# create the big vector
my_data = numpy.empty((spread,), dtype=dtype)

# insert elements
my_char_code              = ...
my_value_for_my_char_code = ...

assert min_value <= my_char_code < max_value
my_data[my_char_code - min_value] = my_value_for_my_char_code

# extract elements
my_char_code              = ...
assert min_value <= my_char_code < max_value
my_value_for_my_char_code = my_data[my_char_code - min_value]

ルックアップはポインタ演算を使用して実装され、配列に格納されている要素の数に依存しないため、これはO（1）です。

実際に格納したい要素の数が。よりもはるかに少ない場合、このアプローチはRAMを非常に浪費する可能性がありますspread。たとえば、spreadが40億（UTF32のすべて）の場合、my_data単独で少なくとも40億*8バイト/ポインタ=32 GBのRAMを消費します（おそらくそれ以上です。Python参照の大きさはわかりません）。一方、min_valueが30億でmax_value = min_value + 100ある場合、メモリ使用量はごくわずかになります。

于 2013-03-04T00:35:56.330 に答える