todo:log
(2003/05/23 05:38:42 PDT) ここにこっそりShiroさんへの質問を書いてみよう. SICP読書会のMLから,インタビュー へのリンクがあって見てみたのですが, Lispとの出会いのところで出てきた「Cで書くLispの本」って何という本ですか? まぁ超シンプルなLispインタプリタなら本を見なくても書けると思いますけど, やっぱ教師あり学習の方が…(笑)
- 多分「CプログラムブックIII」では、Will o'Lispというやつ、初代NEC PC-98001 + MS-DOS 2.1 + Microsoft C ver 3.0 で動作したと記憶してます。とご本人ではないのに書いてるのは -- nobsun
- あーそれです。どうしてもタイトルが思い出せなかった。--Shiro
(2003/05/07 08:46:33 PDT) 最近ちょっとプログラムから遠ざかっていて少し寂しい感じ. ネタですが,こんな本出ないですかねぇ….(ネタ元はこちら→ http://www.ilbbs.com/oracovers/ )
- 2003/05/08 09:38:43 PDT ぎゃははは!! さっそく俺言語の表紙を一人寂しく作ってみるテスト(駄目じゃん) -戯
- 言語名(?)に日本語が使えますね。ウマー 「dynamic object/stack oriented language ばぶばぶ」
- こいつをプリンタで刷ってブックカバーにすれば…(^^;
- その前に、来月号の UNIX USERでは、特別企画として「使って学ぶ!Gaucheによる Schemeスクリプトプログラミング」なんてのがあるようですね。sakae(2003/05/09 05:15:44 PDT)
(2003/03/17 03:45:14 PST) 各ドキュメントに名前を付ける機構が欲しいと思った. …というのも,某コーパスにはドキュメント名(番号)が連番で振られているわけではない. つまり,内部のドキュメント番号と実際のドキュメント名の整合性が取れていないことが 問題だと考えたわけである. htmlとかだとタイトルが連番なわけもないし. とりあえず,そのドキュメント一覧を取得するにはドキュメント名に付随している情報を利用するとよい. 某コーパスは<ACCN>, </ACCN>で区切られている.これを利用する.
(use suffix) (define (show-all-titles suf) (for-each (lambda (x) (format (current-output-port) "~a\n" (suffix-substring suf x (+ x 30)))) (suffix-search-keyword suf "<ACCN>")))
>(show-all-titles suf) <ACCN>gakkai-0000000001</ACCN> <ACCN>gakkai-0000000002</ACCN> <ACCN>gakkai-0000000003</ACCN> <ACCN>gakkai-0000000004</ACCN> <ACCN>gakkai-0000000005</ACCN> <ACCN>gakkai-0000000007</ACCN> <ACCN>gakkai-0000000008</ACCN> …(略)
これは全ドキュメント名を表示するだけだが,これを元にドキュメント名を抜き出せばよい. ドキュメント5の次は7になっている. 内部的には,ドキュメント番号は0から連番として数えるから,gakkai-000..07は5番目のドキュメント. この機構はsuffix.scmに組み込むのが多分本筋な気がするので,持たせることにしよう.
(2003/03/17 06:48:02 PST) 少し早めの帰宅. 文字列が定数時間アクセスじゃないとわかっていながら,利便性のために 実際の文字列はstringのまま持たせていた. でもやっぱり2分探索するときだって定数時間アクセスじゃないとやっぱりツライ.
そもそも利便性って何?と言うと,2分探索時の文字列比較や,部分文字列の取り出しかなぁ. Suffix array生成後も文字列をu32vectorで持たせると,一時的な部分文字列の取り出しが 頻発してオブジェクト生成しまくりかなぁ,と思ったので結局文字列はstringのまま 運用していた. でも実際復元するときはsuffix-substring位であることに気付く. それならいっそのことSuffix array生成後も文字列をu32vectorで運用した方がいいだろう. Suffix array生成部にてu32vectorに変換した文字列比較も実装しているし.
やっぱり速度が気になったので,やってみようっと.
(2003/03/17 11:48:39 PST) ぷほ.どうしようもないバグ発見. 辞書順で一番最後に出現する検索文字列を比較する際,検索文字列の末尾にアンカーとして 比較結果が必ず大となる文字を入れておく必要がある. u32vectorで使う以上,2^32 - 1のアンカーを付けておくべきだが, 何を勘違いしたのか,2^16 - 1のアンカーしか付けていなかった("\uFFFF"ってやつ). とりあえず,直しておいた.もう少しでアップ.
(2003/03/15 03:47:00 PST) 色々ソースを直した.
研究室でcvs使ってるのに$Id:$を埋め込んでいないことに気付く. そんなわけでv 1.1.2.7になった. Suffix array構築の際だけ文字へのアクセスを定数時間にするために string->u32vectorを導入する. 実行したら無茶苦茶速くなったが,とうとう懸念されていたメモリ使用量が明るみに.
Multikey Quicksortを破壊ソートで実装していたが,バグが全然取れない. とりあえず時間もないので,リストで持たせていたソート前Suffix arrayを vectorに変更し,破壊ソート. vectorに対する破壊ソートは0.6.7で実現されたがuvectorにはまだ未対応らしい. それは置いといて,問題なのは…, Multikey Quicksortを結局使わず,ただのQuicksortにしてしまったこと. 破壊ソートでメモリ効率は非常に良くなったが,計算が遅くなった. まぁstring-ref時代と比べれば全然マシ.
時間が出来たらMultikeyの破壊ソート版を動かせるようにしよう. とりあえず某コーパス1万件のSuffix arrayがちゃんと作れた. (define suf (suffix-create corpus "</REC>")) で,きちんとドキュメントの区切りもわかっているので, (suffix-number-of-documents suf) ==> 10000 と出てくれる.えがった.
(2003/03/10 08:49:50 PST) 大きいデータを扱う場合,GCは少々考えもの.
(以下,自分のプログラムの設計が悪いことを棚に上げているという前提を置いて読んで下さい)
某コーパスから日本語ドキュメント1万件を取り出し,Suffix arrayを構築させようとした. 現バージョンではソート前のsuffixをリストで持たせている. ちなみに1万件の日本語ドキュメントは約360万文字で6.5MB. ということは,約360万のセルを持つリストが出来上がってしまう. しかも内部ではキューを使ってセルを追加しまくっているので, とんでもない数のセルを生成してしまっている. 約360万のセルを1パスするだけでも異様な時間がかかっているのは, セルの生成やらGC発動やらが原因であろう.
本当にまじめに書かないとまずいな….
- Shiro (2003/03/11 00:18:57 PST): うーん、GCのせいかどうかは
プロファイル取ってみないと何とも言えませんねえ。
セルの生成はfreelistからひとつ取って来るだけなので、
重いとは限りません。ワーキングセットがでかくなると
markに時間がかかるというのはあるでしょう。
あと、util.queueは破壊的操作(set-cdr!)を使っているんですが、 現在のincremental GCはmark済のページに書き込みがあると そのページが再scanされるので、メモリ上に広く分散したリストに 対して頻繁に破壊的操作を行うとmark phaseが追い付かなくなるとか… そういう場合はむしろconsしてってreverseの方が速いかも。
あと、これはGCではないのですが、再帰が深くなってスタックオーバーフローが 発生すると急に性能が落ちます。GaucheのVMの課題です。
- todo (2003/03/11 03:04:04 PST): 今日明日はちょっと忙しいので, まだ詳細なプロファイルはできていないのですが, とりあえず文字の比較部にて,queueを使わずにconsでリストを生成するようにしました. 結果,とりあえず比較的小さなデータ(83kBytes, 英文84237文字)では 今まで15秒かかっていたものが11秒へと速くなりました. その他いくつかのデータでも高速化された模様なので,リベンジしてみようと思います. ちなみに350万のセルは最初に生成しており(内部のcreate-sequence), それは別に遅くなかったことを思い出しました. 情報不足で申し訳ないです.
- todo (2003/03/11 06:54:57 PST): 帰る間際に10万セルごとに残りセル数と時刻を表示してみる. 家に帰って途中経過を見る. http://esmith.ss.ics.tut.ac.jp/kanaya/diary/d200303b.html#11-2-1 う〜ん….
- Shiro (2003/03/11 12:15:33 PST): むむ。O(n^2)なコードが意図せず紛れ込んでいるような 臭いがしますね。ループ内で作ったリストのlength取ったりとかしてます?
- todo (2003/03/11 17:08:04 PST): 残りのカウンタは,最初にループの外でリストの長さを調べ, ループ内でdec!していたのでそこは問題なさげです. リストに対するlengthは取っていないので,他は…と調べたところ, string-ref使ってました. そういやシンプルなC版実装ではコーパス内の文字を全て全角処理していたので, 文字へのアクセスを定数時間で実現していたんだったっけ. 最初の1パスだけなら文字列を規則正しく順に見ていくので 文字の定数時間アクセスを実現することは出来るのですが, Suffix arrayは全部分文字列のソートなので, ソートが進むに連れ,文字の参照場所がバラバラになってしまいます.
- …ということが分かったところでタイムアップ.お出かけしてきます.
- todo (2003/03/12 00:57:59 PST): 帰ってきました. 文字コードにUnicodeにしたときはstring-refは定数時間になるのかな?
- Shiro (2003/03/12 01:12:38 PST): utf-8で持っているので定数時間にはならないです。 インデックスでの参照が主体ならば、string->u32vectorでu32vectorに 変換すると、一文字一ワードの固定長ベクタになります。アルゴリズムによっては そちらの方が扱いやすいかもしれません。
(2003/03/09 11:48:47 PST) 効率が悪いと分かっていながら,まだ改善していないのが, 一番クリティカルな部分であるSuffix arrayの生成部. 最速なのはSuffix Array の効率的な構築法であるが, 代入の嵐であることと,企業の人の論文なので特許が絡んでいると思い, 実装の簡単なMultikey Quicksortを用いている.
…が,シンプルな実装(sort!を使っていた時代)からあまり変更を加えないように作ったせいか, 大量のunsigned intをリストで持ち,とんでもないメモリと計算の効率の悪さが露呈している.
一番計算の大変なところなので,もっと真面目に作る必要がある.
- Schemeでset!を使って頑張る
- 生成部だけはCなどを呼ぶ
でも比較対照が全部分文字列.C側から可変長文字はどのように見えるんだろう…. とりあえず,前者スタートになりそうだ.
- ToDo
- Suffix array生成の高速化
- search-keyword結果のキャッシュ化
- df(document frequency)をdf2, df3…も計算できるように拡張したい(dfx(t):文字列tをx回以上含むドキュメント数)
(2003/03/07 04:11:53 PST) Suffix array操作用モジュールが一応動くようになったので暫定的に公開してみた. まだファイルI/O周りがbuggyだと思うが,統計関係は一応まともに動いている. 検索エンジンに組み込んでも文句は言って来なかった (検索エンジンから派生したモジュールなので当然と言えば当然だが…)
ところで,事後承諾で申し訳ないのですが,ソース公開に当たって 何かやっておかなければならないこととかあるのでしょうか? (ちなみに今は一応暫定公開)
- Shiro(2003/03/09 13:44:37 PST): 特に無いですが、使用条件の表示、ドキュメント、 テストケースが揃っているとみんなに喜ばれることが多いと思います。
金谷の謎日記(2002年9月12日)にも書いたのですが, string-pointerの仕様がどうしてこうなったのか,理解に苦しんでおります.
Cでは,文字列ポインタは文字列の始点が変動するのに対し, string-pointer-set!, string-pointer-next!, string-pointer-prev! のそれぞれの動作は,始点は0のままで終点が変動するようです.
せめて始点を変動させる手続きがあれば納得はいくのですが, どうしてかなぁ…,と悩んでおります.2002/09/12 01:23:59 PDT
- Shiro string-pointer自身は始点も終点も無く、文字列中のある点を指している だけです。(正確には、文字と文字の「間」を指しています)。 で、string-pointer-substringはデフォルトで文字列ポインタの前の 部分文字列を返します。省略可能な第二引数afterに#tが与えられると 文字列ポインタの後の部分文字列を返します。
- んで、string-pointerはあくまでマルチバイト文字列でSRFI-13を効率良く 実装する低レベルな手段に過ぎないので、あまりお勧めしません。 (string-pointer自身はSRFI-13には含まれません)。
- ちなみに、Gaucheではsubstringは文字列をコピーしません。string-takeも string-dropも然り。なので安心してsubstringしまくってください。
なるほど.了解しました. Suffix Arrayを生成する際に,substringが文字列をコピーしていたら恐ろしいことになると思い, string-pointerを使おうと思っていたのですが,なるほどコピーしないなら問題ないですね. 丁寧な解説ありがとうございました.todo 2002/09/12 06:15:16 PDT
- んと、日記(9/13)に突っ込みますと、「いくつかの手続きでは」文字列をコピーしない、 というよりも、原則としてコピーしないのです。コピーされるのは(1)明示的に string-copyを呼んだ時か、(2)文字列に対する破壊的操作をした時、に限られます。 あ、あと文字列の構築時 (string-append等) でも新しい文字列はアロケート されますが。 また、文字列本体はコピーされなくても、各文字列オブジェクトは文字列本体の 始点へのポインタと文字列の長さ(文字数、バイトサイズ)、及びオブジェクトヘッダを 含むので、substring毎に4ワードのメモリがアロケートされます。 これは文字列をコピーする実装でも必要なオーバーヘッドではありますが。Shiro