Java：スパースビットベクトル
https://stackoverflow.com/questions/3040864
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Javaには、まばらなビットベクトル用の有名なライブラリがありますか？
（そして、それらを使用するのにどのようにスパースが役立つかについてのガイドラインはありますか。 java.util.bitset?)
解決
コルト図書館 スパースマトリックス（1D、2D、3D）があります。また、8ビットではなく、値ごとに1ビットを持つ効率的なBitVectorもあります。 boolean[] します。
ただし、スパースマトリックスはビットを直接サポートしていません - ダブルとオブジェクトのみ。ビットインデックスを長いインデックスにマッピングすることにより、1Dスパースダブルマトリックスをラップできます (bitIndex>>6) それぞれが64ビットを保持しているので、 変換 検索は生の長い値に二重になり、ビット操作を使用して、検索された長さのビットにアクセスします。ちょっとした作業ですが、まばらなベクトルを自分で実装するほどどこにもありません。ラッパーが機能したら、ダブルスのロングへの変換を避け、ダブル1Dスパースマトリックスの使用可能なCOLTソースコードを使用して開始点として使用して、実際のスパースロング1Dマトリックスを実装することができます。
編集：詳細。コルトベクトル/マトリックスは、すべてのビット（ロング）が最初に0であると仮定して、最初に保管にメモリを必要としません。値を0に戻すとメモリを消費し続けますが、ゼロ値のメモリは定期的に回収されます。
ビットが本当にまばらであるため、各バッキングロング値に1つのビットセットしかないようにすると、ストレージオーバーヘッドは非常に貧弱で、実際のビットあたり64ビットが必要です。しかし、典型的なケースが20〜40％スパースであることに言及すると、オーバーヘッドははるかに低くなり、ビットが範囲でクラスター化されている場合、無駄なストレージはありません。 HEXの値。）全体として、地域の1/16のみがビットに割り当てられますが、クラスタリングはビットに無駄なスペースなしで保存されることを意味します。
他のヒント
tl; drはここに行きます Javaでの効率的なスパースビットセット実装
私はこれが「古い」質問であることを知っていますが、同じ質問をしてこの投稿に出くわしました。答えは良いですが、私は最終的には満足していませんでした。さらに掘り出した後、私はJavaのまばらなビットセットの問題に対する「決定的な」答えに出くわしたと思います。
の このプレゼンテーション 著者のブルース・ハドン博士は、標準のJava Bitsetのメモリ効率が高く高性能な代替品を作成するための研究者の努力について議論しています。
彼のプレゼンテーションへの元のリンクは死んでいますが、私はハドン博士に連絡し、ここにコードとプレゼンテーションの両方を保持しています。
https://github.com/brettwooldridge/sparsebitset
このプレゼンテーションをより高く読むことはお勧めできません。まばらなビットセットに興味がない場合でも、魅力的な読み物です。問題解決の本質についてです...
本当にまばらな場合（たとえば、1％未満の負荷）、ビットインデックスでインデックス付けされたハッシュテーブルを使用するのはおそらくかなり良いです。テーブル内のインデックスの単なる存在または不在は、ビットがそれぞれ1つまたはゼロであるかどうかを知るために必要なすべてです。
密度が数パーセント以上の場合は、ビットインデックスで64で割ったハッシュテーブルを使用して保存できます。 長さ 実際のビットを含むハッシュテーブルの単語。少し n ハッシュテーブルに値が含まれている場合、設定されます v にとって int（n/64） と （v >>（n mod 64））＆1 本当です。
これらの回答はどちらも、ビットへのランダムアクセスを最適化することを想定しています。シーケンシャル（またはその他のアクセス）をインデックスごとに最適化する場合は、予想される密度に応じて同じ種類の低レベルビットベクトル表現を使用して、スパースマトリックス構造が必要になる場合があります。見る スパースマトリックス
試してみることができます FastutilのAVLツリーマップ.
Cern Coltは、ベクターおよびマトリックス計算に広く使用されており、まばらなマトリックスを備えていますが、ビットベクトルには特別には使用されていません。
http://acs.lbl.gov/software/colt/api/cern/colt/matrix/impl/sparseobjectmatrix1d.html
鍵の単なる存在または不在があなたに何かを伝えるハッシュテーブル？それはハッシュセットになります！私は、ビットセット上のセット（ハッシュされたものでさえ）のパフォーマンスに懐疑的です。速度とメモリが主要なドライバーであるかどうかに本当に依存します。
Javaewah Libraryを試すことができます。
https://code.google.com/p/javaewah/
あなたの問題に応じて、それは良いフィットかもしれません。
（Apache Hiveなどが使用しています。）
