sileのブログスマートフォン用の表示で見るsileのブログこの広告は、90日以上更新していないブログに表示しています。algorithmLOUDSの四回目。Sums』ただし、良く分からないところや、詳細が省略されているところや、もっと簡潔にできそうなところなどが(少なからず)あったため、以降に載せるbit-vectorの実装は、この二つの論文で説明されているそれとは、(少なからず)異なっている。「参考」にして、後は自分好みに実装した、といった感じ。実装するもの以降では、select1とrank1を備えたbit-vectorを実装する。select0およびrank0を実装しない理由は以下の通り。操作対象となるビット列。Nビットまずは、これまで使ってきたselectおよびrankの実装を再掲する。46この実装では、定義から自明な通り、selectおよびrankにN(ビット列のサイズ)に比例した時間が掛る。他の実装のような補助的なデータ構造が必要ではないので、ビット列自身のための領域しか消費しない。N*32+N*16ビット次は、一度の配列アクセスだけで、select1およびrank1が求められる実装。46これだと、あらかじめ配列に保存しておいた値を取り出すだけなので処理は高速だが、rank1用の配列に32*Nビット、select1用の配列に(平均して)32*N/2ビットの領域が必要になってしまい、(LOUDSにおいて)木をわざわざビット列で表現する(空間効率が極めて良いという)メリットが相殺されてしまう。N*1.5ビット実装3は、実装1と実装2を組み合わせたような方法で、基本的には次のような考えに基づいている。※計算済み配列[引数/間隔]未計算部分の計算は、最大でO(間隔の広さ)=O(1)で済む/span>つまり、大まかな値を実装2の方法(配列アクセス)で取得しておき、細かい値は実装1の方法(間隔の広さ分のビット列の走査)で取得する、といったような方法。458))この時点での実装3の留意点。N*2ビット実装3では、select1でnth番目の1ビットが属するブロックを求めるために、全てのブロックを対象として二分探索を行う必要があり*1、そのために処理ステップ(?)がO(log(N))になってしまっていた。実装4では、bit-vector~~にフィールドを追加して、この二分探索をほとんどの場合にO(log(1))で行えるように修正する。平均1.75Nビット使用)で、だいたいの場合にselect1/rank1をO(1)で実行できるbit-vectorが出来た。ちなみに、select0もサポートした場合、実装4の使用領域は(最悪/最善を問わず)常に2Nビットとなる。実装4のbit-vectorのselect1のステップ数は、ビット列の長さというよりは、ビット分布のパターンに依存し、1ビットが極めて疎な列に対しては若干効率が悪くなる。それが実用上どの程度問題になるかは、ちゃんと調べてないので分からないが、LOUDS++での使用に限れば、ほとんど問題がないのではないかと考えている(確固とした根拠は無し)。###ここまででbit-vectorの実装は終了。LOUDS++は、要素数Mの木を表現するために(約)長さMのビット列が二つ必要。そのビット列を、今回作成したbit-vectorを使って実装すれば、約4Mビットで木*2を表現できることになる。ソースコード実装4の元になったソースコードを下に載せておく。基本的には実装4と同じだが、以下の点は異なる。bitvector)))))))*1:実装3は、実装2でのrank-table(のサイズ節約版)を保持しているためrank1は高速に行えるが、select-tableに対応するものはないためselect1が若干非効率になっている。実装4は、select-tableの対応物的なものを提供し、この部分の高速化を図っている*2:正確には木の構造。各要素に付随する値などの情報は、別に領域を確保する必要がある。bit-vectorTweet広告を非表示にする関連記事2010-12-27昇順数値列のunary表現と定数時間アクセス数値列の圧縮に関するメモ書き。LOUDS++LOUDS++*1の三回目。rankとselectLOUDS++*1実装の続き。読者になる検索リンクgithub最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ月別アーカイブ最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ注目記事ブクログqiitasileのtips人気エントリーはてなブログをはじめよう!sileさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。