Google
ブログ(iiyu.asablo.jpの検索)
ホットコーナー内の検索
 でもASAHIネット(asahi-net.or.jp)全体の検索です。
 検索したい言葉のあとに、空白で区切ってki4s-nkmrを入れるといいかも。
 例 中村(show) ki4s-nkmr

ウェブ全体の検索

Re: ちょっと気になる本、その22006年04月20日 01時47分33秒

ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://iiyu.asablo.jp/blog/2006/04/08/319429
ちょっと気になる本
http://iiyu.asablo.jp/blog/2006/04/20/334280
ちょっと気になる本の続きと、SICPのことも再論
http://iiyu.asablo.jp/blog/2006/04/20/334285
Re: ちょっと気になる本
の続き。

 福岡さんから。
--- ここから ---
中村様へ

福岡と申します。

いつも、刺激的なコラムありがとうございます。
#あ、知的な刺激という意味です

コラムで書かれている通り、こんな、大事だけど、儲からないかもしれない分
野を出してくれた著者と出版社と、普段楽しませていただいている中村様への
お礼として、ご紹介いただいた、HaskelとOSの本、早速アフィリエイトのリン
ク経由で発注させていただきました。

で、以前から中村様も紹介されていたんですが、今まで、買わずに眺めていた
魔法使い本も、年貢の納め時かと、リンクをクリックしましたが、おかしいで
す。
アマゾンには飛びますが、該当の書籍が表示されません。

ご連絡まで。
--- ここまで ---

 すみませんでした&通知ありがとうございまいた。すでに直してありますが、
http://www.amazon.co.jp/exec/obidos/ASIN/489471163X/showshotcorne-22/ref=nosim
Harold Abelson, Gerald Jay Sussman, Julie Sussman著、和田英一訳
「計算機プログラムの構造と解釈」
です。

 この前の「Re: ちょっと気になる本」で、Common Lispでtak関数のたらい回
しをやったら、相当に速かったという話を書きましたが、
「Allegro Common Lisp(ACL)とLispworksのCommon Lispでメモ化したtak関数
をやってみたら、(time (tak 100 50 0))だと実行時間は、0でした。メモ化し
ないバージョンでも(time (tak 12 6 0))は、ぼくのマシン(Lenovoじゃないこ
ろのIBM ThinkPad T41、Pentimum 1.6GHz, メモリ512MB)では、トータル190ms
(0.19)でした」
は、ネイティブコンパイルしたものです。
 そこで、ACLのインタープリタとコンパイラでちょっと遊んでみました。
 インタープリタだと遅い。
CL-USER> (time (tarai 12 6 0))
は、数分待ったけど、戻ってこないので止めました。\(^O^)/
 なお、関数名は、takじゃなくて、taraiのほうに統一しました。
 メモ化したtarai-memoをインタープリタで実行すると、

CL-USER> (time (tarai-memo 12 6 0))
; cpu time (non-gc) 20 msec user, 0 msec system
; cpu time (gc) 30 msec user, 0 msec system
; cpu time (total) 50 msec user, 0 msec system
; real time 330 msec
; space allocation:
; 36,752 cons cells, 436,216 other bytes, 0 static bytes

です。
 tarai-memoは、クロージャとハッシュを使って記憶しますが、ハッシュだけ
でストレートにやる方法でやってみたのがtarai-memo-hash-optです。実はこ
れはコンパイラ用の最適化ヒントがいろいろ埋め込まれているバージョンです
が、これらのヒントは、インタープリタには関係ないと思います。ハッシュキ
ーはリストよりfixnumのほうが速いので、fixnumのキーを使っています。

CL-USER> (time (tarai-memo-hash-opt 12 6 0))
; cpu time (non-gc) 10 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 10 msec user, 0 msec system
; real time 10 msec
; space allocation:
; 53,863 cons cells, 1,395,512 other bytes, 0 static bytes

 次は、tarai, tarai-memo, tarai-memo-hash-optをコンパイルして実行した
ものです。

CL-USER> (time (tarai 12 6 0))
; cpu time (non-gc) 190 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 190 msec user, 0 msec system
; real time 191 msec
; space allocation:
; 3 cons cells, 0 other bytes, 0 static bytes

