テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み – RORO
Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。 (追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future) なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。 リアルタイム共同編集の流れ 共同編集システムの登場人物は次の通りです： サーバ x 1（各クライアントから届く編集操作をもとに、最新の文書を保持します） クライアント x N（文書を編集する側です） そ
WebGPUとRustでネコチャンを点描した話
はじめに 昨年１２月にこんなツイートを見かけました。 かわいいですね。幸いにして論文と実装が公開されていたので、自分でもやってみようと思って、その結果を書いたのが前回の記事です。 読んでいただければわかるとおり、前回の記事の中ではGPUを使わずにアルゴリズムやデータ構造を工夫して近似的に計算しています。結果の画像についてはそんなに悪くないと思っていますが、限界もありました。パーティクルの数も少ないし、一部の画像ではうまく行きませんでした。 やっぱり、もっとちゃんとネコチャンを点描してみたいですよね。 なので、今回の記事ではGPUを使ってアルゴリズムを再現し、よりヴィヴィッドなネコチャンの点描を作成しようと思います。GPUを使って計算するために、WebGPUのRust実装であるwgpuを使用します。ネコチャンの画像を点描にしたい人と、WebGPUに入門してcompute shaderで何か計
JavaScriptで変化点検出がしたい
時系列データを触っているとなにか異常があった、モードが変わったことを検知したくなります。 そうすると機械学習に頼ることになるわけですが、できればパラメータチューニングを最小限にしたい。 調べてみると特異スペクトル変換(Singular Spectrum Transformation)という方法がよさそうです。 ノンパラメトリック（分布を仮定しなくてよい） ノイズに強い 決めるべき変数が少ない いいことづくし。 唯一欠点として計算量が多いというのがありますが、ビッグデータを扱うわけでもない個人の解析の範疇であればマシンスペックが潤沢な現代においてあまり気にする必要もないでしょう。 というわけで特異スペクトル変換をJavaScript(TypeScript)で行ってみます[1]。 サンプルページ 特異スペクトル変換 詳しい理論やアルゴリズムの説明は書籍[2][3]、論文[4][5][6]に譲り
単一始点最短路(Dijkstra法) - アルゴリズムとデータ構造大全
単一始点最短路(Dijkstra法) 重みが全て\(0\)以上である任意の重み付きグラフ\(G\)における単一始点最短路は，Dijkstra法によって\(O(|E| \log |V|)\)で求めることができる． 単一始点最短路とは，あるノード\(s \in G\)から，\(G\)に含まれる任意のノードまでの最短路である．以降始点を\(s\)と呼ぶ． 説明 Dijkstra法の説明と正当性の証明を同時にするような形で説明を書く． 以下の説明では，あるノード\(i\)について，\(s\)から\(i\)までの最短路長を\(d_{s→i}\)と表記する．また，あるノード\(i\)から出てあるノード\(j\)に入る(有向)辺の重みを\(e_{i→j}\)と表記する． Dijkstra法では，\(s\)からの最短路を，最短路長が小さいノードから順に求めていく．つまり，任意の時点で，最短路が求まっている
Wu らによる差分検出の O(NP) アルゴリズム実装シリーズ ②探索方法 - Qiita
はじめに これは、3回にわけて Wu らによる O(NP) アルゴリズムを解説、実装するシリーズです。 ①仕組み、考え方 ②探索方法 <- 今回 ③Goによる実装 の3部に分かれています。 今回も、前回に引き続き Wu らによる O(NP) アルゴリズムの解説をしていきたいと思います。 前回の ①仕組み、考え方編 では、大まかな考え方を整理して、なぜ計算量が下がるのかわかりました。 今回は、前回わかったことを利用して、実際にどう探索していくのかまとめていきます。 元論文は An O(NP) Sequence Comparison Algorithm by described by Sun Wu, Udi Manber and Gene Myers です。興味のある方はそちらも目を通すと面白いと思います。 最終的な実装を確認したい方は https://github.com/convto/on
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
2013-11-04
最近読んで面白かった話 High Energy Asymptotics of Multi--Colour QCD and Exactly Solvable Lattice Models http://arxiv.org/abs/hep-th/9311037 High energy QCD as a completely integrable model http://arxiv.org/abs/hep-th/9404173 High-Energy QCD as a Topological Field Theory http://arxiv.org/abs/hep-ph/9807451 Integrability of High-Energy QCD http://ci.nii.ac.jp/naid/110001208781 元々、高エネルギー極限(Regge極限)に於けるQCDを記述する有
隠れた良書「計算機シミュレーションのための確率分布乱数生成法」を大プッシュしたい - EchizenBlog-Zwei
偶然見つけたのだが「計算機シミュレーションのための確率分布乱数生成法」が大変な良書であったので、とりいそぎメモしておく。ちゃんと読んだら後でレビューする。 本書は簡単にいうと「様々な分布から乱数生成(サンプリング)するプログラム」の実装法をまとめた本。確率統計の本を読んだりして「○○分布からサンプリング」すれば良いことはわかったのだが、どうやって実装していいかわからず途方に暮れた経験を持った人は多いのでは。 そういった方にとって本書は福音となるのではないだろうか。 とりあえず本書はweb上に情報が少ないので、どんな分布を扱っているのか列挙しておく。かなり多いので驚かれるかもしれない。 [連続分布] 正規分布(Normal distribution) 半正規分布(Half Normal distribution) 対数正規分布(Log-Normal distribution) コーシー分布(
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
テンプレートマッチングの魅力 ～ 物体検出・位置決めの定番技術 ～