最近ちょくちょくトライを使いたくなることがあるので、少しまとまったハッシュトライの実装を書いておく。 位置付け的には開発用。使用頻度が高いようなら、もう少しちゃんとしたものに書き直す。 ※ 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」というパズルのような問題を解いてみる。 問題の説明等はここを参照。 途中経過とかは全て飛ばして、とりあえず最初に思いついた解答(を若干…