CL-USER> (time (tarai-memo 12 6 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 1,014 cons cells, 5,200 other bytes, 0 static bytes

は、速すぎて計測不能です。tarai-memo-hash-optも

CL-USER> (time (tarai-memo-hash-opt 12 6 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 3 cons cells, 6,112 other bytes, 0 static bytes

のように速すぎて計測不能です。よって、以降は、メモ化した2つのバージョ
ンのみ、もっとでかいのでやってみました。

CL-USER> (time (tarai-memo 100 50 0))
; cpu time (non-gc) 40 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 40 msec user, 0 msec system
; real time 40 msec
; space allocation:
; 87,342 cons cells, 859,200 other bytes, 0 static bytes

CL-USER> (time (tarai-memo-hash-opt 100 50 0))
; cpu time (non-gc) 10 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 10 msec user, 0 msec system
; real time 10 msec
; space allocation:
; 3 cons cells, 214,832 other bytes, 0 static bytes

 tarai-memo-hash-optをインタープリタで、100 50 0でやってみると、

CL-USER> (time (tarai-memo-hash-opt 100 50 0))
; cpu time (non-gc) 902 msec user, 0 msec system
; cpu time (gc) 2,603 msec user, 10 msec system
; cpu time (total) 3,505 msec user, 10 msec system
; real time 3,595 msec
; space allocation:
; 3,158,558 cons cells, 81,974,248 other bytes, 0 static bytes

なので、ざっと350倍のスピードアップですね。まあ、これは特別な例でしょ
うけど、Lispのコンパイラはかなり優秀なことはわかってもらえるでしょうか。
 Lispは遅いという誤解がいまだに蔓延していますが、いまのマシン環境なら
インタープリタでも決して遅くないし、コンパイルするととっても速いんです
よね。インタープリタで対話的に開発しながら、ある程度まとまったらコンパ
イルしていく、それも関数毎にインクリメンタルコンパイルしたり、ファイル
まとめてバッチ的にコンパイルもできるし、そういう言語です。
 弾さんの
http://blog.livedoor.jp/dankogai/archives/50460894.html
速く動くより早く書くが重要な時代
は、もっともな主張。
 この前も書いたけど、よくあるウェブアプリのようなものは、スクリプト言
語でも十分な時代になってるんです。だって、RDBはネイティブで動いている
わけだし、ブラウザのレンダリングもネイティブだし、スクリプト言語はそれ
らをつなぐグルー(糊付け)言語として、いい道具なんです。
 ただ、元の主張を
http://www.dmtj.net/pm/archives/2006/03/_web.php
素朴な疑問 - なぜスクリプト系 Web アプリ言語がいまだ主流なのか?
を読むと、MVCのVをネイティブコンパイラのある言語で高速化しないとまずい
のではないかといってるのは、一理ありますね。でも、大した量のHTMLを吐く
わけじゃないから、負荷の高いサイト以外は大した問題じゃないとも思うけれ
ど。
 ぼくがLisp、それもCommon Lispを少しずつ勉強しているのは、やはりコン
パイラがあるからで、仕事でやってるバイオの世界は、もういくら速くても処
理できそうにないくらいデータが毎日増え続けています。
 1回全体を処理するには、1ヵ月コンピュータ回しっぱなしになる世界です。
バイオの世界は、Perlを使ったバイオインフォマティクス入門がオライリーか
ら出ていたこともあって、Perlがよく使われているんですが、でも、遅くて対
応できないという現実も明らかになってきています。
 逆にいうと、倍速くなっただけで、1ヵ月かかった処理が2週間でできるよ
うになったといって喜ばれるんです。一桁(10倍)速くなると、3日で処理でき
るようになるわけで、割と簡単に10倍速くできる技術のひとつがコンパイラ
なんですね。
 いまのスクリプト言語が、いつごろ、どういうコンパイラを手に入れるよう
になるか、常に注目はしています。Lispは遅い遅いといわれたことに反発して、
実行スピードでCと遜色ないくらいの非常に優秀な最適化コンパイラを搭載す
るようになりました。歴史は繰り返すというから、いいコンパイラの出現を期
待して、いまは、スクリプト言語は遅い遅いといい続けようと思ってます。
 一昨日、慶応で講師の懇親会があったんですが、最近、またLispを勉強して
いるといったら、まだ、Lispなんかやってる人がいるんだとかいわれたけど
(爆笑)、いまのぼくには、ますますよさげな言語なんです。Lispハッカーのポ
ール・グレアムもいうように、Lispで書く人があまり増えないほうが競争力が
あっていいんですけどね。^^;
 
 ついでに、tarai-memo-hash-optは、もっと大きなのでやってみました。

CL-USER> (time (tarai-memo-hash-opt 1000 500 0))
; cpu time (non-gc) 121 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 121 msec user, 0 msec system
; real time 130 msec
; space allocation:
; 3 cons cells, 4,005,984 other bytes, 0 static bytes

 こういうスケーラビリティも、最適化コンパイラを使いたい大きな理由です。

 これは、この前、数理システムであったセミナーで配られたACL 8.0デモ版
でやりましたが、いま、オンラインで配られているACL 7.0でも同じだと思い
ます。
 それと、ぼく、最近知った、LispWorksのLispは、なかなかいいなと思って
います。
 Windows, Linux, Mac OS Xで同じGUIが書けるようだし、コンパイラも優秀
です。ネイティブコードではなく仮想マシンコードにコンパイルしてますが、
tarai関数の例ならネイティブコードにコンパイルするACLと遜色ないです。ラ
ンタイムも出来がいいんでしょうね。統合開発環境(IDE)は、ACLより使いやす
い感じがします。
 このIDEをポータブルなGUIライブラリCAPで書いてるんだそうです。ACLも
Common GraphicsというGUIライブラリがあるけど、WindowsとLinuxなんです
(Linuxは実験的実装の段階)。バイオ系は、Mac OS Xがビジネス系より多いの
で、Mac OS Xでも動いてくれないと困るんです。
 いまは、仕事でJavaのAWT/Swingで書いていて、実際書いてみると、ちゃん
とWindows, Linux, Mac OS Xで動くので、ちょっと感動しました。Mac OS Xだ
けは、Option Qなどのハンドラを別に書きましたが、それでも、AWT/Swingは、
一番、成熟しているマルチプラットフォームのGUIライブラリだと感じていま
す。でも、Lispでもこの3つのプラットフォームをサポートできるなら、仕事
では無理かもしれないけど、趣味では書いてみたい気もしてます。

http://jp.franz.com/index.html
Allegro Common Lisp(ACL)のフランツ社
http://www.lispworks.com/
LispWorks社

 tarai-memoは、tarai-memo-hash-optより汎用性のある方法でメモ化してい
ますが、これ、実は、プロや達人Lisperからみるとさして汎用性がありません。
プロや達人Lisperが考えることは、すごいです。
http://www.tfeb.org/lisp/hax.html#MEMOIZE
をみてください。
 局所関数のメモ化も考慮してあるし、頭のいいコンパイラが自己再帰をイン
ライン展開してしまうことまで考えているんです。tarai-memoの手法は、グロ
ーバルな関数名のテーブルを操作して、実体をクロージャ化した関数に置き換
えるので、インライン展開されて名前がなくなると、通用しません。それで、
このライブラリでは、def-memoized-functionマクロを定義して、このマクロ
を使って定義するときは、コンパイラにインライン展開しないように指示する
んです。
 局所関数のメモ化をするmemoized-labelsマクロのソースをみると何をやっ
てるんだと、Common LispというよりSchemeもCommon Lispも素人同然、初心者
のおれは頭痛くなりました。^^;
 このライブラリは今回のtaraiには大げさだと思ったので、tara-memoは、こ
のライブラリを非常に簡略化したものになってます。ソースをみると、
http://www.amazon.co.jp/exec/obidos/ASIN/1558601910/showshotcorne-22/ref=nosim
Peter Norvig著「Paradigms of Artificial Intelligence Programming: Case
Studies in Common Lisp」
を参照しています。なんと、この本、いま、読んでいる最中です。この前や
LispやPrologやAIのこと勉強しなおしているといってたのは、これです(あと
ほかにもあるんですけど)。
 いま、200ページの手前です。memoizeが出てくるのが、260ページくらいな
んですね。ああ、もう少しがんばっていれば、ばっちりだったのに、引きが弱
い!(泣)
 でも、なんか、シンクロニシティを感じました。ともかく、弾さんに感謝で
すね。
 tarai-memoのソースは、
http://www.asahi-net.or.jp/~ki4s-nkmr/tarai/tarai-memo.lisp

 tarai-memo-hash-optのソースは、
http://www.asahi-net.or.jp/~ki4s-nkmr/tarai/tarai-memo-hash-opt.lisp
に置きました。

コメント

コメントをどうぞ

※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。

※なお、送られたコメントはブログの管理者が確認するまで公開されません。

※投稿には管理者が設定した質問に答える必要があります。

名前:
メールアドレス:
URL:
次の質問に答えてください:
一富士、二鷹、三は? ひらがなで。

コメント:

トラックバック

_ 404 Blog Not Found - 2006年04月25日 13時38分11秒

おお、ついに正三郎さんまでたらい回し大会に参加!で、ここ読んで
標題: Re: ちょっと気になる本、その2: ホットコーナーの舞台裏この前も書いたけど、よくあるウェブアプリのようなものは、スクリプト言
語でも十分な時代になってるんです。だって、RDBはネイティブで動....

_ ホットコーナーの舞台裏 - 2010年05月06日 09時15分49秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
 アメリカは、さすがにAI(人工知能)本が出続けていますね。こういう

_ ホットコーナーの舞台裏 - 2011年01月20日 03時04分07秒

ASAHIネット(http://asahi-net.jp )のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://iiyu.asablo.jp/blog/2007/01/06/1097181
Perlで高階プログラミング
で紹介し
Google
ブログ(iiyu.asablo.jpの検索)
ホットコーナー内の検索
 でもASAHIネット(asahi-net.or.jp)全体の検索です。
 検索したい言葉のあとに、空白で区切ってki4s-nkmrを入れるといいかも。
 例 中村(show) ki4s-nkmr

ウェブ全体の検索