最近ちょくちょくトライを使いたくなることがあるので、少しまとまったハッシュトライの実装を書いておく。 位置付け的には開発用。使用頻度が高いようなら、もう少しちゃんとしたものに書き直す。 ※ 2010/01/03: print-objectメソッド追加、common-prefix-s…

冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマ…

列の要素にキー関数を適用して、その結果が最大(or 最小)となる要素を返す、という関数。 loopマクロのmin/max辺りでやってくれるかなと思ったが、無理そうなので自作した。 マクロをふんだんに使用。 (defmacro find-xxx-helper (empty? first loop compare…

テキストおよびバイナリファイル読込み関数定義。 (defun read-binary-file (path) (with-open-file (in path :element-type '(unsigned-byte 8)) (let ((as (make-array (file-length in) :element-type '(unsigned-byte 8)))) (read-sequence as in) as)))…

仕事柄(かどうかは分からないが)switch分岐を多用したCやC++の文字列(群?)変換関数を書く機会がたまにある。 例えば最近では、Shift_JISの全角文字(カタカナ+記号)を半角文字に変換するCの関数を作成した(このRuby拡張ライブラリの中で使われている関数)。 …

前回の知見(文字コード変換関数をC++で用意する云々)を反映して、FFIを利用した、バイト列を文字列に変換するsbclのライブラリを作成した。 ・unsafe-conv(0.0.1) 対応している文字コードは、UTF-8、Shift_JIS、EUC-JPの三つ。UTF-8以外のC++の変換関数につ…

