赤黒木の本質 - Qiita
この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思いついたのか見当がつかずとても不思議に感じました。 しかし、その後赤黒木の成り立ちやその基になったデータ構造について知ると、トリッキーに見えた定義がとても自然であることを実感しました。 おそらく知っている人は当たり前に知っている内容だとは思いますが、知らない人
Dive into Apache Arrow（その１） - KaiGaiの俺メモ
Arrow_Fdwを作るモチベーション 昨年、かなり頑張ってマルチGPUや拡張I/Oボックスを使用してシングルノードのクエリ処理性能10GB/sを達成できた。ただ一方で、PG-StromがPostgreSQLのデータ構造をそのまま使えるという事は、トランザクショナルに蓄積されたデータをそのまま使えるという手軽さの一方で、どうしても行指向データに伴う非効率なI/Oが処理速度全体を律速してしまうという事になる。 昨年の10月頃から直接お会いした人にはお話していたが、現在、PG-StromでApache Arrow形式のファイルを扱うようにするための機能強化に取り組んでいる。目標としては、３月末には動かせる状態にしたいと思っているが。 Apache Arrow形式とは、Sparkの人がよく使っているデータ形式で、大量の構造化データを列指向で保持する事ができる。特定の行を更新したり削除したりといっ
人生で何度目かのダブル配列TRIEを書いた - Qiita
概要 人は人生に何度かTRIEを書くという．そんなわけで，何度目かのTRIEでsudachiのdarts-cloneをクローンしてみました．TRIEの記事は沢山あるので，ここではGoに移植してみて気づいた事をいくつか共有していきたいと思います． 今回の成果物： https://github.com/ikawaha/dartsclone darts-clone 元ネタはこちら．Java版とPython版があります． https://github.com/WorksApplications/Sudachi/tree/develop/src/main/java/com/worksap/nlp/dartsclone https://github.com/WorksApplications/SudachiPy/tree/develop/sudachipy/dartsclone 本家は https:/
簡潔ビットベクトルで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
The Case for Learned Index Structures
Tim Kraska1 MIT Cambridge, MA Alex Beutel Google, Inc. Mountain View, CA Ed H. Chi Google, Inc. Mountain View, CA Jeffrey Dean Google, Inc. Mountain View, CA Neoklis Polyzotis Google, Inc. Mountain View, CA Abstract Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record
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
Collections for JavaScript
This package provides JavaScript implementations of common collections, with many useful features. These collections provide specialized alternatives to plain arrays and objects. They include the ability to observe all changes, have a common interface across every collection and work in both Node.js and the browser. Some data structures are better suited for specific problems. The collections pack
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 => {
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://github.com/trekhleb/javascript-algorithms/blob/master/README.ja-JP.md
LCA and RMQ ~簡潔もあるよ！~
Revisiting b+-trees
learning-algorithms.com
GitHub - pmem/pcj: Persistent Collections for Java
