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 一つのキーから複数のハッシュ値を得たい場…