2010-10-01から1ヶ月間の記事一覧

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

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

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

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

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

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

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

倍精度浮動小数点数を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…

Igo: GAE版をgithubに

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

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

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

Igo: JavaScriptで形態素解析

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

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

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

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

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

dict: ハッシュテーブル

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

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

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

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

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

マルチキークイックソート

「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも…