CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか試したかったので、実装してパフォーマンス計測をしてみた。それぞれの実装の詳しい説明が知りたかったら、https://www.coursera.org/learn/algorithms-part1 を見ると良い。 Union Findとは何か 二つのノードを繋いでいき(Union)、あるノードとあるノードがつながっているか(Find or Connected)を判定するアルゴリズム。 例えば、union(1,6)、union(5,6)、union(2,7)、union(3,8)、union(4,9)、union(8,9

アルゴリズム読み物を読みたくて、いろんなところでオススメされている数学ガールの乱択アルゴリズムを読んだ。なかなか興味深かった。 数学ガール/乱択アルゴリズム (数学ガールシリーズ 4) 作者:結城 浩Softbank Creative/Tsai Fong BooksAmazon この本で興味深かったことは以下の二点。 具体例 -> 規則性 -> 一般化で考える アルゴリズムの実行ステップ数の数学的な解析 具体例 -> 規則性 -> 一般化で考える この本で、問題を考えるときは、具体例を考える -> 規則性を見つけ出す -> 一般化する、という3ステップで考える、ということが書かれていた。 例えば「n枚のカードを一列に並べる方法は、全部で何通りあるか」という問題を考えてみる。この時、n枚のカードのまま一般的に考えようとしてよく分からなくなってしまうという失敗をしてしまうことが多い。そうではな

最近アルゴリズムの勉強でJavaを使っていて、いい機会だしどうせならJavaの言語の詳細な機能や考え方などを知りたいと思っていた。Javaをやっている人に聞いてみると「パーフェクトJava」が良いということなので読んでみた。 改訂2版 パーフェクトJava 作者:井上 誠一郎,永井 雅人技術評論社Amazon おすすめされたとおり非常に良かった。Java8に対応していて、Java8ならどう書くかを知ることが出来たし、クラスやインターフェースの構文の細かな詳細、コレクションの使い方や内部実装、ラムダ式の使い方や考え方、さらにはそれぞれの機能の内部まで細かく眺めることが出来た。Javaはこれまでの歴史からインターネット上には古いコードが無限にあるので、こういう本が一冊リファレンスとしてあるのはありがたい。 この本の中で個人的には以下の章が特に面白かった。これまでの経験から基本的な構文はすんなり

以前 Javaで冪集合を生成する - アルゴリズム学習(その3) - $shibayu36->blog; で冪集合を作るメソッドを実装していた。しかし、以前の実装だとListでしか冪集合を作ることができなかった。最近パーフェクトJavaを読んで、ジェネリクスについて学んだので、試しに冪集合を作るメソッドをジェネリクス対応してみた。コードは ここ においてある。 package org.shibayu36.algorithms; import java.util.ArrayList; import java.util.List; public class PowerSetGenerics { public static <T> List<List<T>> make(List<T> data) { if (data.size() == 0) { List<List<T>> empty = ne

文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。 今回はJavaでSuffix Trieを使った探索をしてみた。 トライ木とパトリシア 先にトライ木とパトリシアについて紹介。 今回Suffix Trieという構造を調べていると、同じような構造としてSuffix Treeというものが出てきて混乱した。よく調べてみると、Suffixの集合をトライ木という構造で実装したものがSuffix Trieで、パトリシアという構造で実装したものがSuffix Treeらしい。 トライ木はnodeを連結していって、その枝に1文字を割り当てて辿れるようにした構造。トライ木は枝に1文字しか割り当てない構

なんとなくアルゴリズム系の読み物読んでみたかったので読んだ。 世界でもっとも強力な9のアルゴリズム 作者:ジョン・マコーミック日経BPAmazon この本は、著者が3つの基準で選んだ「偉大なアルゴリズム」について、エンジニアでなくても分かるような簡単な言葉を使って紹介してくれる本である。以下のようなアルゴリズムについて紹介している。 検索エンジンのインデクシング ページランク 公開鍵暗号法 誤り訂正符号 パターン認識 データ圧縮 データベース デジタル署名 話題がかなり身近なものであり、説明が本当にわかりやすいため、とりあえずアルゴリズムを学ぶ前の読み物として非常におすすめ。個人的には検索エンジンやページランク、パターン認識あたりが興味深かった。この本を読んで、興味を持った部分について、さらに深く学習をしていくと良いかもと思った。 読書メモ ## 検索エンジンのインデクシング - 検索エン

アルゴリズムを学習していると、ある実装の速度がどのくらいか計測したいことがよくある。これまでは、currentTimeMillisを利用して、愚直にベンチマークを取っていたのだけど、結構だるい感じだった。 調べてみると、jmh と nanobench という二つのツールがあった。jmhは使ってみたけど、非常に重厚で難しかったので、nanobenchを使ってみた。 ハマったこと nanobench のREADME.mdを見ていると、nanobench.jarを落としてきて、以下のように実行すると良いと書いてある。 > javac ListBenchmark.java > java -jar nanobench.jar ListBenchmarkしかし、Java初心者のためか、jarファイルのことがよく分からなかったり、classpathの問題でハマったり、とにかくハマりまくってうまく動かなか

最近、コンピュータサイエンスなどの基礎的な知識を学習するように心がけている。できる限り今後も長い期間役に立つ、寿命の長い技術や知識を付けておきたいためである。その一貫で アルゴリズムを学習 してみている。 学習をはじめて感じた課題 しかし、とりあえずアルゴリズムを学習してみると、学習を続けられるか分からないという課題も感じた。 寿命の長い技術であるほど、日々の開発にすぐに利用できないことが多い 例えばアルゴリズムを学んだとしても、それが役立つまでいくにはある程度長い時間が必要 日々の開発に利用できていないと、モチベーションをずっと保ち続けるのが難しい モチベーションが保てないと、結局途中で勉強をやめてしまい、日々の開発に利用できるレベルまでたどり着けない 流行りの技術とかは、すぐに開発に導入してみるとかができるので、とりあえずモチベーションは保ちやすい。しかし、数学とかアルゴリズムとかLi

最近、仕事で一週間に一度はペアプロをするということをしているのですが、これによって思ってもみなかった効果が出たので紹介します。 ペアプロというとプログラムを書いている人の後ろでもう一人が見ていて、逐次指摘などしながらプログラミングすることによって、生産性の向上やバグ発生率を抑えるみたいなことが言われています。僕自身もそう思いながらペアプロに望んでいたのですが、違うところで効果が出始めました。それは自身の開発環境がだんだん良くなっているということです。 ペアプロによって開発環境が良くなる 今回開発環境といっているのは、emacsなどのエディタや、ターミナルなど、ローカルマシンの設定などのことです。 なぜ開発環境がよくなっていっているというと、見ている時と見られている時のそれぞれにおいて、次のようなことが起こるからです。 見ている時 後ろから見ていると突然プログラムを書いている人が、自分の知ら

最近PrePANの開発を手伝っていて、Workerの仕組みをQudoで作りました。初めてWorkerの仕組みを一から作ったのでメモしておきます。 Worker処理に必要な部品、それぞれのQudoでの実装、Workerプロセスを管理するためのdaemontools、capistranoでのdeployという順番で書いていきます。 Workerとは ざっくり言うと非同期に色々実行するための仕組みです。perlだとTheSchwartz、Qudo、Jonkとかがあります。 Worker処理に必要な部品 今回作ってみて、Worker処理は大きく分けて次の三つくらいのものが必要だと分かりました。 ApplicationからJobをinsertする部分(Qudo) 実際のJobの処理(Qudo::Worker) Jobの実行を管理して、Jobに処理を委譲する部分(Qudo, Qudo::Paralle