赤黒木の本質 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い
簡潔ビットベクトルで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
前処理O(n)クエリO(1)のLCAと静的RMQ - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ
時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装しました。 アルゴリズムの解説はDさんのスライド [1] LCA and RMQ ~簡潔もあるよ！~ がとても分かりやすいのでそちらを参照してください。 概要だけ説明します。 LCA の概要 LCA は頂点を dfs 順で訪れた順に並べると深さの列の RMQ に帰着されます。このことは [2] 蟻本 などに載っています。 この列は隣り合う数の差がちょうど になっています。 この列を 個ずつのブロックに分け、それぞれのブロック内の最小値を求めます。 ブロックの数は 個になるので、ブロックの区間の最小値を求めるクエリは sparse table を使うと前処理 、クエリ で処理できます。 ブロックの中についてですが、各ブロック
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
典型データ構造まとめ - beet's soil
なんか前回伸びたので 参考 hamayanhamayan.hatenablog.jp ei1333's page 宣伝 beet-aizu.hatenablog.com 以下とりあえず辞書順（そのうち典型度順にしたい） Binary Indexed Tree 一点加算、先頭からの区間和、k番目に大きい値が で可能 library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub 容易に多次元に拡張が可能（実用上は2次元くらい？ library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub Binary Trie 二進数を管理するTrie木 全体にXOR、k番目に大きい値、lower_bound等が で可能 library/binarytri
Revisiting b+-trees
This document discusses B+-trees, which are commonly used to index data in databases. It provides an overview of the structure and functionality of B+-trees, including keys, pointers, fanout, leaf nodes, and internal nodes. It also describes Btree4j, an open source Java implementation of B+-trees that supports features like paging, prefix indexing, and bulk loading. The document aims to revisit th
The Case for Learned Index Structures
Tim Kraska111Work done while author was affiliated with Google. MIT Cambridge, MA kraska@mit.edu Alex Beutel Google, Inc. Mountain View, CA alexbeutel@google.com Ed H. Chi Google, Inc. Mountain View, CA edchi@google.com Jeffrey Dean Google, Inc. Mountain View, CA jeff@google.com Neoklis Polyzotis Google, Inc. Mountain View, CA npolyzotis@google.com Abstract Indexes are models: a B-Tree-Index can b
Treasure 2017 の研修資料は Go を学ぶのに最高だった - kakakakakku blog
Go 関連の本を読んだり，サンプルコードを写経するだけではなく，もっと実践的に勉強したいなと思って調べていたら，VOYAGE GROUP の Treasure 2017 と言うインターンシップの研修資料が GitHub に公開されていることを知って，さっそく挑戦してみた．数日間取り組んでみて，とにかく素晴らしかったので，紹介したいと思う．suzuken 先生，素晴らしすぎます！ Go入門 GitHub - voyagegroup/talks 学べるテーマ Go の研修資料とは言え，幅広いテーマで Go を学ぶことができる点が素晴らしかった．ザッと挙げるとすると以下のようになる．テーマを見るだけで，もうワクワクしてくるのではないだろうか？ アルゴリズム実装とテストコード フィボナッチ数 スタック CLI net/http curl 実装 スクレイピング実装 コンカレンシー goroutine
SymSpell対BK木：100倍速い文字列のあいまい検索とスペルチェック | POSTD
注釈：500,000単語収録の辞書内における1,000単語の検索時間 X:最大編集距離 Y:検索時間/ms 従来、スペル修正や文字列のあいまい検索には、 BK木 が適していると言われてきました。しかし、これは本当でしょうか。 また、 スペル修正に関する私のブログ に寄せられたコメントには、BK木が、あいまい検索のためのデータ構造として優れていると言及されていました。 そのような経緯から、今回、BK木と他の選択肢のベンチマークを取って比較してみようと思い立ったわけです。 近似文字列検索アルゴリズム 近似文字列検索では、文字列リスト内の文字列を検索し、特定の 文字列メトリック に従って、それに近い文字列を返します。 文字列メトリックは多数あり、例えば レーベンシュタイン距離 、 Damerau-Levenshtein距離 、 ハミング距離 、 ジャロ・ウィンクラー距離 、 Strike a m
Union-Find with deletions - 誤読
謎のデータ構造を見つけてしまった。実装したくなかったが、してしまった。後悔しかしていない。 UnionFindといえば競プロerであればほとんどの人が知ってると思われるが、あれはUniteとFindはあってもある要素をフリーにするという操作ができない。 UF木の葉以外を削除しようとすると計算量が増えてしまうのは想像がつくと思う。 そこでUnion-Find with Deletionsというのがあって、これを使うとUniteをO(A(n)),FindをO(A(n)),DeleteをO(1)でできるようになっておいしい。 （追記）論文でUniteがO(1)なのは集合をしていしてUniteする実装だからで、要素を指定してそれらの属するグループを併合するっていうのはFindを挟む必要があるのでO(A(n))になっているだけです。 主なアイデア 1.要素の部分と木構造の部分を切り離して木のノードが
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Minimal Acyclic Subsequential Transducerで遊ぶ - Negative/Positive Thinking
はじめに https://pycon.jp/2015/ja/proposals/vote/11/ Pycon2015で発表された「Pythonで作って学ぶ形態素解析」で紹介されていた辞書データ構造の「Minimal Acyclic Subsequential Transducer」について、勉強のために書いてみた。 Minimal Acyclic Subsequential Transducerとは Finite State Transducerの一種 Transducerにおいて、initial stateが一つで、同じ入力ラベルを共有する同じ状態からのの遷移が2つ以上なく、各最終状態での最終出力文字列が高々p個のとき、p-subsequentialで、pが整数ならfinitely subsequentialというらしい minimal(状態数が最少)、Acyclic(サイクルが無い)
SharedArrayBufferとAtomics APIについて - JS.next
概要 JSで大きな処理を効率良く捌きたい時、今までもWorker等でスレッド立てて処理を分割する事はできたが、 スレッド間のやり取りの方法は制限されたものしかなく、バッファを共有することもできなかった。 そこで新しく導入されたSharedArrayBufferを用いると、スレッド間で共同利用できるバッファを作る事ができる。 記事更新履歴 ※この記事はV8が仕様の新しいバージョンを実装するのに合わせて断続的に更新していきます。 [2016/07/19] V8の半年ぶりの新仕様追従に対応 [2015/09/30] 公開 通常のArrayBufferとの比較 前準備： // メッセージを受け取ると渡された型付配列のインデックス0を123にするWorker w = new Worker(URL.createObjectURL(new Blob([` self.onmessage = e => {
Quantization based Fast Inner Product Search
We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recent
Skylakeファーストインプレッション - anon42’s diary
2015/8/5に開発コードSkylakeで知られていたIntelの新CPUが発売されました。私も早速動かしていますが大変よい結果を得ています。今回は主に各所で公開されている情報等から従来のマイクロアーキテクチャとの比較を見てみます。 フロントエンド とりあえず4wayのままのようです。フェッチ帯域やMacroOps Fusion等はまだ確認していません。あんまり変わっていない気がします。 実行ユニット instlatx64の結果がアップロードされています。 http://instlatx64.atw.hu/ 主にFPU周りの変更が目立ちます。私が使う上で気になったところを挙げます。 div/sqrtのスループットが劇的に向上した。ついでにrcpps/rsqrtpsも高速化している。 blendvのスループットがHaswell/Broadwellの2から1に向上した。SandyBridge
Top-k文書列挙問題 - DO++
いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。 "Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf) 扱っているのは次のような問題です（説明のため本来のと言い換えています） n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています． この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。 簡単に思いつくのは，各節点に適当な個数(d)の答えをあ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
javascript-algorithms/README.ja-JP.md at master · trekhleb/javascript-algorithms
LCA and RMQ ~簡潔もあるよ！~
learning-algorithms.com
Welcome to nginx!