スキップリスト - Wikipedia
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した[1][2][3][4]。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 スキップリストの例。1〜10を追加し、ソートされた状態で保持されている。 説明[編集] スキップリストはリストの階層になっている。
BDDとZDD -ブール関数と集合族の圧縮処理- - Qiita
実質上位互換な記事を書いてしまったのでこちらをどうぞ「BDDとZDDを下から読んで再帰アルゴリズムを作る」 本記事は「文字列アルゴリズム Advent Calendar 2017」10日目の記事です．前後の記事は以下の通りです． 9日目: @okateim 氏による「最短超文字列問題」 11日目: @yoshikyoto 氏による「PHPでしりとりをして Code Quest の連鎖ノ試練をクリアする」です． えー、割と良くない体調の中で書いたので色々と多めにみていただきたく… あ，図も書いてないですね…手元にいい感じに図を描けるものが無いので後日…とりあえず Wikipedia で代用… はじめに 本記事で扱うトピックは Binary Decision Diagram (BDD) ，および Zero-suppressed Binary Decision Diagram (ZDD) という
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium
基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
Elias-Fano encoding: 単調増加する数列をほぼ簡潔に表現する - モナドとわたしとコモナド
Haskell Advent Calendar 2018 20日目 単調増加する自然数の列を、最低限のビット数で表現するための興味深いテクニックと、Haskellによる実装を紹介する。 Elias-Fano encoding この手法は、簡潔データ構造に分類されるもの一つであるが、厳密には条件を満たさないため疑似簡潔データ構造と呼ばれる。1970年代、Peter EliasとRobert Mario Fanoによって独立して発見された。 例題として1, 1, 4, 10, 17, 22, 23, 30という列をエンコードしてみよう。まず、それぞれの数を上位3ビットと下位2ビットに分割する。列の長さをNとしたとき、上位のビット数はとする。 上位ビットの列は000 000 001 010 100 101 101 111となる。これをヒストグラムのようにして23個のビンに分ける。 000: 2個
Suffix Array - Qiita
これは「データ構造とアルゴリズム Advent Calendar 2018」9日目の記事です． はじめに Suffix array1 はよく知られたデータ構造のひとつです．1990年に提案2されて以来，その使われ方は多岐にわたります．本記事では，この suffix array の基本事項として， suffix array とは何か suffix array を全文索引として用いる方法 を紹介したいと思います． パターンマッチングと全文索引 パターンマッチング とは，文字列 $T$ から，パターンと呼ばれる文字列 $P$ を探す問題です．たとえば， $T =$ 麒麟鼬蝙蝠駱駝蝦蟇鼈樹懶鼠膃肭臍羆狒狒鰐麒麟猩猩鼠鼠鼠鼠鼠蟒蛇鼈鼬羆蜥蜴駱駝羆麒麟鼈鼬狒狒狒狒羆蝙蝠膃肭臍麒麟蝙蝠鼬蜥蜴鼬狒狒蝮樹懶鼬羆蝮膃肭臍麒麟羆駱駝蝙蝠蟒蛇狒狒蝙蝠樹懶鼈蜥蜴駱駝羆鼬羆樹懶犀鰐蝙蝠鼠狒狒蝦蟇鼬蜥蜴鼠蝮蝦蟇蜥蜴龍麒
簡潔ビットベクトルでRubyをlog N倍速くした - クックパッド開発者ブログ
技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。 今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。 ひとことで言うと、「簡潔ビットベクトルを索引に使うことで、プログラムカウンタから行番号を計算するアルゴリズムをO(log N)からO(1)に改善した。これにより、TracePoint有効時やコードカバレッジ測定下で、長さ N のメソッドの実行が O(N log N) から O(N) に高速化される」ということです。順に説明します。 背景：Rubyのバイトコードの構造 この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。 たとえば x
Elias-Fano Encodingで遊ぶ - Negative/Positive Thinking
はじめに 読んでる論文に出てきてたElias-Fano Encodingをちょっと書いて遊んでみた。 Elias-Fano Encodingとは 単調増加整数列の表現方法のひとつ 他の方法としては、ちょっと情報が古いけど http://d.hatena.ne.jp/jetbead/20110918/1316373030 など 厳密にはsuccinctではないが、succinctに近い表現 quasi-succinct representationと言っている 整数列の各値を「上位bit列」と「下位bit列」に分割し、整数列全体では、上位bit列を「(negated) unary code表現」、下位bit列を「各下位bitを連結したbit列」で表現したもの 上位、下位のbit数は等分ではなく、上位bitがceil(lg(n))個 例: {3,4,5}という整数列の場合 ceil(lg(3)
文字列の範囲書き込みを効率的に行うアルゴリズム - Qiita
はじめに $T[1 \ldots N]$の文字列の任意の範囲$(j, k)$の要素に指定した文字$c$を書き込む（$T[i] \leftarrow c$ for $j \leq i \leq k$)、文字列の範囲書き込み問題を考えます。 例：領収書の都合の悪い部分を黒塗りにする 愚直に行えば$k-j+1$個の要素の書き込みが必要、かつ範囲長の最大は$N$なので$O(N)$時間かかります。 範囲書き込みが稀であれば問題ありませんが、頻繁に起こる場合はこの書き込みにかかる時間がボトルネックになってしまいます。ここでは読み書きにかかる時間を少し犠牲にし、範囲書き込みをより高速にかつ省領域に行えるアルゴリズムをご紹介します。 正確には各操作を以下の時間で文字列$T$に加え$N-1$bitsの追加領域で実現します。 読み込み 書き込み 範囲書き込み 全体書き込み 範囲書き込みアルゴリズム 大まかなア
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