昨日作成したutf8-octets-to-string関数をclispでも試してみた。 ;;;; データ準備 ;; ファイルをバイト列として読み込む (defun read-octets-file (path) (with-open-file (in path :element-type '(unsigned-byte 8)) (let ((as (make-array (file-length i…

前々回に作成したURLデコード用の関数では、sb-ext:octets-to-string関数が処理のボトルネックとなっていた。 確かsbcl(1.0.28)はバイト列から文字列への変換には、UTF-8でもShift-JISでもEUC-JP(及びその他)でも出来るような汎用的な方法(枠組み?)*1を採用…

昨日の続き。 比較対象にC++とclojureを追加し、Javaのコードも若干変更した。下の三つが、それぞれのベンチマーク用のコード。(ベンチマーク用データは、前回と同様のものを使用する) 参照: mmap_t /** C++ **/ //////////////////////////// // ファイル名…

URLのエンコード/デコード処理は、時々必要になって、その度に(適当に)自作しているものの一つなので、今回少し真面目に作成してパッケージにまとめてみた。 仕様は『URLEncoder (Java Platform SE 6)』を参考にさせてもらった。 (defpackage :url (:use :co…

今日(昨日?)は、HTTPリクエストを並列化して大量のURLからのデータ取得を高速化する、というようなことを試していた。 並列化 初めは単純に、個々のHTTPリクエスト(URL)を別々のスレッドで処理すれば、(イメージ的には)総処理時間もO(1)*1に近いものになるの…

sbcl(1.0.28)で文字列のリストのユニークな要素を取ろうとすると、やけに遅い。 リストの要素数は30万くらいなのだが、しばらく待ってもレスポンスがない。 > (length *word-list*) ; *word-list*は文字列のリスト --> 320000 ; この数は適当 > (time (remov…

今日は、clojureからSQLServerに接続する機会があったので、メモとしてそのコードを残しておく。 まず、起動用のスクリプトを準備: #! /bin/sh # # ファイル名: clojure # clojure起動スクリプト # 引数には、クラスパスに追加するファイルリストを与える CL…

sbclのソースを読んでいたら、次のようなコードを目にした。 ;;; sbcl-1.0.29/src/code/seq.lispのlist-remove-duplicates*関数からの抜粋 (let* ((result (list '())) (splice result) (current list)) ; listは引数で渡されたリスト #|...|# (do (#|...|#)…

一つ前の記事では、以下のようなmaxf及びminfというマクロを定義して使っていた。 ;;; 定義 (defmacro maxf (a &rest as) `(setf ,a (max ,@as))) (defmacro minf (a &rest as) `(setf ,a (min ,@as))) ;;; 使用例 ;; 「aの値が20よりも小さい場合は、aの値…

本業の方が忙しくて、なかなかまとまったことをする時間がないので、軽いものを一つ。「Get a Rectangular Field」というパズルのような問題を解いてみる。 問題の説明等はここを参照。 途中経過とかは全て飛ばして、とりあえず最初に思いついた解答(を若干…

common lispでは、バイト配列型を(vector (unsigned-byte 8))と表す。 この型は個人的にはかなり使用頻度が高いのだが、見ての通り長くて打ちづらい。今まではその時々によって、上の型をそのまま使ったり、エイリアス型を定義して使ったりしていたのだが、…

Shift_JISの全角文字を半角文字に変換するrubyの拡張ライブラリを作成した。 中身は変換テーブル*1を用意してマッピングを行っているだけの単純なものだが、毎回一から作るのは若干面倒なので、まとめてここにおいておく(ruby/sjis_conv-0.1.0.tar.gz)。使え…

形態素解析器の４。 今回は未知語処理+αを扱う。 前回までで作成した形態素解析器では、下の例のように未知語が"_"と表示されてしまうが、これをちゃんと"ocaml"と表示されるようにするのが今回の主たる目的。 ;; 未知語=単語辞書に登録されていない語は、"_…

形態素解析器作成の３。 前回、形態素解析のステップを大まかに二つに分けた。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能なので、その全てのパターンを列挙する それらの分割にコスト(優先順位)を付与する。コスト…

先週のShibuya.lisp TT#4への参加をきっかけ*1に読み始めた『Programming Clojure』を一通り読み終えた。 今までは、JVM上の言語ということで何となく敬遠していたが、結構いろいろ面白そうな特徴があった。 とりあえず個人に良さそうだと思った点は以下の通…

sbcl(1.0.28)は、文字コード(external-format)に:shift-jisを指定することができない。 > (string-to-octets "あいうえお" :external-format :shift-jis) debugger invoked on a SIMPLE-ERROR in thread #<THREAD "initial thread" RUNNING {AB6E569}>: Unknown external-format :SHIFT-JIS ;; :shift_ji</thread>…

形態素解析器作成の２。前回で必要なデータの準備は終わったので、今回からは解析器の実装に入る。 この実装では、形態素解析はおおまかに次の二つの段階に分けられる。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能…

自分の環境では、sortコマンドを実行する時にLC_ALL環境変数に'C'をセットするかしないかで、処理終了までの時間が著しく変わる。 # 約40万行のデータ > wc -l words 392126 words # 入っているのはUTF-8の日本語(IPA辞書を利用) > head words やぼったい や…

以前に「DoubleArrayと辞書があれば、形態素解析器は案外簡単にできるのではないか」というようなことを書いた。 試してみたところ、実際に結構簡単に(ほぼ)MeCab互換の形態素解析器ができたので、それを何回かに分けて載せていくことにする。 作るもの 未知…

sbcl(1.0.28)では、実行可能ファイルを作成することができる。 > (sb-ext:save-lisp-and-die "実行可能ファイル名" :toplevel #'エントリ関数 :executable t) エントリ関数には(必須引数の数が0個なら?)どのような関数でも指定可能なのだが、いろいろクセが…

シェルスクリプトで、親が受け取った引数を、そのまま子コマンドに渡したい場合は、"$@"を使えばいいらしい。 #! /bin/sh # file: parent echo "== $0 ==" for a; do echo "arg: ${a}" done ./child "$@" ./child $@ #! /bin/sh # file: child echo "" echo …

今日試しに使ってみたら、VC++2005のstd::setとstdext::hash_setがやけに遅かった。doarのWindows対応も一通り終ったので、VC++の上記クラスと検索速度を比較してみたのだが、結果は以下のようになった。 doar# 1.875 sec ※ 数値は、32587100要素(325871*100…

正確にはpingではないけど、機能的には似てなくもないメソッド。 引数にuriにHEADコマンドを投げて、open_timeout時間内に接続できればtrueを返す。 uriが有効(安全に読み込める)かどうかを知りたいときに便利。 同様の機能の既存のメソッドがあるかもしれな…

前に少しDoubleArrayの動的追加時(のx-check関数で空き領域を探す際)に乱数を使えば処理速度を大幅に改善できるのでは、というようなことを書いた。 この方法だとメモリ使用量は結構増える(まだ正確には把握していない)が、確かに処理速度は大きく向上する。…