3

約 100 万個のキーと値のペアを格納するためのメモリ効率の良いデータ構造が必要です。ここで、キーは約 80 バイトの文字列で、値は約 200 バイトの文字列で、キーと値の合計サイズは約 280 MB です。また、キー、できればハッシュマップによる効率的な値の検索も必要です。メモリのオーバーヘッドはできるだけ少なくする必要があります。たとえば、280MB の有用なデータの場合、データ構造は 300MB を超える仮想メモリを使用しないでください (malloc()オーバーヘッドとその他すべて)。使用パターンは次のとおりです。空のデータ構造から始めて、キーを変更したり、値の長さを変更したりせずに、徐々に入力します。プラスとして、データ構造は値の長さの変更をサポートする場合がありますが、100% の値のオーバーヘッドが発生します (つまり、x 値バイトの場合、x バイトが未使用のバッファー領域で一時的に無駄になる可能性があります)。

純粋な Python モジュール、組み込みの Python モジュール、またはできれば (C)Python バインディングを使用した C 実装が必要です。データ構造全体をディスクにシリアライズして、非常に迅速に読み戻すことができればと思います。

このような小さなオーバーヘッドが可能であることを証明するために、オープン アドレス指定を使用した単純な設計を作成しました。125 万要素のハッシュ テーブルには、1MB のデータ ブロックへの 4 バイトのポインターが含まれており、データ ブロックにはキーと値の長さがベースとして含まれています。 -128 ヴァリント。この設計には重要な制限があります。メモリ領域を無駄にせずにペアを削除または変更することはできません。それぞれ 280 バイトの 100 万のキーと値のペアを使用した私の計算によると、オーバーヘッドは 3.6% (10 080 000 バイト) 未満です。上記の制限はより寛大で、20 000 000 バイトのオーバーヘッドが許容されます。

http://www.pytables.org/を見つけました。これは、データの高速アクセスとメモリ効率の高いパッキングを提供します。それが私のニーズに合っているかどうかを確認するために、もっと詳しく調べなければなりません。

4

10 に答える 10

7

わかりました、ダートシンプルなアプローチです。

データ構造には Python 辞書を使用します。キーが 80 文字、値が 200 文字の 100 万個のランダムなキーと値のペアを Python 辞書に入力しました。私のコンピューターでは 360,844 Kb かかりました。これは 300 MB を超えないという仕様の範囲外ですが、それでもかなりメモリ効率が良いので、とにかく解決策として提供します。

これも、C API を使用するという要件を満たしていません。なぜCが必要なのかわかりませんが、質問にはPythonのタグが付けられており、Cのタグがないため、純粋なPythonを提供して、それが法案に適合するかどうかを確認します.

持続性について。cPickle モジュールを使用します。それは非常に高速で、これも簡単です。辞書を保存するには:

cPickle.dump(mydict, "myfile.pkl")

辞書をリロードするには:

mydict = cPickle.load("myfile.pkl")

2 番目の簡単なアイデアは、shelve基本的にディスクベースの Python 辞書であるモジュールを使用することです。メモリのオーバーヘッドは非常に低いです (すべてディスク上にあります)。しかし、それはまたはるかに遅いです。

于 2010-10-26T18:39:08.530 に答える
6

大量の削除を計画していない場合、これはそれほど難しいことではありません。削除すると断片化につながります。

また、固定長のキーにコミットする必要があります。あなたは80バイトについて言及しました。キーの複製は許可されていますか？そうでなければ、それはさらに簡単です。

だから、これがあなたがすることです。

次の配列を作成します。

struct {
    char value[80];
    char *data;
} key;

そして、この配列をソートしたままにします。

キーを複製できる場合は、次のものが必要です。

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

（私のCはさびていますが、これがその要点です）後者には、リンクされた値のリストを指す各キーがあります。

次に、ルックアップは単純な二分探索です。「苦痛」は、この配列を維持し、キーを挿入/削除することです。思ったほど苦痛ではありませんが、特に64ビットシステムでは、多くのメモリを節約できます。

減らしたいのはポインタの数です。ポインタで満たされた構造がたくさんある場合、ポインタは高価です。64ビットシステムでは、ポインタは8バイトです。したがって、単一のポインタの場合、8MBのメモリバジェットが発生します。

したがって、費用は配列の構築、メモリのコピーと圧縮にあります（100万行があり、それにコミットできることが「わかっている」場合は、malloc（1000000 * sizeof（key））をすぐに使用できます。拡張中のコピー）。

しかし、恐れることはありません。一度起動して実行すると、パフォーマンスは非常に良好になります。現代のCPUは、実際には1億ブロックのメモリをコピーするのに非常に優れています。

余談ですが、私はJavaでこのようなことをしました。64ビットJVMでは、25Mエントリのマップは2GのRAMです。私のソリューション（これと同様の手法を使用）のソリューションは約600Mです）。JavaはCよりも多くのポインターを使用しますが、前提は同じです。

于 2010-10-26T18:03:27.000 に答える
6

