マルチキークイックソートとstd::sortの比較

C++ algorithm speed

以前にCommon Lispで実装したマルチキークイックソートをC++で書き直して、STLのstd::sortと速度を比較してみた。使用データ Wikipediaの記事タイトル約500万行を使用。データ作成方法などはここを参照。 $ wc -l wiki.title.500 5340378 wiki.title.500 $…

2010-10-26

DAWG2(2.5): DAWG構築時のハッシュ値用の領域節約

sbcl C++ algorithm

前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。 ;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sib…

2010-10-24

erlterm: Erlang項とCommon Lispオブジェクトの相互変換

common lisp Erlang library

Erlang -- External Term Formatを参考にして、Erlangの項(のバイナリ表現)とCommon Lispのオブジェクトを相互変換するライブラリを作成。・erlterm-0.0.1 ポートを用いた外部接続での利用を想定。細かい作り込みや最適化はまだまだだけど、一応一通りの変…

2010-10-23

浮動小数点数のIEEE754形式への変換

common lisp utility

倍精度浮動小数点数をIEEE754形式のビット表現(整数値)にエンコードする方法。 (defun encode-double-float (float) (declare (double-float float)) (multiple-value-bind (fraction exponent sign) (integer-decode-float float) (let ((code 0)) (setf (l…

2010-10-22

Igo: GAE版をgithubに

Java

Igo: GoogleAppEngineで形態素解析サーバとIgo: JavaScriptで形態素解析で書いた内容を少し整理してgithubにソース一式を登録。・igo-gae現状は本当にただ必要な分だけを修正して、とりあえずGAE上で動かしているだけだけど、その内にもっとちゃんとしたも…

2010-10-21

llvm: ビットコードのデコード

llvm common lisp

LLVM Bitcode File Format — LLVM 3.4 documentationを読んでllvmのビットコードをデコード(パース)してみたので、そのメモ(あくまでも個人用メモ。用語とかは結構自分の好き勝手に書いているので、ちゃんと知りたい人はオリジナルのドキュメントを参照のこ…

2010-10-18

Igo: JavaScriptで形態素解析

Java JavaScript utility

Igo: GoogleAppEngineで形態素解析サーバで用意したサーバ(※追加修正あり。後述)を使って形態素解析を行うJavaScriptを書いてみた。制限結構制限が多い。対応がUTF-8のみレスポンスのJSONに含まれる文字列内のASCII以外の文字を16進数表記(\uXXXX)にエス…

2010-10-15

DAWG2(2): ソート済みファイルからのDAWG構築

common lisp sbcl algorithm speed

前回はトライだったけど、今回はDAWGを構築。 Nをキーセットに含まれる文字の総数*1だとして、DAWGはトライと同様にO(N)で構築可能(多分間違っていないはず...)。ただし、子ノード(サブトライ)が共有可能かどうかの判定が入るので、実際には一桁程度遅くな…

2010-10-14

DAWG2(1): ソート済みファイルからのトライ構築

common lisp sbcl algorithm

七月にやっていたDAWG(Direct Acyclic Word Graph)シリーズ(?)の続き。結構長い間中断していて自分でも内容がうろ覚えなので、仕切り直してもう一度。今回はDAWGの前段階として、ソート済み(かつ各行がユニーク)なファイルからトライを構築する。 DAWG 軽…

2010-10-11

dict: ハッシュテーブル

common lisp algorithm library

前回にErlangで作成したhashtrieをcommon lispに移植していたら、いつのまにかただのハッシュテーブルになっていた。もともとはHAMTから始まったはずなのに...。ソースコード等: dict-0.0.1 実装キー衝突時にAMTを使わないで、リンクリストを使うHAMT。初…

2010-10-08

HAMT(もどき): Erlangへの応用

Erlang algorithm library speed

最近Erlang本を読んでいる関係もあってこことここで書いているHAMT(Hash Array Mapped Try)のErlangへの応用を試していた。 immutableでpersistentなハッシュマップをHAMTで効率的に実装できないかと。その成果物: hashtrie-0.0.3 HAMT? hashtrieを作ったも…

2010-10-06

Igo: GoogleAppEngineで形態素解析サーバ

Java

IgoをGoogleAppEngine上で動かしてみた。 URL URLと仕様。トップ: http://igo-morp.appspot.com/ 形態素解析: http://igo-morp.appspot.com/parse 'text'パラメータに入力テキスト*1をセットしてリクエスト(POST or GET)を投げると、形態素解析結果がUTF-8…