RustでMD5ハッシュを計算する

別に難しくはないけど、いざ使いたいという時に方法を忘れてしまっており、何度か調べ直しているのでメモに残しておく。 以下のようにrust-cryptoを使えば実現可能。 サンプルプロジェクトの準備: $ rustc -V rustc 1.9.0 (e4e8b6668 2016-05-18) $ cargo ne…

RustとSBCLでのDAWG構築性能の比較メモ

Rustの勉強を兼ねて、cl-dawgというDAWGのCommon Lisp実装を移植して、rust-dawgというライブラリを作ってみた。 (DAWGは末尾部分を共有可能にしたトライの亜種。上記ライブラリでは、そのトライ木をDoubleArray形式で表現している。DAWGやDoubleArrayの構築…

Emacsのファイル保存時に自動的にrustfmtが適用されるようにする

コードフォーマッタによる整形がファイル保存時に自動で行われるようにするための手順メモ。 まずはrustfmtをインストール: # バージョン $ rustc -V rustc 1.5.0 (3d7cd77e4 2015-12-04) # インストール $ cargo install rustfmt $ export PATH=$PATH:$HOME…

現在時刻をUNIXタイムスタンプ形式で取得する

chronoというライブラリを使えば出来そう。 $ cargo new sample --bin $ cd sample $ echo -e '\n[dependencies]\nchrono="*"\n' >> Cargo.toml main.rsを修正: // src/main.rs extern crate chrono; use chrono::offset::local::Local; use chrono::duratio…

loglevelとseverityの使い分けメモ

自分用のログレベル関連の用語整理メモ。 loglevel、severity、severity level、をどう使い分けるか。 ここに書いてあることが一般的に正しい使い分けかどうかは不明。 severity は、その名の通りログメッセージの深刻度を表す。 その数値表現が severity le…

特定オプション指定時にdialyzerのメモリ消費量が異様に大きくなる

--get_warningsと-Wrace_conditionsの二つのオプションを合わせて指定すると、何故かメモリ使用量が大きくなってしまう模様。 例えば、以下のコマンド実行時には、メモリ使用量が途中で8GB(RAMサイズ)に達してしまい、PLTを構築することができなかった。 (上…

素数列生成

素数列の実装方法を考えてみたのでメモ。 基本的にはエラトステネスの篩と同じようなことを行っているはずだが、一度に保持する篩の範囲が(おそらく)必要最小限となっている。 (一つの既知の素数につき、ハッシュテーブル内の一つの枠しか消費しない) // fil…

Rustで関数型っぽい見た目のペアリングヒープを実装

Rustでペアリングヒープを実装してみたのでコードをメモとして残しておく。 無駄に関数型っぽい見た目の実装(selfを使わずに更新結果を戻り値で返す)となっている。 最低限のテストは書いたが正しく動作するかどうかは自信がない。 効率周りも無頓着。 // $ …

yumのパッケージ(rpm)をダウンロードする方法

yumdownloaderというコマンドを使えば、インストールは行わずにパッケージのrpmだけを取得できる模様。 # yumdownloaderのインストール $ sudo yum install yum-utils # vimのrpmを取得 $ yumdownloader vim Loaded plugins: fastestmirror Loading mirror s…

優先度付きキュー系モジュールのベンチマーク

『Purely Functional Data Structures』(略:PFDS)で紹介されている優先度付きキュー(+ α)をいくつか実装してみたので、その性能測定メモ。 なおPFDSは(データ構造がヒープ特性を満たしているかどうかに関係なく)優先度付きキュー群をまとめてヒープと呼称し…

ErlangでUNIXドメインソケットのクライアント接続を行なう簡単な方法

Erlang(OTP-17.3)では標準でUNIXドメインソケットをサポートされておらず、ちゃんと使おうとすると外部ライブラリが必要だったり、自前でポートドライバを書く必要があったりして、結構面倒。 ただ、特に性能等を気にせず簡単に使いたいだけなら、ncコマンド…

マップ系モジュールのベンチマーク

最近、かなり以前に作成したErlangのハッシュマップ的なライブラリ(hashtrie)のrebar対応等を行う機会があったので、ついでにErlangでマップ的な処理を行うために使えるデータ構造(モジュール)群の性能測定をしてみた。 対象モジュール dict gb_trees array …

マルチプロセスで使用可能なロックフリーキュー

タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。 作成物 github: ipc-msgque (0.0.4) ロックフリーなFIFOキュー 再入可能 かつ SIGKILLに対して安全*1 C++ 共有メモリ(mmap)を使用 マルチプロセス(and…

ソート済みのリストに対する破壊的マージソートの改良

以前に載せたマージソート(をベースとしたもの)をSBCL(1.0.58)にコミットしてくれたPaul Khuongさんが、こんな記事を書いていて、なるほどなー、と思ったので、表題に関係する部分を参考にさせて貰って変更前後での比較を行ったメモ。 オリジナルのマージソ…

Lock-Free Queue

compare-and-swap操作を用いたロックフリーなキューの実装。 SBCLでのみ動作*1。 (defpackage lock-free-queue (:use :common-lisp) (:export queue make enq deq empty-p element-count to-list)) (in-package :lock-free-queue) ;; compare-and-swap: 成功…

複数プロセスで共有しているmutexのロック中にSIGKILLを投げたらどうなるか

C++

結論: デッドロックになってしまう 自動的にロックを解放してくれたりはしないみたい。 以下、試した内容のメモ書き。 環境 $ cat /proc/version Linux version 3.0.0-23-generic (buildd@komainu) (gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3) ) #38…

エラトステネスの篩

loop*1を使って、エラトステネスの篩を実装してみたメモ。 以下、処理系にはSBCLのver1.0.54(x86-64bit)を使用。 ;; 引数nまでの範囲の素数のシーケンス(ジェネレータ)を作成する (declaim (inline make-prime-sequence)) (defun make-prime-sequence (n) (l…

ループ処理を関数型っぽく書いてみる(2)

前回の続き。 githubにあるloopの簡易版を載せておく。 基本的な考え方 基本的なJava等のIteratorと似た*1インタフェースを通してループ処理を実現している。 異なるのは全ての関数をinline展開可能にすることで、同等のループを非関数型的に書いた場合と同…

ループ処理を関数型っぽく書いてみる(1)

今週は、common lispでループ処理を関数型っぽく、かつ効率良く実装できるかどうかを試していたので、その結果を載せておく。 結論から云えば、処理系の十分な最適化を期待できれば、関数型っぽく書いても、手続き型的に書いた場合と比肩しえる性能が得られ…

逆FizzBuzz

逆FizzBuzz問題 (Inverse FizzBuzz)というものがあるのを知ったので解いてみた。 結構力技。 あと、本当に合っているかは不明。 ;; 逆FizzBuzzを解く関数 ;; listは fizz,buzz,fizzbuzz のいずれかを要素に持つリスト ;; ;; 処理内容は、 ;; - 1: 開始数値を…

Gomokuの形態素解析部をScalaで実装してみた

ここ数日はScalaのコップ本を読んでいて、何かまとまったプログラムをScalaで書いてみたくなったのでGomoku(Java形態素解析器。ver0.0.6)をScalaで実装してみた*1。 ・github: scala-gomoku(ver0.0.1)以下、使用例とJava版/Scala版の簡単な比較メモ。 使用例…

簡易スタック型VM(JITコンパイラもどき)でのフィボナッチ数計算速度

前々々回でスタック型言語をバイトコードにコンパイルする部分を、前々回でCommonLispアセンブラによるマシン語生成を、前回でそのアセンブラ上にスタック型言語のラップするところを扱った。 今回はそれらをまとめて、最初に作成したバイトコードインタプリ…

CommonLispアセンブラ上にスタック型言語(っぽいもの)

前回のCommonLispアセンブラを使って、アセンブラ上に簡単なスタック型言語(っぽいもの)を組み立てて、それを使ってフィボナッチ数を計算するプログラムを書くと、どのような感じになるかを試してみた。 cl-asmはバージョンを更新して0.0.2を使用*1。 0.0.1(…

アセンブリ言語でフィボナッチ数

前回は、C++で単純なVMを書いて、その上でのフィボナッチ数の計算時間を測定した。 そのVM部分をネイティブコードに置き換えたら、どの程度処理速度が改善するのかを測ってみたかったので、その前にまずネイティブコード(x86)の勉強も兼ねて、common lispで…

簡易スタック型VM(バイトコードインタプリタ)でのフィボナッチ数計算速度

今年はlisp系のプログラミング言語(及びその処理系)を作ってみようと考えていて、かつ(少なくとも)当面の間はスタック型VMを基盤として実装していくことになると思われるので、まずは単純なスタックマシンのバイトコードインタプリタで、どの程度の処理速度…

fletとlabels

CommonLispのfletとlabels的なものを(あらかじめ使えるものはlambdaしかない状況で)自分で実装する必要が出てきたので、その際のメモ。 なお、以下では煩雑になるためfuncall呼び出しの記述を省略している(実際にはScheme処理系で動作確認を行っていた)。 le…

マインスイーパー

端末上で動作するマインスイーパーをCommonLisp(SBCL)で実装してみた。 github: cl-mine-0.0.2 端末操作 端末操作部分のソースコードは以下のような感じ。 基本的には端末のエスケープシーケンスで(カーソル移動や画面クリア、文字色等の)制御を行っている。…

N-Queen: 高速化

こちらの記事に刺激を受けて、以前に実装したN-Queenを高速化してみた(Common Lisp版のみ)。 (defvar *fastest* '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))) (deftype max-board-size () '(mod #x100)) (declaim (inline check)) ; …

erl-creole: ユニコード文字列とマルチバイト列の変換ライブラリ

少し必要になったのでErlangでユニコード文字列と各種エンコーディングのマルチバイト列(バイナリ)の相互変換を行うモジュールを作成した。 github: erl-creole-0.0.1 現状、対応しているエンコーディングは以下の通り*1: UTF-8, Shift_JIS, CP932, EUC-JP, …

文字列/バイト列用のハッシュ関数ライブラリ

A Hash Function for Hash Table Lookupに載っているハッシュ関数(Jenkins Hash)をCommon Lispで実装した。 github: jenkins-hash(0.0.2) 作成の主な動機は以下の二つ: SBCLにはバイト列用のハッシュ関数がない *1 一つのキーから複数のハッシュ値を得たい場…

N-Queen (Haskell + Common Lisp)

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: ハッシュテーブル

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

std::tr1::unordered_mapのキーの型をconst char*にした場合の挙動

C++

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

フィールドのポインタから、オブジェクト全体のポインタを取得するためのマクロ

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

Sanmoku(0.0.5): 原型や読みの情報取得に対応

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

UNF-0.0.4: サイズ削減

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

Sanmoku(0.0.4): 辞書データサイズ縮小

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

Sanmoku: 省メモリな形態素解析器

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

マージソート(3): 高階関数呼び出し最適化

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

マージソート(2): 要素数が少ない部分リストの特別扱い

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

マージソート(1)

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

=関数よりもeql関数の方が速かった(間接呼び出し時)

以下、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…

Cの定数値や型のサイズを取得するための関数

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

再帰関数(ハノイの塔)にinline宣言をつけたら・・・

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

Forthでハノイの塔

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

ソート済みファイルからO(1)のメモリ使用量でDoubleArrayを構築する方法 #APPENDIX

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

ソート済みファイルからO(1)のメモリ使用量で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を構築する方法 #前半

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