Martijn はコメントでこれについて言及しましたが (人々が回答をコメントする理由がわからない)、私は同意します: SQLite を使用してください。試してみて、ニーズを満たすかどうかを確認してください。

于 2010-10-26T17:53:40.500 に答える
5

簡単な辞書を使ってみましたか? ほとんどのデータは文字列であるため、オーバーヘッドは要件内に収まる可能性があります。

于 2010-10-26T17:55:34.150 に答える
2

SQLiteを使用することをお勧めします。迅速な実装により、わずかな労力で十分に高速かどうかを判断できます。

自分でロールする必要があると判断した場合は、次のことをお勧めします。

ペアの数、またはその上限をどれだけうまく予測できますか？
合計データサイズ、またはその上限をどの程度予測できますか？

文字列とノードのアリーナアロケータ。（通常、アリーナのリストで作業するので、合計サイズを予測する必要はありません）。

アラインメントはアルゴリズムに依存します。原則として、バイトタイトにパックできます。唯一のオーバーヘッドはオーバーアロケーションであり、ワーキングセットへの影響はごくわずかです。

ただし、これらの文字列に対してcmp / copyなどの操作を実行する必要がある場合は、次の保証を使用して、これらの文字列操作から少しまたは多くを絞り出すことができることに注意してください。

  • すべての要素はCPUワードで整列されます
  • すべてのパッドバイトは（例）0です
  • CPUの境界を越えない限り、文字列の終わりを「超えて」安全に読み取ることができます

インデックスのハッシュテーブル。辞書も機能しますが、それは潜在的な劣化/再ハッシュが深刻な問題になる場合にのみ意味があります。Cの「ストック」ハッシュテーブルの実装はわかりませんが、あるはずですよね？右？割り当てをアリーナアロケーターへの呼び出しに置き換えるだけです。

メモリの局所性

ルックアップがマップにない文字列を要求しないことを保証できる場合は、キーがハッシュの衝突でのみ必要になるため、キーを別のアリーナに保存する必要があります。これにより、メモリの局所性を大幅に向上させることができます。（その場合、「ファイナル」テーブルがある場合は、衝突するキーを新しいアリーナにコピーして、他のすべてのキーを破棄することもできます。ただし、そのメリットはおそらくわずかです。）

分離は、アクセスパターンに応じて、助けになったり傷ついたりする可能性があります。通常、各ルックアップの後に値を1回使用する場合は、同じアリーナでペアごとに値を使用することをお勧めします。たとえば、いくつかのキーを検索し、それらの値を繰り返し使用する場合は、個別のアリーナが理にかなっています。

「面白い文字」/Unicodeをサポートする必要がある場合は、文字列を保存する前に正規化してください。

于 2010-10-26T20:10:47.997 に答える
2

sha1キー自体の代わりにキーの を使用できます。キーが一意である場合、キーのsha1ハッシュも可能性があります。制限を超えないようにメモリを節約できます。

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

私のubuntuボックスでは、これは304 MBのメモリで最高になります：

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

十分近い？CではなくPythonです。

後で: また、データが多少冗長な場合はgzip、値を取得できます。これは、時間とスペースのトレードオフです。

于 2010-10-26T18:28:40.713 に答える
1

構造体モジュールを使用して、バイナリ データをパックし、必要に応じてアンパックできます。このアプローチを使用して、メモリ効率の高いストレージを実装できます。アクセスがめんどくさいと思います。

于 2010-10-26T17:45:35.883 に答える
1

Judy はメモリ効率が高いはずです: http://judy.sourceforge.net/
(ベンチマーク: http://www.nothings.org/computer/judy/、「データ構造のサイズ」を参照)。
参照: http://www.dalkescientific.com/Python/PyJudy.html

また、

固定サイズのキーについては、C++ のhttp://panthema.net/2007/stx-btree/があります (カスタム C ラッパーを使用すると、CPython から使用できると確信しています)。データセットで許可されている場合は、可変長キーを値に格納し、可変長キーのハッシュまたはプレフィックスを固定長キーとして使用できます。

同じロジックがhttp://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and-time.htmlとhttp://code.google.com/p/sparsehashに適用されます/ - 重い std::string をキーとして使用する代わりに、32 ビットまたは 64 ビットの整数キーを使用して、何らかの形で実際の可変長キーから作成します。

于 2013-02-04T22:10:24.547 に答える
1

Apache Portable Runtime (別名 APR) には、c ベースのハッシュ テーブルがあります。ドキュメントはhttp://apr.apache.org/docs/apr/0.9/group_ apr _hash.htmlで参照できます。

apr_hash_t を使用すると、保存するのは void* だけです。したがって、値を完全に制御できます。SO 必要に応じて、文字列の実際の長さではなく、100 バイト ブロックへのポインターを格納できます。

于 2010-10-26T18:01:43.670 に答える
0

メモリを密に詰め込む既存のソリューションが見つからなかったので、自分でCで実装することにしました。質問のオープンアドレス法で私のデザインを参照してください。

于 2010-11-13T11:12:56.903 に答える