Software Archive

あちこちでソースを編集するので整合性がとれないし，githubでバージョン管理してみることにしてみました．はまってしまったらやめるかもしれません．ただ，GitHubは利用まですごくスムーズだったので期待！

ちまちまやれるので多少更新頻度が上がるかもしれません．ブランチとのmergeとかがうまく行けば，デザインの編集される方にも便利にならないかなとの試みもかねて．

ma38su / wp.vicuna.ext at master - GitHub

最近は，WEB系の人達だけじゃなくてあちこちでmemcachedを使ってるって聞く(もちろん，はてなでもよく聞く)ので，ちょっと調べてみたら結構面白かった．

なにがって，memcached本体は，ハッシュ的なkey, valueペアでデータをキャッシュしておけるただのデーモンなのだけれど，クライアント側に複数(サーバ)のmemcachedを教えておくと自動的にkeyのハッシュ値からデータを分散させて保存できたりするところ．本体に手を加えなくてもクライアント側で，機能拡張できるモデルっていうのは面白いなーと思った．

最近のクライアントの主流らしいlibmemcachedでは，Consistent Hashingに基づいて分散させるって聞くので，じゃぁフェイルオーバーも容易．．．だと思ったんだけど，ちょっと遊んでみたところ，簡単にそういうことができるわけではないみたい．（まぁ，Consistent Hashingを最大限に生かそうとすると本体にも手を加えないといけないから期待してなかったけど）研究室の計算機数台にインストールしてmemcachedを分散させてつかってみたけど，一台落とすと，結果が返ってこなくなるだけじゃなくて，保存もできないキーがあったりした．しかもどのキーかは一見わからないし．（今回Cから直接叩いたんだけど，PHPとかのライブラリだとフェイルオーバーするらしい，ほんとに？）

常駐するサーバ的なアプリとかならクライアント側アプリが直接複数のmemcachedを知っていて管理するべきなんだけど，（データベースに持たせてるとデータベースが落ちるとダメだから）普通のCGIやPHPとかだと，セッション毎にメモリが解放されちゃって管理できないからlibmemcachedでは対応してないのかな．

ちなみにAmazonのDynamoとか，楽天が作ってるROMAとか，MSR AsiaのBitVaultとかもConsistent Hashingで，脱マスター・スレーブモデルが最近の流行みたい．

Kansai.ARに参加してきました．若干迷って遅刻したり．．．

参加するといいつつ，遠いので実は結構家を出るのがおっくうだったのですが大変有意義でした．昔レンダラー書いて3D面白いなーと思ってたくらいの動機（あとスカウター）で，別にARとは無縁なのですが楽しめました．想像してなかったテレビ局の仕事の話とか，北京オリンピックの開会式もいえばARじゃないかみたいな話とか聞けたり，いろいろ面白かったです．

次はなにかしらアウトプットを出したいところです．

ありがとうございました．> 皆様

よその芝生はなんとやらとはいいますが，NAISTは楽しそうです．研究室選び失敗したかな．．．

実家の2Fで快適なネットとプリンターを共有できるようにしてくれといわれてて困っていたのだけど．AirMac Express 2台使ってやっと実現できた．

2Fは無線が安定していない状態なのだけど，そこにAirMacおいたら，安定してくれた．プリンターもBonjourで簡単に共有できた．Windows機の電源が入ってなくても印刷できるようになるのでいろいろうれしい(私のベッドのすぐそばに印刷のためのマシンがおいてあってうるさかった)

難点を挙げるとすれば，Windows機にBonjourにつなぐためにソフトが必要だということかな．

高速なTrie実装として知られているDouble ArrayをRubyで実装してみた。インターンで実装したハッシュのTrieとの速度を比較してみるとおもしろそう。配列しか使ってないし、1byte単位で枝葉を構成していくので、メモリ効率は確実にいいと思うんだけど。まだ改良の余地はいろいろとありますが。

#!/usr/bin/ruby

class Trie
	def encode(char)
		l = 0
		u = @code.length - 1
		while (l  char
				u = m - 1
			elsif @code[m] < char
				l = m + 1
			else
				return m + 1
			end
		end
		return -1
	end

	def initialize(file)
		@base = [1]
		@check = [0]
		@code = Array.new
		words = Array.new
		io = open(file)
		while line = io.gets
			line.chomp!
			words.push(line)
			line.each_byte {|c| @code[c] = c }
		end
		io.close
		words.sort!
		@code.compact!
		_search(0, 0, words.length, 0, words)
	end

	def match(word)
		check = 0
		base = @base[check]
		word.each_byte do |c|
			i = base + encode(c)
			if (@check[i] != check)
				break
			end
			base = @base[i]
			check = i
		end
		return @check[base] == check
	end

	def _search(i, l, u, parent, words)
		stack = Array.new
		tmp = Array.new
		sons = Array.new
		j = l
		p = nil
		while j < u
			word = words[j]
			if i  0)
			base = 0
			flag = 0
			begin
				base += 1
				tmp.each do |c|
					break if (@check[base + c] != nil)
					flag += 1
				end
			end while flag != tmp.length
			tmp.each do |c|
				@base[parent] = base
				son = base + c
				@check[son] = parent
				@base[son] = - 1 if c == 0
				sons.push(son)
			end
		end
		stack.push(j)
		l = stack.shift
		if stack.length > 0
			i += 1
			(stack.length).times do
				u = stack.shift
				son = sons.shift
				_search(i, l, u, son, words)
				l = u
			end
		end
	end
end

構築部分にバグがありそうな感じです。