Etsukata blog: Haskellでlist monadを使ってN-Queens問題を解いてみました を見たのをきっかけに久しぶりにN-Queen問題を解くプログラムをHaskellで書いてみた。 ---- ファイル名: nqueen.hs ---- コンパイル: ghc -O2 -o nqueen nqueen.hs # Glasgow Haske…

割合汎用的な、整数のビットを前後反転する関数を作成してみた。 2の乗数サイズの任意の整数型のビット反転が可能。 // 反転例 bit_reverse(0x0000FFFF) => 0xFFFF0000 // 実装 // バイト単位での変換表 const unsigned char REV_BYTE[]={ 0,128,64,192,32,1…

ハッシュテーブルを実装してみた。 ・cc-dict-0.0.3 チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。 ベンチマーク 一応、ベンチマークも取…

g++(及びその他)のunordered_mapで文字列をキーにしたい場合の注意書き。 unordered_mapのようにconst char*を指定すると、キーが文字列ではなくポインタ(整数値)として解釈されてしまう*1。 以下、その際の挙動の確認用のコード: /** * ファイル名: str_map…

構造体やクラスのインスタンスの特定のフィールドのアドレス(ポインタ)だけ分かっている場合に、そこからオブジェクト全体のポインタを取得したい場合に使うマクロ。 やっていることは単にフィールドのアドレスから、そのフィールドの(クラスor構造体の)先頭…

Sanmoku(0.0.4): 辞書データサイズ縮小のコメントにて要望があったのでSanmokuを形態素の原型や読みの情報取得に対応させてみた。 Sanmoku本体のインターフェースは以前の同様*1で、原型・読み・発音の取得を行うためのFeatureExクラス(sanmoku-feature-ex-x…

今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。 大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。 もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共…

この一週間でSanmokuの辞書データサイズの縮小をいろいろ試していたので、その結果を載せておく。 現時点でのバージョンは 0.0.4。 やったこと 試した主なこと。 データ 内容 サイズ(Gomoku-0.0.4 => Sanmoku-0.0.4) 連接コストデータ(matrix.bin) 類似品詞…

GomokuをベースにしたSanmokuという形態素解析器を実装した。 Gomokuに比べて解析時に必要なメモリ量が少ないのと初期ロード時間が短いのが特徴。 将来的には解析精度を若干落として、辞書サイズ*1をさらに削減する可能性もあるけど、現状は解析結果はGomoku…

マージソート(1)の改良版。 ソートのような高階関数では、引数で渡した比較関数の間接呼び出しのコストも実行速度にそれなりの影響を与えるので、それを(マクロをほとんど使わずに)できるだけ低く抑えるための試み。 比較関数最適化 まず、比較関数自体の実…

昨日に作成したマージソートに手を加えたもの。 要素数が少ない部分リスト*1には、(再帰的な)マージソートではなく、ソーティングネットワーク的なソートを適用することで高速化を図った。 けど、結果的にはほとんど効果がなかった。 計時 まず計測結果から…

久々にマージソートを実装してみたら、結構良いものができたので載せておく。 まずはパッケージ定義とグルーバルな宣言。 ;;;; SBCL-1.0.51 (x86-64) (defpackage merge-sort (:use common-lisp) (:shadow :common-lisp sort) (:export sort)) (in-package :…

以下、sbcl-1.0.51-x86-64-linuxでの実行結果。 ;; 計時用関数 (defun compare-time (fn nums1 nums2) (declare (optimize (speed 3) (safety 0) (debug 0)) (function fn)) (time (loop FOR n1 fixnum IN nums1 FOR n2 fixnum IN nums2 WHEN (funcall fn n1…

sb-alienパッケージとかを使ってネイティブライブラリを使用していると、ちょくちょくCの定数の値や型の定義(型のサイズ)を知りたくなることがある。 毎回ヘッダファイルを調べるのも面倒なので、lisp上から取得出来るように関数を用意してみた。 (defun c-i…

Forthでハノイの塔 - sileの日記でハノイの塔を解くcommon lispプログラムを載せたら「inline宣言を付けるともっと早くなりますよ」というコメントを頂いたので試してみた。 inline宣言付与結果 再帰関数をinline展開する際の深さはsb-ext:*inline-expansion…

Forthを触ってみたくなったので、試しにハノイの塔を実装してみた。 ついでにcommon lispとC++でも実装し、Forthとの処理速度を比較してみた。 ※ common lispの処理系にはSBCLを、Forthの処理系にはgforth及びVFX-Forthを使用した Forthでの実装(gforth) gfo…

前半および後半で実装を省略していたパッケージのソースコードをここに載せておく。 buffered-outputパッケージとnode-allocatorパッケージの二つ。 buffered-output ランダムアクセス可能なバイナリファイル出力用のパッケージ。 DoubleArray構築時に使われ…

昨日の続き。 今回は主に、前回のtrieパッケージでは未定義だったchange-active-node関数を埋めていくことになる。 ※ ちなみに今回は'後半'となっているけど、まだ後続がある・・・。詳しくはソースコード内のコメントを参照。 実装: DoubleArray構築パッケ…

タイトル通りのパッケージ。 実装の前に使用例。 ;;;; sbcl-1.0.49 ;; 例で使用する文字列(および対応するバイト列) (sb-ext:string-to-octets "下書き") --> #(228 184 139 230 155 184 227 129 141) ;; 作成 (defparameter *in* (octet-stream:make "下書…

格納するキー数に大してO(1)のメモリ使用量で、DoubleArrayを構築する方法を思いついたので、その実装メモ。 今回はその前半。 いきなりDoubleArrayの実装を行うとやや複雑となるので、まずはより単純な通常のトライ(オンメモリ)の実装から始める。 基本的な…

後々使いたいので、簡単なカウントダウンラッチを作成してみた。 ウェイトは単純なスピンで実装しているのであまり実用的ではないけど、お試し用途であれば十分(だと思う)。 (defpackage countdown-latch (:use :common-lisp) (:export make countdown-and-a…

実行中のスレッドがN個あるとして、そのそれぞれに0からN-1のID値を割り振る関数を作成した。 (defpackage thread-id (:use :common-lisp) (:shadow :common-lisp get) (:export get)) (in-package :thread-id) (define-symbol-macro *id* (tls:symbol-value…

Igo-0.4.3: 若干のパフォーマンス向上 - sileの日記の続き。 Gomoku(0.0.4)では辞書引き部分*1にDAWGを使っているので、それもIgoに取り込んで処理速度の変化を図ってみた。 比較 諸々の条件は前回と同様。 今回は新たにIgoのDAWG版が加わる。 総処理時間(1)…

Gomoku(0.0.4)で得た知見の一部をIgo(0.4.3)に取り込んでみた。 形態素解析の部分が少し速くなっている。 比較 MeCab(0.98)、Gomoku(0.0.4)、Igo(0.4.2,0.4.3)の処理速度の比較*1。 以前とはマシンも変わっているので、全部計り直した。 計時には約80MBの日…

SBCLの出力をパイプして使う場合の注意点。 何も気にせずに書いていると大量のエラー情報が出力されて戸惑うことがある。 例として以下のSBCLスクリプトを用いる。 ;;;; ファイル名: loop.lisp ;;;; sbcl-1.0.48 (loop FOR n FROM 0 DO (format t "loop: ~a~…

ジェネレータを使ったループっぽいものをcommon lispで実装してみた。 実装は適当で制限も多いけど、処理効率は(通常のループと同程度に)良い。まず動作例。 ;; 1: ".profile"の各行を出力する (for (x (each-line ".profile")) (print x)) "# ~/.profile: e…

マシンのネイティブのバイトオーダーを自動的に判定できるユーティリティ関数があると便利かと思ったので作成してみた。 ;# <- バイトオーダー判定用文字列 ;; ファイル名: byte-order.lisp (defun guess-byte-order (sample-file) (with-open-file (1byte s…

igo-gaeを修正して、辞書データ読み込みを速度を向上させた。 ※ igo-gaeの現在のバージョンは0.0.2。 修正内容概要 オリジナルのIgoでは、データ読み込みにはnio系パッケージのjava.nio.channels.FileChannelとjava.nio.MappedByteBufferを使っていた。 // M…

SBCLでnon-blocking I/Oを使いたくなったので少し調べてみた。serve-eventというものが利用可能らしい。 SBCL自体のマニュアルにはこれに関数詳しい説明はなく、CMUCLのドキュメント(CMUCL User's Manual: Event Dispatching with SERVE-EVENT)を参照する必…

『Pearls of Functional Algorithm Design』の15章「All the common prefixes」に目が止まったので、その要件を満たすものをcommon lispで実装してみたメモ(かなり雑)。以下、15章の冒頭から引用した「All the common prefixes」の概要。 Let llcp xs ys den…