私は行列減少アルゴリズムを実装しています。私は数学の学生です。 はもちろん、私は、検索やインターネットを中心に読んで、私が探していたまさに見つかりませんでしたしました（私は私が見つけたものを最後にリストし、私が読んだ論文。）のC++の複雑さと実装のビットベクトルを選択
クイック概要を問題：
ビットベクトルbは（1から（インデックスのみのカップル（倍の大半）で、またはかなりのインデックスであることができ、すべての段階で長さN
Bの変更を修正しました/ 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++ライブラリ
- 論文/文書 持っていいだろう何
：両方の操作が高速である場合
- すなわち「最低1」（1に設定された最後のインデックスを取得するための高速な方法は、（ランク（B））を選択します（O（1）））
私は何を必要としないことである：スペース
- は 012のデータを圧縮
私はSimon GogらのライブラリSdsl 2.0を使用しています。 （https://github.com/simongog/sdsl-lite）が、選択構造
bit_vector::select_1_type
は、すべてのクエリに対してO（n）を初期化する、O（1）がかかりますが、Bの変化を「追跡」（右??私は何も見つかっていないいません非常に具体的です）、変更後のすべてのステップで初期化する必要があります。私が読んだ
論文は以下のとおりです。 「高速、小型、シンプルランク/ビットマップ上の選択」（G.ナバロとE. Providel）と「実践エントロピー圧縮ランク/セレクト辞典」（D. Okanohara K.定兼）と構造が私の要件を満たしている場合、私は）（私は助けにはならなかったと同様のトピックに関するstackexchangeにここに見つけた
物事C++での固体の実装へのリンクをお願い申し上げます。
長い質問には申し訳ありませんが、私は私が必要なものを説明願っていますそれを見つけようと決心しました。私はまだビットベクトルに関連する様々なことについて非常に混乱していますが、それは間違いなく私の専門分野ではないので、どんな説明も分かります。
ありがとうございます。
これを行うライブラリはわかりませんが、簡単に実装できます。あなたは 'b = b＆〜（1 << i）'や 'b = b | b | 'を使ってO（1）のb [i]を0または1に設定できます。 （1 << i）である。それ以外に 'b = b ^（1 << i）'を使ってビットを変更することができます（0の場合は1に、1の場合は0に設定します）。 ＆lt; 1 << i)) > 0'、iビットが1の場合はtrueを返し、それ以外の場合はfalseを返します。 –
"各ステップで索引Iのセットをすぐに取得します（O（logN）、理想的にはO（1）あなたはそれに何をしようとしていますか？あなたが言っていることは、時間の少なくとも10％に比例するいくつかのインデックスを含んでいるでしょうから、歩くにはNに比例した時間がかかるでしょう。 – moonshadow
変更を "追跡"し、N個のサイトを歩くよりも高速にインデックスを取得できるようなデータ構造については、いくつかのツリーの実装や、そのような情報の取得を認めている他のオーバー構造があるかもしれません！挿入/削除の複雑さが増すことを意味するでしょうか？forサイクルの何かに対してO（log N）のコストを認めることはできますが、間違いなくO（N）ではありませんが、可能かどうかわかりません！私はもっと混乱して読んだほうがいいです... btw、読んでいただきありがとうございます;） – joerg91