OCaml 標準ライブラリ探訪 #2 List : スタックと計算量に注意 - Oh, you `re no (fun _ → more)
理解も出来ない上に試して実感もしない、という方は関数型言語は使わないで 配列しかない言語を使った方がお互いのためだと思います。さようなら。
出会ったばかりでさようならも悲しすぎるので、試してみます。
でもOcamlってやったことないので、今勉強中のErlangでやってみます。
コード
%% Author: Ehren %% Created: 2009/11/02 -module(new_file). %% %% Exported Functions %% -export([dame_rev/1,rev_iter/2]). %% %% 再起で実装 dame_rev([]) -> []; dame_rev([H|T]) -> dame_rev(T) ++ [H]. %% 反復で実装 rev_iter([],L) -> L; rev_iter([H|T],[]) -> rev_iter(T,[H]); rev_iter([H|T],L) -> rev_iter(T,[H] ++ L).
計測方法
いい機会なのでErlangの時間計測方法を調べた。↓の情報を発見！
kamonama@Blogger: Erlangで関数の実行にかかった時間を計るには
出力は、{ かかった時間[microsec]、関数の出力 }
実行結果*1
Eshell V5.7.3 (abort with ^G)
(spm@random)3> Seq=lists:seq(1,100000).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29|...]
(spm@random)4> timer:tc(lists,reverse,[Seq]).
{1,
[100000,99999,99998,99997,99996,99995,99994,99993,99992,
99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,
99981,99980,99979,99978,99977,99976,99975,99974|...]}
(spm@random)5> timer:tc(new_file,dame_rev,[Seq]).
{131578000,
[100000,99999,99998,99997,99996,99995,99994,99993,99992,
99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,
99981,99980,99979,99978,99977,99976,99975,99974|...]}
(spm@random)6> timer:tc(new_file,rev_iter,[Seq,[]]).
{15000,
[100000,99999,99998,99997,99996,99995,99994,99993,99992,
99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,
99981,99980,99979,99978,99977,99976,99975,99974|...]}再帰は時間がかかる。これは「SICP 1.2.3増加の程度」にも出てくるようにステップ数が列の長さに比例して増えることが原因なのかなと思う。
実際に反復で書き直すとかなり高速化される。(大体8000倍程度速くなる計算)
そして標準ライブラリ早い！100000要素のリスト渡して、1マイクロ秒ってすごすぎ。
標準ライブラリはパフォーマンスも含めてよく考えられていることがわかります。
参考
- 反復的プロセス、末尾再帰、継続渡しスタイル : torus solutions!
- 反復バージョンを書く際に参考にしました。Schemeですが。。
- bif 一覧 - いたわさににほんしゅ
- どうやら標準ライブラリはいろいろ考えられている様子。
