英会話なんて

所詮パターンの組み合わせなんですよ。

パターンで話せる英会話「1秒」レッスン (成美文庫 し- 7-1)

・・・と信じて、パターンをとにかく頭に叩き込んで、ひたすら声に出すことにした。といっても、英語を話す機会は留学生と会話するくらいなので、まずは自分の行動をぼそぼそっと英語で表現することからはじめよう。

memcachedのインストール

インストールは、Fedora 11で行いました。

memcachedの動作には、libeventというライブラリが必要になります。

$ sudo yum install libevent libevent-devel

次にmemcachedをインストールします。memcachedのtarballは↓から。

http://www.danga.com/memcached/download.bml

$ tar zxf memcached-<version>.tar.gz
$ cd memcached-<version>
$ ./configure
$ make
$ sudo make install

インストール先は、

/usr/local/bin/memcached

になります。

久しぶりの投稿

一ヶ月半ぶりの投稿です。自分にとって大事なことが立て続けに起こっていたので、こんなに間が空いてしまいました。だいぶ落ち着いてきたので、また少しずつブログを書こうと思います。

卒論

今後は卒論の話題がメインになってくるかな。今は次のようなキーワードを元に、分散システムについて考えています。

オンメモリキャッシュ、key/value store、P2P、仮想化、マルチプロセッサ、SSD

新規性を見つけるのってすごく難しいですね。サーベイすればするほど、誰かがすでに研究しているようなことばかりで、新規性が見つけられなくなります。サーベイせずにさっさと論文書いたほうが良いのかも。知らぬが仏。・・・とまぁ、それは冗談として、思いついたことを少しずつアウトプットしていって、自分なりのアイディアを練りだせていければ良いね。

ネットワークスペシャリスト試験

あと、今後の目標としては、10月のネットワークスペシャリスト試験です。本日問題集を買ってきました。

ネットワークスペシャリスト予想問題集〈2009〉 (情報処理技術者試験対策書)

情報処理試験では、いつもアイテックの問題集を使用しています。解答が丁寧で、問題数も豊富なのでおススメです。毎日少しずつ勉強していこう。

PostgreSQLで自動的にインデックスが生成される条件

PostgreSQLのインデックスについて。

インデックスの有無によるクエリ実行速度の違いをベンチマークしていて気がついたんですが、制約によっては勝手にインデックスが生成されるんですね。それに気づかなかったから、実験データが無駄に・・・orz

せっかくなので、その条件を調べてみました。ちなみに生成されるインデックスはすべてB-treeです。使ったのはPostgreSQL 8.3.7。

インデックスが生成される場合

• PRIMARY KEYを指定する
• UNIQUE NOT NULLを指定する
• UNIQUEを指定する

UNIQUE NOT NULLはPRIMARY KEYと同じ意味になります。

インデックスが生成されない場合

• NOT NULLを指定する
• 何も指定しない

まとめ

UNIQUE制約またはPRIMARY KEYが定義されるとインデックスが生成されるようです。

調べてみると、このようにUNIQUE制約されたカラムにつけられるインデックスを一意インデックスといい、その一意性を強制するためにつけられるみたいです。この「強制する」というのは、B木に挿入する過程でそれと同じ値が存在していないかチェックするってことですかね？あと、MySQLでも同様な条件で一意インデックスが生成されます。

SQLは知らないことが多い・・・もっと勉強しないと！

参考

• PostgreSQL 8.3.7文書　http://www.postgresql.jp/document/pg837doc/html/indexes-unique.html
• MySQL/制約 - MinacoWiki

最長共通部分系列長（LCS）を求めるJavaプログラム

素朴に実装。LCS長が何たるかは別のページを参照してください。

LCSのアルゴリズムは、系列Xのi番目をxi、系列Yのj番目をyjとすると、

• i = 0 または j = 0 のとき、
  • LCS(i, j) = 0
• i, j > 0 かつ xi == yj のとき、
  • LCS(i, j) = LCS(i-1, j-1) + 1
• i, j > 0 かつ xi != yj のとき、
  • LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

ですが、Javaは配列が0オリジンなので、このまま素直に実装してしまうと系列XとYの一文字目が一致した場合でもLCS長が0になってしまいます。そこでちょっとトリッキーな実装にしてみました。

public class LongestCommonSubsequence {

	// 実行サンプル
	public static void main(String[] args) {
		System.out.println(LCS_Length("ABCBDAB", "BDCABA"));
	}

	private static int LCS_Length(String str1, String str2) {
		int len1 = str1.length(), len2 = str2.length();
		int[][] lcs_table = new int[len1][len2]; // LCS長を格納した表
		
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				if (str1.charAt(i) == str2.charAt(j))
					lcs_table[i][j] = ((i == 0 || j == 0) ? 0 : lcs_table[i-1][j-1]) + 1;
				else if (str1.charAt(i) != str2.charAt(j))
					lcs_table[i][j] = Math.max(
							i == 0 ? 0 : lcs_table[i-1][j],
							j == 0 ? 0 : lcs_table[i][j-1]);
			}
		}
		
		// LCS表の表示
//		for (int i = 0; i < len1; i++) {
//			for (int j = 0; j < len2; j++)
//				System.out.print(lcs_table[i][j] + " ");
//			System.out.println();
//		}
		
		// LCS表の最も右下にLCS長が格納されている
		return lcs_table[len1-1][len2-1];
	}
}

今日買った本

WEB+DB PRESS Vol.50

WEB+DB PRESS Vol.50

WEB+DB PRESSのvol.50（前回号）です。key-valueストアの特集が読みたくて購入。最近のIT系雑誌の中ではこれが一番面白い。旬な技術から古典的な技術まで、幅広く解説記事が載ってて読み応え抜群です。おススメ。

創造はシステムである 「失敗学」から「創造学」へ

創造はシステムである 「失敗学」から「創造学」へ (角川oneテーマ21)

何やら評判が良かった＆さらっと読みながしたら面白そうだったので購入。

目指せ！プログラミング世界一

こんな本が出てました。即購入。

目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦

恐らく国内初のICPC本じゃないでしょうか。書かれているのもACM日本支部副支部長の筧捷彦さんだし、実質公式ガイドブックになるのかな。執筆者が豪華・・・。

まだ読んでないんですが、さらっと眺めた感じだと物語チックな出場までの手引きと、2008年度の国内予選問題の解法が説明されているみたいです。国内予選は問題解説がないし、このように開催者側による解説があるとスキルアップにつながって良いですね。ICPCの問題って解法のとっかかりが思いつかなかったら勉強のしようがないから、毎年なんらかの方法でフォローアップしてくれると良いんですが・・・。

参加してみたいって人は一読の価値がありそうです。