5

私は約 5 億の 128 ビット整数を持っており、年間約 1 億を追加しています。何も削除されません。数値は、スケールごとおよび時間ごとに均一に分布しています。

基本的に、必要なのは追加操作だけで、数値が DB に既に存在するかどうかも返します。また、このシステムに RAM を使いすぎたくないので、すべてをメモリに格納するだけでは探していません。

これまで、2 つの bigint を主キーとして使用して、MySQL で複数の MyISAM テーブルを使用してきました。これで十分なパフォーマンスが得られますが、この作業には適切なツールではないと思います。テーブルを分割する前にいくつかのパフォーマンスの問題が発生し、停電時に破損が発生しました。また、DB は必要のない多くの機能を提供してくれます。

Linux で Python を使用していますが、提案は受け付けています。

C++ での同様の質問。

更新: Marcelo のコメントはBloom Filterに言及しており、これは私にとって本当に有望なようです。私はハッシュを扱っているので、完全な正確さをあきらめているので、これは精度とパフォーマンスの大きなトレードオフになる可能性があります。

4

2 に答える 2

3

整数のnビット ハッシュを計算することによって選択された2 n SQLite データベース (おそらく 2 8が適切な数)のプールの 1 つに各整数を挿入します。既存の数値を挿入しようとすると失敗するように、1 つのテーブルの 1 つの列を主キーにします。

整数がすでに十分にランダムであると仮定すると、おそらく最下位バイトを「ハッシュ」として選択できます。

編集：いくつかのテストを行いました。約 2 時間で 2,500 万のエントリを挿入しましたが、その過程で 1 GB 以上を使い果たしました。これは、乱数を生成し、それらを 32 のサブプロセスに分散することによって行われます。各サブプロセスは、その制御下にある 1 つの SQLite データベースを持ち、100,000 回の挿入ごとに 1 回コミットします。挿入は現在、問題が要求する 3 Hz をはるかに超える約 1350 Hz で動作していますが、データベース全体はまだキャッシュに収まります (私は 8 GB RAM を持っています)。現在のデータベース サイズに近づけない限り、定常状態のパフォーマンスはわかりません。その時点で、挿入ごとに少なくとも 4 回のディスク ヘッドの動き (インデックスとテーブルの読み取りと書き込み、おそらく B+ ツリーにドリルダウンするためにさらに多くの動き) が発生します。 .

これは非常に興味深い問題であり、独自のソリューションを使用すればはるかに効率的に解決できるのではないかと考え始めています。ただし、データベース エンジンを大幅に上回るには相当な労力が必要になると思います。

于 2010-11-18T09:54:41.097 に答える
0

あなたのハッシュをハッシュしますか？

于 2010-11-18T13:20:01.940 に答える