Home > Software Archive

Software Archive

Double Array

高速な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 < 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 }
		end
		io.close
		words.sort!
		@code.compact!
		_search(0, 0, words.length, 0, words)
	end

	def match(word)
		check = 0
		base = @base
		word.each_byte do |c|
			i = base + encode(c)
			if (@check != check)
				break
			end
			base = @base
			check = i
		end
		return @check == 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
			if i  0)
			base = 0
			flag = 0
			begin
				base += 1
				tmp.each do |c|
					break if (@check != nil)
					flag += 1
				end
			end while flag != tmp.length
			tmp.each do |c|
				@base
 = base
				son = base + c
				@check = parent
				@base = - 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

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

TeXのためのMakefile

Previewだと，pdfでもxdviと同じように一度開いたファイルを自動更新してくれるので，pdfまで変換してしまうのもありかと思ってTeXのためのMakefileを書いた．

追記
依存関係を抽出するdep.plを書いたので，普通はDOCとBIBを設定すれば使えると思う．

DOC     = paper    # メインのTeXファイル名(拡張子不要)
BIB     = ref.bib  # BibTeXファイル名（拡張子必須）
SOURECE = $(shell perl dep.pl $(DOC).tex)

LATEX   = platex
DVIPDFM = dvipdfmx
BIBTEX  = jbibtex
RM      = rm
.SUFFIXES: .tex .dvi .pdf

$(DOC).dvi: $(DOC).aux $(DOC).bbl $(SOURECE)
	$(LATEX) $(DOC)
	$(LATEX) $(DOC)

.dvi.pdf: $(DOC).dvi
	$(DVIPDFM) $<

$(DOC).aux: $(DOC).tex
	$(LATEX) $(DOC)

$(DOC).bbl: $(DOC).tex $(BIB)
	$(BIBTEX) $(DOC)

pdf: $(DOC).pdf

clean:
	$(RM) -f $(DOC).dvi $(DOC).toc $(DOC).aux $(DOC).blg $(DOC).bbl $(DOC).log $(DOC).pdf *~

dep.pl : 依存関係を抽出するためのスクリプト

use strict;
use warnings;

parse_tex($ARGV<0>);

sub parse_tex {
	my ($file) = @_;
	my $fp;
	open($fp, $file) or die "IOError: ". $file;
	while () {
		chomp;
		if (/^<^%>*<\\¥>includegraphics\*?(?:\<[^\[\>]+\])?\{(<^\{\}>+)\}/o) {
			printf("%s ", $1);
		} elsif (/^<^%>*\\input{(<^\{\}>+)}/) {
			my $texfile = sprintf("%s.tex ", $1);
			parse_tex($texfile);
			printf("%s ", $texfile);
		}
	}
	close($fp);
}

exit(0);

あんまり賢くないけど、これで大体の画像ファイルなんかの依存関係も把握できるんじゃないかな．

Google東京オフィスにお邪魔させてもらった。

先週月曜のデベロッパー交流会は、たまたま都合が合ったので参加したのだけど、そこで金曜日のGoogle Maps API Hackathonも人数的に余裕があると聞きつけて勢いで参加してきた。金曜日まで一部ネットカフェ難民してた。そんなわけで東京オフィスに御邪魔させていただいた。

ハッカソンは勢いだけに任せて参加してこともあって、不慣れなJavascriptが不安だったけどid:secondlifeさんの講義を受けたとこなのでjavascriptは結構なんとかなった。でもAPIもクラシックなとこしか使わなくて、Googleオフィスでコーディングさせてもらうっていうメリットを全然生かせてない、ちょっともったいなかった。

オフィスランチをいただいて、Google Tシャツとかもらった。オフィスを少しみせてもらって、アンドロイドフォンまで触らせてもらったよ。Googleのパメラさんとか参加者のひととカラオケに行ったり。(夜行バスの時間とか野都合で途中で抜けさせてもらったけど)

せっかくなので、ちょこっとはてなとグーグルについて比較してみる。Googleははてなっぽいと思った。逆なのかもしれないけど、はてなを先にみてるからそうなった。Googleは本当の意味でグローバルで、そこらへんは日本の会社とはだいぶ違うけど、あんまりベンチャーっぽさはないかもなぁと感じた（ベンチャーとかいう言葉でお茶を濁すけど）。オフィスはほんの少し見学させてもらっただけなので、ほとんど何も分からないけどね。

Google東京オフィスのランチはビッフェ的な感じで品数が多かった。id:r_kurainみたいに食べられないものが多い人にはいいかも。はてなはみんなでご飯みたいな感じがよかったけど、Googleは意外と普通の食堂という感じだったかな。ご飯は、どっちもすごく美味しかったけどね。イメージわかない人はZDNetとかの写真をみてください。

ひがやすを飲み会も少なかったけど、今回は学生が僕だけでしたよ。もうちょっといた方がねぇ。

Vimの環境設定

$ sudo port install vim

http://www.vim.org/scripts/script.php?script_id=1585
=> ~/.vim/syntax/actionscript.vim

http://www.vim.org/scripts/script.php?script_id=1879
=> ~/.vim/plugin/autocomplpop.vim
autocomplpop - vimグループ

http://subtech.g.hatena.ne.jp/secondlife/20070211/1171123374
=> ~/.vim/dict/actionscript3.dict

あとは、必要に応じて足りないものを足す。
>|
$ sudo gem install rascut -y
$ sudo gem install mongrel -y
$ sudo gem install json -y
|<

svn://rubyforge.org/var/svn/hotchpotch/rascut/trunk
gemでもrascutはインストールできるけど、-sオプションがつけると正常に動作しない。（Macだけかも）
なのでsvnからインストールする。とりあえず動くはず。

あとは、xmlを監視しないみたいなので、監視するようにlib/rascut/config.rbを一部改変した。
Leopardでは、gemと、rubyのPATHが中途半端にMacPortsのものになってたりしないか気をつける。

vimperatorででエスケープできないので，でエスケープできるようにした．(google suggestとかjavascript連中はうまく行かないけど．)
慣れると結構楽なので，vimでも同様にした．

>||
vim -p *.cpp *.h
||<
のようにすれば，必要なファイルをタブで全部開ける．

多分、追記してく。

Hatena::WordPress::Adaptor ver.0.2

WordPressからはてなへIDトラックバックするプラグインをつくりました。（id:smlyには、くだらんとかいわれながら。。。）

インターンに参加してから、idトラックバック打ちまくったり、スターをぽちぽち押すようになったので、WordPressで使えないのは不便だなーと思って。（ちなみに、第2回インターン参加者のうち、日頃、はてな以外でブログを書いてるのは僕だけのようで。。。）

はてなインターンのまとめを書いてたら、いろいろバグが見つかったので修正しました．

Hatena::WordPress::Adaptor ver.0.2

Home > Software Archive

Return to page top