今年も半分が終わろうとしているが1月の TODO を解決する。 404 Blog Not Found:Algorithm - Suffix Array を JavaScript で再発明してみた Suffix Array ではなく BWT の方を。 Groovy で実装してみる 参考 http://homepage3.nifty.com/DO/blocksorting.htm…

ゲーム おはじきを使ったゲームをやっていた。 おはじきに 1 から 100 までの数字を書き缶に入れておく。 缶を振ってから10個とりだして並べる。 両手の指を使っておはじきを入れ替えながら数字の順に並べる。 一応競争なんだけど一斉にやったりしているわけ…

文字列照合のアルゴリズムは理解しても結果は java.lang.String#indexOf と変わらない。 ただ String#indexOf が O(NM) であるのに対して O(N) で処理できる*1。 Boyer-Moore algorithm (BM法) は KMP 法や Z algorithm と同じく O(N) だが平均比較回数は優…

理解できると楽しいけど難しくて理解できないことも多い。 理解の種類で分類すると次のようになる。 概要を理解している (API が使える) 仕組みを理解している (実装できる) 様々な問題でそれを適切に使える 大抵 1 はまあ何とかなるし、それさえ分かってい…

WEB-DB PRESS Vol.66 に文字列検索のアルゴリズムが載っていたので、検索していたら気づいたこと 今まで Boyer-Moore だと思っていたものは Boyer-Moore-Horspool だった KMP 法のプログラムはシンプルなのに読めない KMP 法については日本語で書かれたわか…

diffの動作原理を知る〜どのようにして差分を導き出すのか を読んでからずいぶん時間を経たけれども Diff のアルゴリズムを理解できた*1。 理解するためにいろいろ検索したが Diff algorithm の解説が自分にはいちばん分かりやすかった*2。このエントリがな…

Longest common subsequence - Rosetta Code を Groovy で実装してみる。 DP は Java 版を再帰は Haskell 版を参考にした。 Dynamic programming def lcs1(xs, ys) { int N = xs.size() int M = ys.size() int[][] dp = new int[N+1][M+1] for (i in 0..

ハフマン符号はデータ圧縮の手法で 『プログラミングコンテストチャレンジブック』 によると貪欲法になるらしい。 出現頻度が高い文字により短い符号を割り当てるので元の文字列より圧縮できる。 エンコードの手順 文字列から頻度表を作成する 頻度表からハ…

Y combinator について分かった(気がする)範囲のメモ 『Scheme 手習い』 9章 この章が難しくて悩んでいたのだけど理由が分かった。 Learning Programming Languages with Koans によると*1『Scheme 手習い』は Koan の元になっているようだ。 各章はあるテー…

以前、AST変換でバイトコードを直接生成して計算する方法で Pure Java より速いことが話題に上がっていた。*1 http://www.jroller.com/melix/entry/yes_fibonacci_in_groovy_can 速いぞGroovy! - uehaj's blog Pure Java より速いぞ Groovy! - 倭マン's BLOG…

シャッフル関連のメモ 1年前の記事 「Microsoft が提供しているブラウザ選択でランダムであるはずの表示順序に偏りがあった」という内容だ。 MS、Webブラウザ選択画面にアルゴリズム上のバグか − ＠IT Doing the Microsoft Shuffle: Algorithm Fail in Brows…

まずは Groovy の機能で Groovy の List は順列を生成するメソッドを持っている。*1 [1,2,3].permutations().each { println it } ただし、辞書式順序ではない。 [1, 2, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2] [2, 1, 3] [1, 3, 2] でも Collection#eachPermutat…