マルチプロセスで使用可能なロックフリーキュー
タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。
作成物
- ロックフリーなFIFOキュー
- 再入可能 かつ SIGKILLに対して安全*1
- C++
- 共有メモリ(mmap)を使用
- マルチプロセス(and マルチスレッド)間の通信に使用可能
- gcc(ver4.1以上)*2 かつ POSIX準拠環境*3でのみ使用可能
単機能な割に、内部では「まず(割合)汎用的な可変長ブロックメモリアロケータを作って、その上に固定長ブロックアロケータ、さらにその上にFIFOキューを実装」と地味に凝ったことをしている。
使用例
fork()と併用した例。
/** * 親子プロセスで共有するFIFOキューを作成し、子から親へメッセージを送信するサンプルプログラム * * ファイル名: msgque-sample.cc * コンパイル: g++ -o msgque-sample msgque-sample.cc */ #include <imque/queue.hh> // インクルードパスを通しておく #include <unistd.h> // fork, getpid #include <sys/types.h> #include <stdio.h> // sprintf #include <string.h> // strlen #include <iostream> #include <string> #define CHILD_COUNT 10 // 子プロセスの数 #define QUEUE_ENTRY_COUNT 32 // キューの最大要素数 #define SHM_SIZE 4096 // キューが使用可能な共有メモリのバイト数 int main(int argc, char** argv) { // 要素数と共有メモリサイズを指定してキューを作成 imque::Queue que(QUEUE_ENTRY_COUNT, SHM_SIZE); if(! que) { return 1; } for(int i=0; i < CHILD_COUNT; i++) { if(fork() == 0) { // 子プロセスの処理 char buf[1024]; sprintf(buf, "Hello: %d", getpid()); // enqueue que.enq(buf, strlen(buf)); return 0; } } // 親プロセスの処理 for(int i=0; i < CHILD_COUNT; i++) { std::string buf; // dequeue while(que.deq(buf) == false); // キューが空の間はビジーループ std::cout << "[receive] " << buf << std::endl; } return 0; }
実行結果:
$ ./msgque-sample [receive] Hello: 12736 [receive] Hello: 12737 [receive] Hello: 12738 [receive] Hello: 12740 [receive] Hello: 12739 [receive] Hello: 12742 [receive] Hello: 12744 [receive] Hello: 12743 [receive] Hello: 12745 [receive] Hello: 12741
気が向けば、内部で使用しているメモリアロケータのコードなども載せていくかもしれない。
ループ処理を関数型っぽく書いてみる(1)
今週は、common lispでループ処理を関数型っぽく、かつ効率良く実装できるかどうかを試していたので、その結果を載せておく。
結論から云えば、処理系の十分な最適化を期待できれば、関数型っぽく書いても、手続き型的に書いた場合と比肩しえる性能が得られそうな感じだった。
使用例
シーケンス(or 無限シーケンス)とmapとかfilterとかを組み合わせてループを表現する。
;; 1から5までの数値を表示する > (loop:each (lambda (n) (print n)) (loop:from 1 :to 5)) 1 2 3 4 5 => NIL > (loop:from 1 :to 5) => #<CLOSURE (LAMBDA () :IN LOOP:FROM) {10030E0E0B}> ; 実態はクロージャー ;; マッピング > (loop:collect (loop:map (lambda (c) (list c (char-code c))) (loop:for-string "mapping"))) => ((#\m 109) (#\a 97) (#\p 112) (#\p 112) (#\i 105) (#\n 110) (#\g 103)) ;; フィルター > (loop:collect (loop:filter #'oddp (loop:from 1 :to 10))) -> (1 3 5 7 9) ;;; fizzbuzz > (defun fizzbuzz-seq () (loop:filter #'consp (loop:map (lambda (n) (cond ((zerop (mod n 15)) (cons n :fizzbuzz)) ((zerop (mod n 5)) (cons n :buzz)) ((zerop (mod n 3)) (cons n :fizz)) (t nil))) (loop:from 1)))) ;; 先頭三つ > (loop:collect (loop:take 3 (fizzbuzz-seq))) => ((3 . :FIZZ) (5 . :BUZZ) (6 . :FIZZ)) ;; 10から12番目 > (loop:collect (loop:take 2 (loop:drop 10 (fizzbuzz-seq)))) => ((24 . :FIZZ) (25 . :BUZZ)) ;; 100以下かつ偶数のものだけ > (loop:collect (loop:take-while (lambda (x) (<= (car x) 100)) (loop:filter (lambda (x) (evenp (car x))) (fizzbuzz-seq)))) => ((6 . :FIZZ) (10 . :BUZZ) (12 . :FIZZ) (18 . :FIZZ) (20 . :BUZZ) (24 . :FIZZ) (30 . :FIZZBUZZ) (36 . :FIZZ) (40 . :BUZZ) (42 . :FIZZ) (48 . :FIZZ) (50 . :BUZZ) (54 . :FIZZ) (60 . :FIZZBUZZ) (66 . :FIZZ) (70 . :BUZZ) (72 . :FIZZ) (78 . :FIZZ) (80 . :BUZZ) (84 . :FIZZ) (90 . :FIZZBUZZ) ;; zip > (loop:collect (loop:take 3 (loop:map-n 3 (lambda (x y z) (list x y z)) ; zipと組み合わせる場合は XXX-n 系のマクロを使用して、引数の数を指定する (loop:zip (loop:filter #'oddp (loop:from 1)) (loop:down-from 100 :by 3) (loop:map #'sqrt (loop:repeat (lambda () (random 1000)))))))) => ((1 100 19.078785) (3 97 19.052559) (5 94 16.309507)) ;; フィボナッチ数列を定義 (defun fib-seq () (let ((n+1 1)) (declare (fixnum n+1)) (loop:make-generator :init (lambda () 0) ; 初期値生成関数 :next (lambda (n) (prog1 n+1 (incf n+1 n))) ; 値更新関数 :end? (lambda (n) (declare (ignore n)) nil)))) ; 終端判定関数 > (loop:collect (loop:take 20 (fib-seq))) => (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
速度比較
loopマクロやdoを使って書いた場合との速度比較。
処理系はSBCL(1.0.54)。
比較1: sum関数 (単純なループ)
;; 準備 (defparameter *fastest* '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))) (defparameter *note* '(sb-ext:unmuffle-conditions sb-ext:compiler-note)) ;; loopパッケージ版 (defun sum1 (start end) (declare (fixnum start end) #.*fastest* #.*note*) (loop:reduce (lambda (acc x) (the fixnum (+ acc x))) 0 (loop:from start :to end))) ;; loopマクロ版 (defun sum2 (start end) (declare (fixnum start end) #.*fastest* #.*note*) (loop WITH total fixnum = 0 FOR i FROM start TO end DO (incf total i) FINALLY (return total))) ; (loop ... SUM i) では最適化されない部分があるので、少し長くなるけどこちらを採用 ;; do版 (defun sum3 (start end) (declare (fixnum start end) #.*fastest* #.*note*) (let ((total 0)) (declare (fixnum total)) (do ((i start (1+ i))) ((> i end) total) (incf total i)))) ;; 実行 > (time (sum1 1 100000000)) ; loopパッケージ版: 0.084秒 Evaluation took: 0.084 seconds of real time 0.084006 seconds of total run time (0.084006 user, 0.000000 system) 100.00% CPU 167,231,593 processor cycles 0 bytes consed => 5000000050000000 > (time (sum2 1 100000000)) ; loopマクロ版: 0.086秒 Evaluation took: 0.086 seconds of real time 0.088005 seconds of total run time (0.088005 user, 0.000000 system) 102.33% CPU 171,410,077 processor cycles 0 bytes consed => 5000000050000000 > (time (sum3 1 100000000)) ; do版: 0.083秒 Evaluation took: 0.083 seconds of real time 0.084005 seconds of total run time (0.084005 user, 0.000000 system) 101.20% CPU 166,793,649 processor cycles 0 bytes consed => 5000000050000000
単純なループ処理なら、どれも速度は同じくらい。
比較2: 数値リストの奇数番目の要素の平均値を求める (zipを使ったループ)
;; データ準備: 1000万要素のリスト (defparameter *list* (loop REPEAT 10000000 COLLECT (random 100000))) ;; loopパッケージ版 (defun avg1 (list) (declare #.*fastest* #.*note*) (flet ((average (sequence) ; シーケンスの生成と平均値を求める処理を分離することが可能 (let ((total 0) (count 0)) (declare (fixnum total count)) (loop:each (lambda (n) (incf total n) (incf count)) sequence) (float (/ total count))))) (let ((seq (loop:map-n 2 (lambda (_ n) n) (loop:filter-n 2 (lambda (i _) (oddp i)) (loop:zip (loop:from 0 :to most-positive-fixnum) (loop:for-list list :element-type fixnum)))))) (average seq)))) ;; loopマクロ版 (defun avg2 (list) (declare #.*fastest* #.*note*) (loop WITH total fixnum = 0 WITH count fixnum = 0 FOR i fixnum FROM 0 FOR n fixnum IN list WHEN (oddp i) DO (incf total n) (incf count) FINALLY (return (float (/ total count))))) ;; do版 (defun avg3 (list) (declare #.*fastest* #.*note*) (let ((total 0) (count 0)) (declare (fixnum total count)) (do ((i 0 (1+ i)) (head list (cdr head))) ((endp head)) (declare (fixnum i)) (when (oddp i) (incf count) (incf total (the fixnum (car head))))) (float (/ total count)))) ;; 実行 > (time (avg1 *list*)) ; loopパッケージ版: 0.084秒 Evaluation took: 0.084 seconds of real time 0.084005 seconds of total run time (0.084005 user, 0.000000 system) 100.00% CPU 166,739,958 processor cycles 0 bytes consed => 50003.64 > (time (avg2 *list*)) ; loopマクロ版: 0.036秒 Evaluation took: 0.036 seconds of real time 0.036002 seconds of total run time (0.036002 user, 0.000000 system) 100.00% CPU 72,645,764 processor cycles 0 bytes consed => 50003.64 > (time (avg3 *list*)) ; do版: 0.037秒 Evaluation took: 0.037 seconds of real time 0.040003 seconds of total run time (0.040003 user, 0.000000 system) 108.11% CPU 75,246,648 processor cycles 0 bytes consed => 50003.64
loopパッケージ版はzipを通すと、loopマクロやdoを使った場合の半分以下になってしまう。
比較3: 比較2での、平均値算出部分と奇数番要素のフィルタ部分を、別関数に分けた場合
;; loopマクロで、平均値算出部分と奇数番要素のフィルタ部分を、別関数に分けた場合 (declaim (inline average-list)) (defun average-list (list) (declare #.*fastest* #.*note*) (loop WITH total fixnum = 0 WITH count fixnum = 0 FOR n fixnum IN list DO (incf total n) (incf count) FINALLY (return (float (/ total count))))) (declaim (inline filter-list)) (defun filter-list (list) (declare #.*fastest* #.*note*) (loop FOR i fixnum FROM 0 FOR x IN list WHEN (oddp i) COLLECT x)) > (time (average-list (filter-list *list*))) Evaluation took: 0.122 seconds of real time ; 全体で0.122秒、GC抜きなら0.081秒 0.120008 seconds of total run time (0.120008 user, 0.000000 system) [ Run times consist of 0.040 seconds GC time, and 0.081 seconds non-GC time. ] 98.36% CPU 244,986,221 processor cycles 79,986,688 bytes consed => 50003.64 ;; do版 ;; ※ loopマクロ版とほとんど変わらないので省略 ;; loopパッケージで、平均値算出部分と奇数番要素のフィルタ部分を、別関数に分けた場合 (declaim (inline average-loop)) (defun average-loop (sequence) (declare #.*fastest* #.*note*) (let ((total 0) (count 0)) (declare (fixnum total count)) (loop:each (lambda (n) (incf total (the fixnum n)) (incf count)) sequence) (float (/ total count)))) (declaim (inline filter-loop)) (defun filter-loop (list) (declare #.*fastest* #.*note*) (loop:map-n 2 (lambda (_ n) n) (loop:filter-n 2 (lambda (i _) (oddp i)) (loop:zip (loop:from 0 :to most-positive-fixnum) (loop:for-list list :element-type fixnum))))) > (time (average-loop (filter-loop *list*))) Evaluation took: 0.070 seconds of real time ; 0.070秒 0.072005 seconds of total run time (0.072005 user, 0.000000 system) 102.86% CPU 139,856,631 processor cycles 0 bytes consed => 50003.64 ;; loopパッケージでinline宣言を外した場合 (declaim (notinline average-loop)) (declaim (notinline filter-loop)) > (time (average-loop (filter-loop *list*))) Evaluation took: 0.378 seconds of real time ; 0.378秒 0.376024 seconds of total run time (0.376024 user, 0.000000 system) 99.47% CPU 754,498,049 processor cycles 0 bytes consed => 50003.64
loopマクロやdoマクロでは、ループ処理の一部を自然な形で効率よく外だしするのが困難なので、そういった用途ではloopパッケージの方が性能が良い。
ただし、現状のloopパッケージは、inline展開による最適化に過度に依存しているので、展開が効かないケースでは、いっきに処理速度が遅くなってしまう。
Gomokuの形態素解析部をScalaで実装してみた
ここ数日はScalaのコップ本を読んでいて、何かまとまったプログラムをScalaで書いてみたくなったのでGomoku(Java形態素解析器。ver0.0.6)をScalaで実装してみた*1。
・github: scala-gomoku(ver0.0.1)
使用例
$ scala -cp scala-gomoku-0.0.1.jar // インタプリタ起動 & パッケージインポート scala> import net.reduls.scala.gomoku._ // 分かち書き scala> Tagger.wakati("Scalaはオブジェクト指向言語と関数型言語の特徴を統合したマルチパラダイムのプログラミング言語である。") res0: List[String] = List(Scala, は, オブジェクト, 指向, 言語, と, 関数, 型, 言語, の, 特徴, を, 統合, し, た, マルチパラダイム, の, プログラミング, 言語, で, ある, 。) // 形態素解析 scala> Tagger.parse("Scalaはオブジェクト指向言語と関数型言語の特徴を統合したマルチパラダイムのプログラミング言語である。") res1: List[net.reduls.scala.gomoku.Morpheme] = List(Morpheme(Scala,名詞,固有名詞,組織,*,*,*,0), Morpheme(は,助詞,係助詞,*,*,*,*,5), Morpheme(オブジェクト,名詞,一般,*,*,*,*,6), Morpheme(指向,名詞,サ変接続,*,*,*,*,12), Morpheme(言語,名詞,一般,*,*,*,*,14), Morpheme(と,助詞,並立助詞,*,*,*,*,16), Morpheme(関数,名詞,一般,*,*,*,*,17), Morpheme(型,名詞,接尾,一般,*,*,*,19), Morpheme(言語,名詞,一般,*,*,*,*,20), Morpheme(の,助詞,連体化,*,*,*,*,22), Morpheme(特徴,名詞,一般,*,*,*,*,23), Morpheme(を,助詞,格助詞,一般,*,*,*,25), Morpheme(統合,名詞,サ変接続,*,*,*,*,26), Morpheme(し,動詞,自立,*,*,サ変・スル,連用形,28), Morpheme(た,助動詞,*,*,*,特殊・タ,基本形,29), Morpheme(マルチパラダイム,名詞,一般,*,*,*,*,30), Morpheme(の,助詞,連体化,*,*,*,*,38), Morpheme(プログラミング,名詞,サ変接続,*,*,*,*,39), Morpheme(言語,名詞,一般,*,*,*,*,46), Morpheme(で,助動詞,*,*,*,特殊・ダ,連用形,48), Morpheme(ある,助動詞,*,*,*,五段・ラ行アル,基本形,49), Morpheme(。,記号,句点,*,*,*,*,51)) // 名詞のみ取り出し scala> for(m <- res1 if m.feature.startsWith("名詞")) yield m.surface res2: List[String] = List(Scala, オブジェクト, 指向, 言語, 関数, 型, 言語, 特徴, 統合, マルチパラダイム, プログラミング, 言語)
ソースコード行数
Java:
$ cd gomoku-0.0.6-src $ wc -l `find . -name '*.java'` 117 ./analyzer/src/net/reduls/gomoku/Tagger.java 12 ./analyzer/src/net/reduls/gomoku/Morpheme.java 23 ./analyzer/src/net/reduls/gomoku/util/ReadLine.java 83 ./analyzer/src/net/reduls/gomoku/util/Misc.java 38 ./analyzer/src/net/reduls/gomoku/bin/Gomoku.java 32 ./analyzer/src/net/reduls/gomoku/dic/Unknown.java 72 ./analyzer/src/net/reduls/gomoku/dic/Char.java 23 ./analyzer/src/net/reduls/gomoku/dic/WordDic.java 61 ./analyzer/src/net/reduls/gomoku/dic/SurfaceId.java 43 ./analyzer/src/net/reduls/gomoku/dic/Morpheme.java 26 ./analyzer/src/net/reduls/gomoku/dic/PartsOfSpeech.java 23 ./analyzer/src/net/reduls/gomoku/dic/ViterbiNode.java 26 ./analyzer/src/net/reduls/gomoku/dic/Matrix.java 579 合計
$ cd scala-gomoku-0.0.1-src $ wc -l `find . -name '*.scala'` 3 ./src/net/reduls/scala/gomoku/Morpheme.scala 27 ./src/net/reduls/scala/gomoku/bin/Gomoku.scala 15 ./src/net/reduls/scala/gomoku/dic/Matrix.scala 13 ./src/net/reduls/scala/gomoku/dic/PartsOfSpeech.scala 18 ./src/net/reduls/scala/gomoku/dic/Morpheme.scala 22 ./src/net/reduls/scala/gomoku/dic/Char.scala 32 ./src/net/reduls/scala/gomoku/dic/Util.scala 9 ./src/net/reduls/scala/gomoku/dic/ViterbiNode.scala 39 ./src/net/reduls/scala/gomoku/dic/SurfaceId.scala 30 ./src/net/reduls/scala/gomoku/dic/Unknown.scala 15 ./src/net/reduls/scala/gomoku/dic/WordDic.scala 56 ./src/net/reduls/scala/gomoku/Tagger.scala 279 合計
処理速度
以下のようなベンチマークスクリプトを書いて、両者の処理速度を比較してみた。
// ファイル名: Benchmark.scala import scala.testing.Benchmark import net.reduls.scala.gomoku.{Tagger=>ScalaTagger} import net.reduls.gomoku.{Tagger=>JavaTagger} import scala.io.Source // ベンチマーク用データ: 使用したのは約17MBの日本語テキストデータ object BenchmarkData { val lines = Source.fromFile("/path/to/testdata").getLines.toArray } // Scala用のベンチマークオブジェクト object ScalaGomokuBenchmark extends Benchmark { // BenchmarkData.linesの各行を分かち書き override def run() { BenchmarkData.lines.foreach(ScalaTagger.wakati _) } } // Scala用のベンチマークオブジェクト object JavaGomokuBenchmark extends Benchmark { override def run() { BenchmarkData.lines.foreach(JavaTagger.wakati _) } } // ベンチマーク実行 println("[Data]") println(" lines: " + BenchmarkData.lines.length) println("") val scalaRlt = ScalaGomokuBenchmark.runBenchmark(11).tail println("[Scala]") println(" result : " + scalaRlt.mkString(", ")) println(" average: " + (scalaRlt.sum / scalaRlt.length)) println("") val javaRlt = JavaGomokuBenchmark.runBenchmark(11).tail println("[Java]") println(" result : " + javaRlt.mkString(", ")) println(" average: " + (javaRlt.sum / javaRlt.length)) println("")
実行結果:
# Scala: version 2.9.0.1 (OpenJDK 64-Bit Server VM, Java 1.6.0_23). $ scala -cp scala-gomoku-0.0.1.jar:gomoku-0.0.6.jar Benchmark.scala [Data] lines: 172088 # データの行数(約17万行) [Scala] result : 4529, 4574, 4568, 4540, 4503, 4510, 4523, 4515, 4551, 4531 average: 4534 # 平均: 4.534秒 [Java] result : 3153, 3111, 3118, 3112, 3102, 3098, 3118, 3130, 3117, 3133 average: 3119 # 平均: 3.119秒
自分の環境では、Scala版はJava版よりも1.5倍程度遅かった。
※ まだScalaでの効率の良い書き方とかが全然分かっていないので、その辺りを踏まえてちゃんと最適化を行えばもっと差は縮まるかもしれない
erl-creole: ユニコード文字列とマルチバイト列の変換ライブラリ
少し必要になったのでErlangでユニコード文字列と各種エンコーディングのマルチバイト列(バイナリ)の相互変換を行うモジュールを作成した。
github: erl-creole-0.0.1
- UTF-8, Shift_JIS, CP932, EUC-JP, eucJP-ms, JIS(ISO-2022-JP), ISO-2022-JP-1
使用例
%% 入力文字列 > S = "Unicode (ユニコード) とは、世界中の多くのコンピュータ上の文字列を一貫した方法で符号化し、表現し、扱うためのコンピュータ業界の標準である。". %% EUC-JPに変換 > creole:from_string(S, eucjp). <<"Unicode (\æ\Ë\³¡¼\É) ¤È¤Ï¡¢À¤³釗Ãæ¤Î¿¤¯¤Î\³\ó\Ô\塼\¿¾å¤Îʸ»úÎó¤ò°ì´Ó¤·¤¿ÊýË¡¤ÇÉä¹æ²½¤·¡¢É½¸½¤·¡¢°·¤釗¤¿¤á¤Î\³\ó\Ô\å¡"...>> %% JIS(ISO-2022-JP)に変換 > Bin = creole:from_string(S, jis). <<"Unicode (\e$B%f%K%3!<%I\e(B) \e$B$H$O!\"@$3&Cf$NB?$/$N%3%s%T%e!<%?>e$NJ8;zNs$r0l4S$7$?J}K!$GId9f2=$7!\"I=8=$7!\"07$&$?$a$N"...>> %% バイト列からユニコード文字列に変換 > creole:to_string(Bin, jis). [85,110,105,99,111,100,101,32,40,12518,12491,12467,12540, 12489,41,32,12392,12399,12289,19990,30028,20013,12398,22810, 12367,12398,12467,12531,12500|...] > io:format("~ts~n", [creole:to_string(Bin, jis)]). Unicode (ユニコード) とは、世界中の多くのコンピュータ上の文字列を一貫した方法で符号化し、表現し、扱うためのコンピュータ業界の標準である。 ok %% 変換不能なバイト列がある場合は、デフォルトでは "?" が代わりに使用される > io:format("~ts~n", [creole:to_string(<<"Unicode (\e$B%~^s^sjaf*(asf7aK%3!<%I">>, jis)]). Unicode (??潁潁裃罟?癈羞疔コード ok %% "?"の代わりに"_"を使用 > io:format("~ts~n", [creole:to_string(<<"Unicode (\e$B%~^s^sjaf*(asf7aK%3!<%I">>, jis, creole:replace($_))]). Unicode (__潁潁裃罟_癈羞疔コード ok
*1:ユニコードと他のエンコーディングのコードポイントの対応は主に http://source.icu-project.org/repos/icu/data/trunk/charset/data/ucm/ を参考にさせてもらった。
文字列/バイト列用のハッシュ関数ライブラリ
A Hash Function for Hash Table Lookupに載っているハッシュ関数(Jenkins Hash)をCommon Lispで実装した。
github: jenkins-hash(0.0.2)
作成の主な動機は以下の二つ:
おそらくSBCL以外の処理系でも動くと思うけど、動作は未確認。
使用例
以下、使用例。
;;;; SBCL-1.0.51-64bit ;;; 【文字列】 ;; 文字列からハッシュ値を算出 (jenkins-hash:hash-string "ハッシュ関数") --> 3188986421 ; 一つのキーに対して二つのハッシュ値(32bit)を返す 2167986557 ;; パラメータ(seed1,seed2)を替えて別のハッシュ値を算出 (jenkins-hash:hash-string "ハッシュ関数" :seed1 13 :seed2 44444) --> 2402597428 3323692532 ;; 範囲指定 (jenkins-hash:hash-string "ハッシュ関数" :start 2 :end 4) --> 58741211 888923469 ;;; 【バイト列】 ;; バイト列からハッシュ値を算出 (jenkins-hash:hash-octets (sb-ext:string-to-octets "ハッシュ関数")) --> 1523938354 936250363 ;; sxhash関数だと配列を与えた場合、全て同じハッシュ値になってしまう (sxhash (sb-ext:string-to-octets "ハッシュ関数")) --> 518591303 (sxhash (sb-ext:string-to-octets "別の値")) --> 518591303 ;;; 【複数のハッシュ値】 ;; nth-hash関数を使って、任意個のハッシュ値を安価に生成可能 ;; ※ 内部的にはDoubleHashingを用いて生成している => 可算一つと乗算一つで算出可能 ;; 一つのキーに対する10個の異なるハッシュ値を取得する (defun hash10 (key) (multiple-value-bind (h1 h2) (jenkins-hash:hash-string key) ;; 最初の二つはそのまま使って、残りはnth-hash関数で生成する `(,h1 ,h2 . ,(loop FOR i FROM 2 BELOW 10 COLLECT (jenkins-hash:nth-hash i h1 h2))))) (hash10 "ハッシュ関数") --> (3188986421 2167986557 3229992239 1103011500 3270998057 1144017318 3312003875 1185023136 3353009693 1226028954)
cc-dict: ハッシュテーブル
ハッシュテーブルを実装してみた。
・cc-dict-0.0.3
チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。
Sanmoku(0.0.5): 原型や読みの情報取得に対応
Sanmoku(0.0.4): 辞書データサイズ縮小のコメントにて要望があったのでSanmokuを形態素の原型や読みの情報取得に対応させてみた。
Sanmoku本体のインターフェースは以前の同様*1で、原型・読み・発音の取得を行うためのFeatureExクラス(sanmoku-feature-ex-x.x.x.jar)を新しく追加した。
使用例:
import net.reduls.sanmoku.Tagger; import net.reduls.sanmoku.Morpheme; import net.reduls.sanmoku.FeatureEx; // 追加 for(Morpheme m : Tagger.parse("...")) { // 形態素解析 FeatureEx fe = new FeatureEx(m); // 解析結果の形態素インスタンスから、追加の素性データを取得 // 結果表示 System.out.println(m.surface+"\t"+m.feature+","+fe.baseform+","+fe.reading+","+fe.pronunciation); }
$ export CLASSPATH=sanmoku-0.0.5.jar:sanmoku-feature-ex-0.0.1.jar $ echo '招待制でリリースしました' | java net.reduls.sanmoku.bin.SanmokuFeatureEx 招待 名詞,サ変接続,*,*,*,*,招待,ショウタイ,ショータイ 制 名詞,接尾,一般,*,*,*,制,セイ,セイ で 助詞,格助詞,一般,*,*,*,で,デ,デ リリース 名詞,サ変接続,*,*,*,*,リリース,リリース,リリース し 動詞,自立,*,*,サ変・スル,連用形,する,シ,シ まし 助動詞,*,*,*,特殊・マス,連用形,ます,マシ,マシ た 助動詞,*,*,*,特殊・タ,基本形,た,タ,タ EOS
比較
以前の表にSanmoku-0.0.5(+ FeatureEx-0.0.1)を追加したもの。
| 辞書データサイズ(IPADIC) | 最小所要メモリ(-Xmx) | 起動(≒辞書ロード)時間*2 | 10MBテキストの解析時間 | |
|---|---|---|---|---|
| Igo-0.4.3 | 40MB | 73MB | 0.058秒 | 2.729秒 |
| Gomoku-0.0.4 | 8.2MB | 23MB | 0.371秒 | 2.621秒 |
| Sanmoku-0.0.4 | 4.8MB | 2MB | 0.057秒 | 5.807秒 |
| Sanmoku-0.0.5(+ FeatureEx-0.0.1) | 10MB | 11MB | 0.098秒 | 6.814秒 |
読み等の情報を取得した場合、性能は全体的に劣化しているけど、これくらいなら十分許容範囲内のような気がする。
