線形時間RePair - 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 2017」14日目の記事です． はじめに 文字列を圧縮する日々が続いています． 今日は，文法圧縮アルゴリズムのひとつであるRePair1を，線形時間計算量で実現する方法を紹介したいと思います． 非常に高度な内容となった昨日に引き続き，今日もかなり難しい話を扱います．文法圧縮（とRePair）への入門が不十分だとはじき飛ばされるおそれがあるので，この分野になじみが薄いという方は，まず「文字列アルゴリズム Advent Calendar 2017」12日目の記事「文法圧縮入門
BDDとZDD -ブール関数と集合族の圧縮処理- - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 実質上位互換な記事を書いてしまったのでこちらをどうぞ「BDDとZDDを下から読んで再帰アルゴリズムを作る」 本記事は「文字列アルゴリズム Advent Calendar 2017」10日目の記事です．前後の記事は以下の通りです． 9日目: @okateim 氏による「最短超文字列問題」 11日目: @yoshikyoto 氏による「PHPでしりとりをして Code Quest の連鎖ノ試練をクリアする」です． えー、割と良くない体調の中で書いたので色々と多めにみていただきたく… あ，図も書いてないですね…手元にいい感じに図を描けるものが
文法圧縮入門 - 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 2017」12日目の記事です． はじめに 今日は文字列を圧縮してみます． P e t e r _ p i p e r _ p i c k e d _ a _ p e c k _ o f _ p i c k l e d _ p e p p e r s . _ A _ p e c k _ o f _ p i c k l e d _ p e p p e r s _ P e t e r _ P i p e r _ p i c k e d . _ I f _ P e t e r _
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
Compact Directed Acyclic Word Graphを定義する - 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 2017」４日目の記事です． ３日目の記事は@itomomotiによる「周期性補題」でした． ５日目の記事は@kazu0x17による「木の同型性判定」です． 昨年の文字列アルゴリズム Advent Calendar では「Suffix Tree + Suffix Array = Suffix Tray」という記事を書きました． はじめに 文字列アルゴリズム，特に文字列に対する索引が好きです． 古典的な全文索引であるCompact Directed Acyclic Word Gr
JavaScriptで大量のオブジェクトの当たり判定を効率的にとる - Subterranean Flower Blog
ゲームなどのコンテンツにおいて、「当たり判定」から逃れることはできません。オブジェクトとオブジェクトが衝突したかどうかという判定は、インタラクティブコンテンツにおいて最も重要な部分になるからです。 当たり判定の実装自体は難しくありません。ですが、素朴な実装ですと、対象となるオブジェクトが大量である場合に、十分なパフォーマンスが出ません。これはオブジェクトの多い、現代的なゲームでしたり、弾幕シューティングなどを作るときに大きな障害となります。 この記事では、大量のオブジェクトの当たり判定を処理する、効率的な方法について紹介します。 まずは素朴に実装してみる 当たり判定の処理を語るには、ある程度ゲームの骨組みのようなものが必要になってきます。もちろんクラスなどを使わないベタ書きでもよいのですが、大変読みにくくなってしまいます。ですので、今回は、まず簡易的なゲームエンジンのようなものを作って、そ
『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
(UPD 11/15) 下の記事を書くにあたってやらかしたこととか、 返ってきた辛辣な反応を見て、いろいろ言いたくなったんですが、 自分の過ちがどんどん浮き彫りになった気がします。それはまた今度書きます。 個人的にPSP経由の解法はカットが苦手な人にはオススメだと思うので、 そういう人はぜひ試してほしいです。 次記事とか次々記事あたりは面白いんじゃないでしょうか。 - こういうツイートをした。 『昨日のARCに関してなんですが、個人的には、『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProjectSelectionの形そのものを覚えれば瞬殺だからです。だからみんな http://tokoharu.github.io/tokoharupage/docs/formularization.pdf のp7とかwikipediaのページを読んでほしい』 珍しく腹が
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
初期化配列の実装 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? こんにちは、最近ハマっている初期化配列について紹介したいと思います。 はじめに 皆さんプログラミングをする時に配列を使ってますか？使ってない人はほとんどいないのではないでしょうか？ 長さNの固定長配列AはN個の要素を格納でき、かつ任意の位置に保存された要素A[i]を最悪定数時間（以下、定数時間）で読み書き可能な最も基本的なデータ構造の一つです。配列の様々な操作の中で読み書きについで頻出する重要な操作が、配列の全ての要素を指定した値に書き換える初期化操作です。配列の初期化は配列長に対して線形な時間がかかるため、配列長が長い場合や、初期化が
Text Editor: Data Structures – averylaird.com
The first step in building my text editor is to implement the core API. If you’re wondering why I want to do this, the original article is here. I researched several data types, and I tried to be language agnostic. I wanted my decision to not be influenced by any particular language, and first see if there was a “best way” out there, solely based on operations. Of course, a “best way” rarely exist
Mo's algorithm - ei1333の日記
うしのアルゴリズムです. もーもー. (なんかアルゴリズムの概要というよりは, Moを使う問題のソースコードをたくさん貼る場所になってます...) 間違っている可能性があるので, ゆるして>< 2020/08/03 新しいジャッジ環境でバグるコードだったので修正 2022/03/06 新しいジャッジ環境ではなくてもバグるコードだった また計算量の記述も間違っていたので全体的に書き直しました 本当に申し訳ありません Mo's algorithm (Query Square Root Decomposition) 概要 以下の つの条件を満たしていれば Mo を適用できる可能性がある. 配列の要素が不変. クエリを先読みできる(オフライン). 区間 の結果から区間 , , , の結果を容易に計算できる. アルゴリズムの流れとしては以下の通り. 非常にシンプル. 区間を 個のブロックに分割する.
Designing a Tree Diff Algorithm Using Dynamic Programming and A* - Tristan Hume
During my internship at Jane Street1, one of my projects was a config editing tool that at first sounded straightforward but culminated in me designing a custom tree diffing algorithm using dynamic programming, relentlessly optimizing it and then transforming it into an A* accelerated path finding algorithm. This post is the story of the design and optimization of the algorithm, of interest to any
ビームサーチの基礎知識と機械学習への3つの活用事例
深さ優先探索と幅優先探索 深さ優先探索 幅優先探索 ビームサーチ 機械学習への応用 Google Alloの返答 学習時にビームサーチの幅を持たせて学習 3D形状の学習への応用 まとめ 参考文献 ビームサーチ（Beam Search）は、探索アルゴリズムの一種でメモリをそれほど必要としない最良優先探索です。 機械学習の分野でも、翻訳やチャットボットの返答などに応用されています。本記事では、ビームサーチのアルゴリズムを理解してどのように応用されているのかを解説します。 機械学習を活用したシステムを構築する際にも、探索空間が広い場合などには応用可能なので、使いこなせるようにしておくと役に立ちます。 深さ優先探索と幅優先探索 いきなりビームサーチの解説に入る前に、理解しやすいようにグラフ探索アルゴリズムを紹介します。 深さ優先探索 深さ優先探索は、その名の通り可能な限り突き進んで、行けなくなった
Myers Diff Algorithm - Code & Interactive Visualization
2017-06-07 - By Robert Elder Below you will find example source code and interactive visualizations that are intended to complement the paper 'An O(ND) Difference Algorithm and Its Variations' by Eugene W. Myers[1]. Multiple variants of the algorithms discussed in Myers' paper are presented in this article, along with working source code versions of the pseudo-code presented in the paper. Two ref
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
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.要素の部分と木構造の部分を切り離して木のノードが
A new algorithm for finding a visual center of a polygon
By Vladimir Agafonkin We came up with a neat little algorithm that may be useful for placing labels and tooltips on polygons, accompanied by a JavaScript library. It’s now going to be used in Mapbox GL and Mapbox Studio. Let’s see how it works. The problemThe best place to put a text label or a tooltip on a polygon is usually located somewhere in its “visual center,” a point inside a polygon with
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Gap Buffers: a data structure for editable text | James Routley
https://louisabraham.github.io/notebooks/suffix_arrays.html
GitHub - EbTech/rust-algorithms: Common data structures and algorithms in Rust
