Programming Archive

高速な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

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

id:ma38su

最近、sourceforge.jpにアクセス拒否されてるみたい。困った困った。

ASにもJavaのコレクションフレームワークみたいなのを実装してくれないものかなと思いつつ気分転換に書いてたのをせっかくなので晒す。

package org.ma38su.util
{
	/**
	 * ヒープを実装したクラスです。
	 * コンストラクタに比較関数を定義することで、自由に要素の順序を定義することができます。
	 * 比較関数の引数は2、戻り値は、intでもNumberでも比較できる型であればかまいません。
	 * 比較関数の戻り値が0のとき、要素は等しいと判断され、
	 * 0より大きいとき、1番目の引数よりも、2番目の引数が小さいとされ、
	 * 0より大きいとき、1番目の引数よりも、2番目の引数が大きいとされます。
         * @author ma38su
	 */
	public class Heap
	{
		/**
		 * ソートされるオブジェクト
		 */
		private var entries:Array;

		/**
		 * 要素間の比較をする関数
		 */
		private var comparator:Function;

		/**
		 * ヒープのコンストラクタ
		 * @param comparator 比較関数
		 */
		public function Heap(compareFunction:Function=null) {
			entries = new Array();
			entries.push(null);
			this.comparator = compareFunction;
		}

		/**
		 * @param entry 挿入する要素
		 */
		public function add(entry:Object):void {
			entries.push(entry);
			fixUp(entries.length - 1);
		}

		/**
		 * 入れ替える
		 * @param index1
		 * @param index2
		 */
		private function swap(index1:uint, index2:uint):void {
			var tmp:Object = entries[index1];
			entries[index1] = entries[index2];
			entries[index2] = tmp;
		}

		/**
		 * ヒープの先頭（根）の要素を削除して取り出す
		 * @return ヒープの先頭の要素
		 */
		public function poll():Object {
			if (entries.size == 0) {
				return null;
			}
			var entry:Object = entries[1];
			if (entries.length > 2) {
				entries[1] = entries.pop();
			} else if (entries.length == 2){
				entries.pop();
			}
			if (entries.length > 2) {
				fixDown(1);
			}
			return entry;
		}

		/**
		 * 削除せずにヒープの先頭（根）の要素を取り出す
		 * @return ヒープの先頭の要素
		 */
		public function peek():Object {
			return entries[1];
		}

		/**
		 * 子との状態の比較、必要に応じて移動
		 * @param index 比較する要素の添字
		 */
		private function fixDown(index:uint):void {
			var son:uint;
			while ((son = index << 1) < entries.length) {
				var nson:uint = son + 1;
				if (comparator ==  null) {
					if (nson  entries[nson]) {
						son = nson;
					}
					if (entries[index] <= entries[son]) {
						break;
					}
				} else {
					if (nson  0) {
						son = nson;
					}
					if (comparator.call(null, entries[index], entries[son]) > 1) > 0) {
				if (comparator == null) {
					if (entries[index] >= entries[parent]) {
						break;
					}
				} else {
					if (comparator.call(null, entries[index], entries[parent]) >= 0) {
						break;
					}
				}
				swap(index, parent);
				index = parent;
			}
		}

		/**
		 * ヒープが空かどうかの確認
		 * @return ヒープに空ならtrueを返す
		 */
		public function isEmpty():Boolean {
			return entries.length <= 1;
		}

		/**
		 * ヒープの要素数を返す関数
		 * @return ヒープの要素数
		 */
		public function size():uint {
			return entries.length - 1;
		}
	}
}

あー、一応ラクダの本とか、アルパカの本とかもちょこちょこ目を通してますよ。

JavaのKD-treeをActionScriptに書き直して、k近傍探索を実装してみた。

Continue reading

見直すと結構無駄があったので、Rubyの練習をかねてGCJ2008のQualification Roundを改めて解いてみる。実行時間を犠牲にしてもコードは短く書いてる。Ruby使ってみるかなとか思ってたけど、比較してみるとさほどありがたいものではなかった。Pythonも試してみるかな。

問題Cはなんかうまくいかない。あきらめて強引に積分しようとしたけど、答えは合わず。。。

Continue reading

Congratulations! The results of the Google Code Jam 2008 Qualification Round are now official, and we’re happy to announce that you have advanced to Round 1.

というメールが来てました、そういうことらしいです。足切りレベルと判定されたらさすがに凹むし。ひねりはなかったとか書いたけど、3000位強と不甲斐ない。次もこれだと落選ですorz

ただ、いまさら、ちゃんと調べてみたら、Round 2以降の日程が微妙ですね。まぁ、通過してから考えよう。すぐ落選の報告をするのもいやなので、ちっとは練習したりまじめに望もうかな。