3

私は行列削減アルゴリズムを実装しています。私は数学の学生です。明らかに、私はインターネットを検索して読みましたが、探していたものを正確に見つけることはできませんでした (見つけたものと読んだ論文を最後にリストします)。

問題の簡単な概要:

  • ビットベクトル b は FIXED LENGTH N です。

  • b はすべてのステップで変化します (ほとんどの場合、2、3 のインデックスでのみ、またはかなり多くのインデックス (1/10 から 1/3) で、これは 10% までのケースでのみ)。

  • 私はすでにスパース実装を持っています。ビットベクトルのスマートな実装を使用してコーディングしたいと思います。

    //initialize to 0 
b=bitvector(0, n=N)

for i in 1 to N
    {some operations on the bitvector b}
    get I= { j | b[j] == 1 }
    {save I}

私が必要とするのは：

  • b[i]=1 または =0 (おそらく O(1)) をすばやく設定します。
  • 各ステップで一連のインデックスをすばやく取得しますI(間違いなく O(logN) 以下、理想的には O(1))
  • それを可能にする C++ ライブラリ
  • 論文/ドキュメンテーション

あるといいもの：

  • 「最低のもの」を取得する高速な方法 (両方の操作が高速 (O(1)) の場合、最後のインデックスを 1 に設定、つまり select(rank(b)))

私が必要としないのは：

  • スペースを節約
  • データを圧縮する

Simon Gog らのライブラリ Sdsl 2.0 を使用しています。( https://github.com/simongog/sdsl-lite ) しかし、選択構造

bit_vector::select_1_type

初期化には O(n) のコストがかかり、すべてのクエリに対して O(1) がかかりますが、b の変更に「従わない」(そうですか?? 私はそれについて非常に具体的なものを見つけていません)。変更後のすべてのステップ。

私が読んだ論文は次のとおりです。「ビットマップの高速、小型、単純なランク/選択」(G. Navarro および E. プロビデル) および「実用的なエントロピー圧縮ランク/選択辞書」(D. 岡野原 K. 定兼) および私C ++での堅実な実装へのリンクをいただければ幸いです（構造が私の要件を満たしている場合）

役に立たなかった同様のトピックについて、stackexchange で見つけたもの:

長い質問で申し訳ありませんが、必要なものとそれを見つける決意を説明していただければ幸いです。ビットベクトルに関連するさまざまなことについて、私はまだ非常に混乱しています。それは間違いなく私の専門分野ではないため、明確化していただければ幸いです。

前もって感謝します。

4

1 に答える 1