スパースビットベクトル用のJavaでよく知られているライブラリはありますか？
（そして、スパースとjava.util.BitSetの使用にどのように役立つかについてのガイドラインはありますか？）
5760 次
7 に答える
9
TL;DRはここにありますJavaでの効率的なスパースビットセットの実装
これが「古い」質問であることは知っていますが、同じ質問があると、この投稿に出くわしました。答えは良いのですが、最終的には満足できませんでした。さらに掘り下げてみると、Javaのスパースビットセットの質問に対する「決定的な」答えに出くわしたと思います。
このプレゼンテーションでは、著者であるBruce Haddon博士が、標準のJavaビットセットの非常にメモリ効率が高く高性能な代替品を作成するための彼の研究者の取り組みについて説明します。
彼のプレゼンテーションへの元のリンクは無効ですが、私はハドン博士に連絡し、コードとプレゼンテーションの両方をここに保存しました。
https://github.com/brettwooldridge/SparseBitSet
このプレゼンテーションをこれ以上読むことはお勧めできません。あなたがまばらなビットセットに興味がなくても、それは魅力的な読み物です、それは問題解決の本当の性質についてです...
于 2011-12-01T02:36:22.627 に答える
5
本当にまばらな場合（たとえば、読み込みが1％未満の場合）、ビットインデックスでインデックス付けされたハッシュテーブルを使用するのはおそらくかなり良いでしょう。テーブル内のインデックスの単なる存在または不在は、ビットがそれぞれ1であるか0であるかを知る必要があるすべてです。
密度が数パーセント以上の場合は、ビットインデックスを64で割った値でインデックス付けされたハッシュテーブルを使用し、実際のビットを含むハッシュテーブルに長い単語を格納できます。ハッシュテーブルにint（N / 64）の値Vが含まれ、（V >>（N mod 64））＆1がtrueの場合、ビットNが設定されます。
これらの答えは両方とも、ビットへのランダムアクセスを最適化することを前提としています。インデックスごとにビットへのシーケンシャル（または他のアクセス）を最適化する場合は、予想される密度に応じて同じ種類の低レベルビットベクトル表現を使用して、スパース行列構造が必要になる場合があります。スパース行列を参照してください
于 2010-06-14T21:10:45.710 に答える
3
coltライブラリには、スパース行列（1D、2D、および3D）があります。また、8ビットのように値ごとに1ビットではなく、効率的なBitVectorを備えてboolean[]います。
ただし、スパース行列はビットを直接サポートしていません。doubleとオブジェクトのみをサポートしています。(bitIndex>>6)各longは64ビットを保持するため、ビットインデックスをlongインデックスにマップし、取得したdoubleをraw long値に変換し、ビット操作を使用して取得したlongのビットにアクセスすることにより、1Dスパース二重行列をラップできます。少し作業が必要ですが、スパースベクトルを自分で実装するほどではありません。ラッパーが機能したら、doubleをlongに変換することを避け、double1Dスパース行列に使用可能なColtソースコードを開始点として使用して、実際のスパース長い1d行列を実装できます。
編集：詳細。すべてのビット（long）が最初は0であると仮定すると、Coltベクトル/行列は最初にストレージにメモリを必要としません。値をゼロ以外に設定するとメモリが消費されます。値を0に戻すと、メモリを消費し続けますが、ゼロ値のメモリは定期的に再利用されます。
ビットが本当にまばらで、各バッキングロング値に1ビットしか設定されていない場合、ストレージオーバーヘッドは非常に低くなり、実際に格納されるビットごとに64ビットが必要になります。ただし、一般的なケースは20〜40％のスパースであるため、オーバーヘッドははるかに低くなり、ビットが0〜100、次に1000〜1100、2000〜2200の範囲でクラスター化されている場合、ストレージが無駄になることはありません（全体として、領域の1/16のみがビットに割り当てられますが、クラスタリングとは、ビットが無駄なスペースなしで格納されることを意味します。
于 2010-06-14T21:04:22.250 に答える
1
FastUtilのAVLツリーマップを試すことができます。
于 2010-06-14T21:13:10.523 に答える
0
CERN COLTは、ベクトルと行列の計算に広く使用されており、スパース行列がありますが、ビットベクトルには特に使用されません。
http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/SparseObjectMatrix1D.html
于 2010-06-14T20:59:41.090 に答える
0
キーの単なる存在または不在が何かを教えてくれるハッシュテーブル？それはハッシュセットになります！私は、ビットセットに対するセット（ハッシュされたものでさえ）のパフォーマンスに懐疑的です。それは本当に速度またはメモリが主要な推進力であるかどうかに依存します。
于 2010-06-14T21:21:58.733 に答える
0
JavaEWAHライブラリを試すことができます。
https://code.google.com/p/javaewah/
問題によっては、適切な場合があります。
（Apache Hiveなどで使用されています。）
于 2013-09-16T14:41:36.837 に答える