2010-07-24
*1279982968*Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」がとても遅い件のまとめ
前日話の流れを時系列でまとめかけたけど、もはや情報量が多すぎて流れを追っていなかった人にとってはキャッチアップが困難かと思うので改めてまとめてみる。(情報量の多いほうがいい人はこちら: a href='http://d.hatena.ne.jp/nishiohirokazu/20100720/1279595270'続:Haskellのfibが遅い件/a)
Haskellでフィボナッチ数列を定義する方法としては
|haskell|
fib = 1:1:zipWith (+) fib (tail fib)
||
が有名であり、Wikipediaには「次の定義は線形時間でフィボナッチ数列のリストを生成する」と紹介されている。しかし、少なくとも n = 10000 ～ 300000 くらいの範囲ではO(n^2.6)くらいの計算時間が掛かっていて、事実に反する。 (グラフはこちら: a href='http://shinh.skr.jp/m/?date=20100719#p01'はじめてのにき(2010-07-19)/a)
2.6という値がどこから出てきたのか？これはGCにO(n^3)くらいの時間がかかっていて、それが小さい係数で本来の計算時間O(n^2)に混ざっているため、O(n^2.6)ぐらいに見えている。
なぜGCにO(n^3)ぐらいの時間がかかるのか？HaskellのGCは世代別GCであり、固定長のマイナーヒープがいっぱいになるとGCを始める。このとき、スタック上のオブジェクトはGCのルートとして使われるのでスタックの深さをmとしたときにO(m)の時間がかかる。今回のケースでは、スタックの深さをmとした場合にO(m)のメモリを確保するので、i回目のGCが起きたときの消費時間mは係数無視してi^0.5になり、これをiについて足しあわせるので積分してi^1.5になり、iがいくらまで増えるかというとメモリの消費量をマイナーヒープのサイズで割ったものだから係数無視してn^2なので、これを代入してn^3になる。というわけでGCの計算量はO(n^3)になる。
この挙動はGHC 6.10.1以前では再現しないので、6.10.2で行われたGCに関する修正(a href='http://hackage.haskell.org/trac/ghc/ticket/2747'#2747 (Excessive Memory Usage: space leak with foldl' on Integer) #8211; GHC/a)が原因と思われる。6.10.1ではnの2乗くらいのオーダーになるらしい。
また、「スタックの上に大量の巨大なIntegerがある状況」が問題を引き起こしているので、Haskellでも素朴に末尾再帰で書けばO(n^2)になる。計算順序によっても挙動が変わる(a href='http://d.hatena.ne.jp/mkotha/20100623/1277286946'無限リストを使っているfibでは30万番目を取るより30万番目までの和を取るほうが速い/a)し、評価戦略でも変わる(a href='http://d.hatena.ne.jp/kazu-yamamoto/20100624/1277348961'正格評価するzipWith'を作れば速い/a)
無限リストが絡むことで見かけが複雑になっているので、よりシンプルな「末尾再帰でない再帰呼び出しでnに比例して大きくなるメモリを確保しようとしたときにO(n ^ 2.6)の時間がかかる」事例(a href='http://d.hatena.ne.jp/nishiohirokazu/20100721/1279687613'Haskellで単にn回7を掛けるだけでもO(n ^ 2.6)の時間がかかる/a)を先に見たほうが分かりやすいのかも知れない
「Haskellが遅い」という主張にエアリーディングした人もいたようだが、あくまで「fib = 1:1:zipWith (+) fib (tail fib)が遅い(n = 100000ではPythonで素朴にループで書いたコードよりも！)」ということなので勘違いなさらないよう。実際最初のエントリーでも素朴な末尾再帰で書いて速くなってるわけだし。
こんな感じですかね。なんか間違っていたらご指摘よろしくお願いします。
*1279985270*今回の件で個人的に学んだことのまとめ
** gnuplotの使い方
- fit a*(x**b) data.txt via a, b
- plot a*(x**b) data.txt
- using (log ($1)):(log ($2))
- set log x
- unset log x
** GC
- GCは想像以上にいろいろな処理のオーダーに影響を与える
** 事実と解釈
他人と解釈が食い違う場合、特に自分がある事実Xを見て解釈している場合に、相手は事実を見ていないんじゃないか、と思い込みがちだが、別の事実Yを見ている可能性もある。非生産的な議論を避けるためには速やかに事実を共有する必要がある。
*1279985390*原稿をブログで書くメソッド
もうちょっと早く着手すべきだったなー。締切りを知った時点で締め切りが一週間後という。
公平性を重んじて偏りがないように慎重に書くよりも、炎上しそうなことを勢いで書いてしまって反論を受けて修正する方がスピードは速いわけだが、うむむ。
*1279999839*不完全にしてかなり言葉足らずな比較プログラミング言語学
プログラミング言語は人が作ったもの。人は誤るもの。なので完璧なプログラミング言語は存在しない。
「人は誤るもの、しかし誤りに固執するのは馬鹿の所業だ。」(キケロ) プログラミング言語も、間違った設計をして、馬鹿でない人がそれを修正することの繰り返しで発展してきた。
というわけで言語間での設計判断の食い違いとか失敗した設計とかを収集中。一部抜粋して講義資料に入れるつもりなので他の事例をご存知でしたらぜひ情報をいただけるとありがたいです。
** if(x = 0)
C言語では代入が式であるためif(x == 0)のつもりでif(x = 0)と書いてしまい、常に偽になってしまう。
- x = 0の値はint、条件式はboolでないといけないので型エラーだよ派: Java
- x = 0は式ではないので条件式に入れたら構文エラーだよ派: Python
- 条件式にx = 0をいれたらx == 0と解釈するよ派: HMMMML ((http://twitter.com/HomeiMiyashita/status/19575507867))
** 値渡し、参照渡し
C言語では関数を呼ぶ場合の引数の渡し方に、値渡ししかできなかった。変数のアドレスを取得し、それを値渡しし、呼び出し先でそのアドレスに間接アクセスすることで参照渡し風のことをすることができた。C++では呼び出し先で間接アクセスしないでいい参照渡しが導入された。
Javaでは「変数のアドレスを取得する方法」を取り除いた。オブジェクトへのアクセスはC++の参照のような見かけで、しかし関数に渡す際にはアドレスの値渡しで行う(参照の値渡し)とした。それで十分であった。非オブジェクト(プリミティブ型)は従来通り値渡しにした。
Pythonでは全てがオブジェクトのため、全てが参照の値渡しになった。整数や文字列などのプリミティブなものは変更不可能なオブジェクトにすることで「呼び出し先で破壊的変更を行うこと」を不可能にした。これによって参照が値渡しされていてもただの値渡しと同様になった。
** 値の範囲の定義
C言語では環境によって「intが何ビットであるか」などがまちまちのためプログラマに無駄な労力をさかせていた。Javaでは言語仕様としてintなどのプリミティブ型の大きさと値の範囲が定められている。
** 配列
Cの配列は長さを持たない。ただの「たまたま同じ型のデータが並んでいるメモリ領域の先頭へのポインタ」である。範囲外アクセスによる脆弱性の例は枚挙にいとまがない。Javaの配列は作成時点で長さが定められ、範囲外へのアクセスは例外を投げる。
Javaの配列はファーストクラスのオブジェクトであり、関数の引数にそれ単体で渡すことができる。
** 関数へのポインタ
Cは関数へのポインタを作成することが出来る。ポインタはファーストクラスのオブジェクトなので関数の引数に関数を渡すことが出来る。
Javaではそもそも関数がない。リフレクションによってメソッドオブジェクトを取得することは出来る。
C++では関数の呼び出しオペレータを定義したクラスを作ることが出来る。
LispやHaskellやPythonの関数はファーストクラスのオブジェクトであり、なんら気兼ねなく関数の引数に渡すことが出来る。
Pythonでも関数の呼び出しオペレータを定義したクラスを作ることが出来る。
** 関数呼び出しの括弧
関数(メソッド)の呼び出しに
- たとえ引数がなくても括弧が必要派: Python
- たとえ引数がなくても括弧が必要、ただし外側にな、派: Lisp
- 引数がないときだけ括弧を省略できるよ派: D (thanks id:Dubhead)
- 括弧はいらないよ派: Perl, Ruby
- 括弧はいらないよ、引数が0個の関数？なにそれ定数じゃん派: Haskell
- 括弧はいらないよ、引数が0個の関数？引数に()を渡せ派: OCaml
- 関数はおろか演算子の結合順序を変える括弧もいらないよ、(1 + 2) * 3 は 1 2 + 3 * って書けよ派: Postscript, Forth
- 演算子の結合順序？計算は左からって決めればいいじゃん 1 + 2 * 3でいいよ派: Smalltalk
- 演算は右から順だよ派: APL, J (thanks: straggler)
引数のない関数呼び出しに括弧がいらない、かつ関数がファーストクラスの言語では、逆に「その関数自体」を意味する式をつくるために新しい文法が必要になる。
たとえばPythonでこう書けるところを:
|python|
def foo():
... print foo!
...
bar = foo
bar()
foo!
||
Rubyではこう書く事になる
|ruby|
def foo
p foo!
end
= nil
bar = Object.method(:foo)
= #Method: Class(Object)#foo
bar.call
foo!
= nil
||
** 演算子オーバーロード
C++では演算子の多重定義が可能である。たとえば「+」が再定義できる。これは乱用するととても読みにくいコードになる。
Javaでは演算子の多重定義を許さないようにした。結果、独自定義のクラスについてx + yと書きたくてもx.add(y)と書かざるを得なくなり、プログラムの可読性を損ねる結果となった。
PythonやRubyなどでは再び演算子の多重定義を許している。乱用するなよ、みんな大人でしょ、というスタンスである。
** 多重継承
C++は任意のクラスを多重継承できる。これはたまたま同じシグニチャのメソッド実装が複数あった場合にどの実装が選ばれるのか、という問題を引き起こす。((a href='http://ja.wikipedia.org/wiki/%E8%8F%B1%E5%BD%A2%E7%B6%99%E6%89%BF%E5%95%8F%E9%A1%8C'菱形継承問題 - Wikipedia/a))
Javaは実装を持ったクラスの継承は1つまでとすることでこの問題を回避した。実装を持たないクラス(インターフェイス)はいくつでも継承できる。しかしこれは「複数のクラスから実装を引き継げない」という不便さと引換である。Javaではこういうシチュエーションで、もっぱら実装のあるクラスFooへの参照を持っておいて自分のbarメソッドが呼ばれたらFooのbarメソッドを呼んでそっちに処理を任せるという書き方をする。
Rubyは実装の継承を部分的に許すためにMix-inという概念を導入した。「インスタンスを作れず、クラスから継承もできない特殊なクラス」である「モジュール」をクラスに「混ぜ込む」構文を用意した。
Pythonは多重継承をサポートして、メソッドの解決順序の決定にC3-Linearizationっていう比較的自然な結果が得られやすいアルゴリズムを採用して、「まあ、多重継承を乱用すると悲惨なことが起こるってみんな知ってるでしょ、大人でしょ、これで普通は問題起きないでしょ」というスタンスである。((PEP 283 -- Python 2.3 Release Schedule http://www.python.org/dev/peps/pep-0283/))
PerlはPythonと同じC3を併用可能だった。Perl 6からはデフォルトがC3になっている。 (( http://perldoc.jp/docs/modules/mro-1.00/mro.pod ))
** GC
- GC必要でしょ、メモリのこと気にするのとかめんどくさいでしょ派: Lisp, Java, Python, Ruby, その他最近の言語のほとんど
- GCみたいなゆとりのための機能を入れて遅くなるとかありえん派: C
- GCみたいなゆとりのための機能を入れて遅くなるとかありえん、スマートポインタでだいたい用が済むだろ派: C++
- AutoreleasePoolでだいたい用は済むだろ、だけどやっぱりGCあった方が楽だよね派: Objective-C (thanks id:jmuk)
- 普通はGCを使うけど必要ならmalloc/freeもできるよ派: D (thanks id:Dubhead)
- リージョン推論（region inference）試してみたけれど、リージョン推論だけでは速度が出なかった。なので GC も使う派: Haskell (thanks id:shelarcy)
** 変数の初期化
- 初期化が必要なら必要なときにプログラマがやればいい。デフォルトでやるなどというゆとりのための機能で遅くなるとかありえん派: C, C++
- 初期化されていない(値がなんだかわからない)変数の存在は危険なバグのもとであり許してはいけない、勝手に初期化しよう派: Java, D (thanks id:Dubhead)
- っていうか値を代入することでしか変数を作れないので未初期化の変数とかありえないし派: Python
- 未定義の変数に謎の値が入ってるのがダメなんだよ、「未定義」って値を入れとけばいいじゃん派: JS
** グローバル変数
C言語はグローバル変数を定義できる。グローバル変数の乱用に起因する問題はプログラマの責任である。
Javaではグローバル変数を定義できない。もしどこからでもアクセス可能なグローバル変数的なものが必要であれば、クラス名がどこからでもアクセス可能なことを利用する、というトリックがやはり場合により乱用されて問題を起こしたり。
Pythonではグローバル変数を定義できるように見えるが、それはファイル単位のスコープである。グローバル変数を書き換えるには特別の「この関数はグローバル変数fooを書き換えるぞ」宣言が必要である。本当にどのファイルからでも参照できる変数が欲しければ__builtins__モジュールに動的に追加する。
** 整除の丸め方向
C, C++では整数の除算が割り切れなかった場合に0方向に丸めるのかマイナス無限大方向に丸めるのかが環境依存である。つまり、-1/2は0にも-1にもなりえる。
Javaでは常に0方向に丸める。C99も同様。
Haskellでは整数同士を「/」で除算することはできない。divとquotという二つの整除関数がありdivが-1, quotが0を返す。
** x / 0.0
x / 0.0 をエラーにすべきか否か
Ruby1.8ではNaNやInfinityにする。
Pythonでは例外を投げる。
** 0xxx型の8進法リテラル
|python|
1000 + 0100 + 0010 + 0001
1073
||
- 0100は64だよ派: Python2.*, Java, Scala
- 0o100と0O100は64だよ派: Python3.0, Haskell
Haskellの仕様を見て大文字のOを許容するとかダメだろ、と思ったらPython3.0でも同じだった
** long intのリテラルに小文字のエルを許す
大文字Oで思いついたので:
|python|
100l == 100
True
||
- Yes: Python2.6
- No: D (= 0.154 http://www.digitalmars.com/d/1.0/changelog2.html#new0154 ) thanks id:hzkr
** 整数演算の結果がintの範囲を超えたときに自動的に表現力の大きい型に変更する
Cで書かれたビット演算のコードとかを丸写しすると、「」で上位ビットが捨てられているようなところで長整数型に変わってしまって結果が合わないという罠。
しかし数値をビットの塊として認識していない人にとっては「人間の都合で上限が定められていて、それを超えても例外を投げるでもなく変な値になるってのはおかしい」という主張もまあ一理ある。
-上限のない整数になるべきだ派: Python、Ruby
-勝手に変換するのはよくない派: C, Java
-ていうか整数なんてないし派: JS
-そもそも上限のない方がデフォルトだし派: Haskell
** 変数への再代入を許すかどうか
- え、当然許すよ何言ってんの派: Python
- 定数はあったほうがいいよね。大文字で始まるのは定数。まあ再代入しても警告しか出さないけど派: Ruby
- 再代入させたくないものだけconstとかfinalとかつけたらいいじゃん派: C++, Java
- 変数への再代入なんて諸悪の根源だ派:
-- だから一切認めないッッ派: Haskell
-- でも完全に禁止すると実用的じゃないから書き込める場所を用意しましたor用意する方法を作りました派: Erlang, OCaml
** 演算子の優先順位について
Pascalでは加算演算子(+, -, orなど)は乗算演算子(*, /, andなど)より優先順位が低く、比較演算子(==, など)はさらに低い。つまり 「4 + 1 * 2 == 3 * 2」は「(4 + (1 * 2)) == (3 * 2)」と解釈される。これは自然。しかし「0 x and x 9」は「0 (x and x) 9」になってコンパイルエラー
他の多くの言語では条件演算子(and, or)が算術演算子(*, /, +, -など)より低い優先順位になっている。
C では x == y z が (x == y) z となる(thanks @mametter)
** 比較演算子の連続について
- 0 x x = 9とか頻出パターンだし複数の比較の連続で一つの式って構文にしようよ。 0 x = 9 って書けるよ派: Python
** 単項演算子のマイナス
Haskellでは「f -1」が「f - 1」と解釈されるので「f (-1)」と書かなければいけない。逆に演算子の部分適用で(/ 2)は「2で割る関数」になるが(- 1)は-1と解釈される。
SMLでは ~1、J言語では _1。
** ループ
- ループをするにはforとかwhileとかgotoとかいろいろな方法があるよ派: C
- gotoは悪だ、forとwhileだけでいいだろ派: Java
- 末尾再帰がジャンプに置き換えられるから再帰呼び出しでループするのもありだよ派: Lisp
- むしろループいらないよねmapとfoldlあるし派: Haskell
** 空リストの型
Cambridge LCF の MLではかつてlet x = ref [] で polymorphic な \forall a. a list ref が作れた
xにintの値を入れてからポインタとして取り出してアクセスすることができてしまう。
SML '97 Types and Type Checking http://www.smlnj.org/doc/Conversion/types.html
thanks id:camlspotter
** インデントと実際の構造の不一致
C言語では下のようにif文を書くことができる。
|c|
if (x 0)
when_x_is_positive();
||
x 0の時に別の処理を追加しようと考えてこんな書き方をしてはいけない
|c|
if (x 0)
when_x_is_positive();
another_task();
||
これは下のような意味であり、another_task()は常に実行される。
|c|
if (x 0) {
when_x_is_positive();
}
another_task();
||
また下のコードにもインデントと構造の不一致がある。
|c|
if (x 0)
if (y 0)
all_positive();
else
x_isnt_positive();
||
x == -1の時にx_isnt_positive()は呼ばれない。代わりにx == 1, y == -1の時に呼ばれる。このコードは下のような構造である。
|c|
if (x 0) {
if (y 0) {
all_positive();
} else {
x_isnt_positive();
}
}
||
Cではプログラマが気をつけるか、braces {}を付けろ＆正しくインデントしろというコーディング規約で回避する。
Rubyではendで閉じる。
Pythonでは発想を逆転してインデントをもとに構造を決める。下記のコードは見ためどおりに動く。
|python|
if x 0:
if y 0:
all_positive()
else:
x_isnt_positive()
||
QuickBASICやHMMMML(( http://miyashita.com/HMMMML.pdf ))では他の言語における「end」や「}」でのブロック終了がどのブロックの終了であるのか分かりにくい点を改善するため「If ~ End If」(QB)「lt;/if」(HMMMML)などを用いる。
** レシーバの受け取り方
obj.method(arg)的なコードを実行したときにmethodの中ではどうやってobjにアクセスするのかと言う話
- レシーバは明示的に仮引数として受け取る派: Python, C (thanks @mametter)
- メソッド内でanother_method()がobj.another_method()を意味しているのでレシーバを意識する必要はないけどレシーバ自体をどうこうしたい時にはthisに入っているよ派: Java
- レシーバ？それ単なる引数だろ、特別なものじゃないじゃん派: Common Lisp with CLOS, Haskell
** 文字列オブジェクトは破壊的に変更できるか？
- はい: Ruby, C++
- いいえ: Python, Java
- 文字列？なにそれ？char*のこと？: C
** 文字列と数値を自動変換するか？
PHPの場合
||
$ php -r 'print 1 + 2;'
3
$ php -r 'print 1 . 2;'
12
$ php -r 'print 1 . 2;'
12
$ php -r 'print 1 + 2;'
3
||
Perlも同じ
- 文字列と数値は自動的に変換するよ、だから文字列の結合と数値の足し算は別の演算子だよ派: Perl, PHP
- それは型エラーにするよ派: Python, Ruby
- 数値に限らずオブジェクトは自分の文字列化の方法を知っているはず(toString)だから文字列への変換はしてもいいんじゃない？派: Java
** 1/2は何になる？
- 整数の0だよ派: Python2.*, Ruby, OCaml
- 浮動小数点数の0.5だよ派: Python3.*
- 有理数の1/2だよ派: Scheme
- 念のために確認するとその1や2ってのは Int じゃなくて (Num a) = a だよな？だったら計算結果は(Fractional a) = a だな。これは浮動小数点数と有理数のどちらでもありうる型クラスで、どちらになるかは型推論で決まる。ちなみに推論によって決定できないときにはDefaultingと(省略されました。続きを読むにはa href=http://www.haskell.org/onlinereport/decls.html#sect4.3.4こちら/a): Haskell
- 数値はデフォルトでBigDecimalだよ派: Groovy
** オブジェクト指向
- データと手続きを分けて管理するのは面倒だから、ひとまとめにしたオブジェクトとかクラスとかあると幸せになるんじゃない？: Simula
- すべてはオブジェクトとその間のメッセージのやりとりで表現できるんだよ!メッセージ！メッセージ！: Smalltalk
- なにそれ遅い…: C
- ふむ、Simulaのクラスって概念はいいものだ。採用！要するにstructで既存の型を組み合わせて新しい型を作ってたのの延長で、そこに関数も組み合わせてひとかたまりにできればいいわけだよね。あ、あと継承ね。これも便利。採用！アクセス制限？ふむ、これもいれとくか。メッセージ？…なにそれおいしいの？: C++
- プログラミングとはクラスを定義してオブジェクトを作ることなんだよ！オブジェクト！オブジェクト！え？プリミティブ型はオブジェクトじゃないじゃんって？えっと、まあ、それはそのパフォーマンスのためとかさ（ごにょごにょ): Java
- じゃじゃーん、整数とかもオブジェクトにしたよ！プリミティブ型も自動でオブジェクトに変換するよ！オブジェクト！オブジェクト！: Java 5
- っていうか要するにデータを持っておくハッシュと、関数の入っているモジュールを貼り合わせる手段があればいいだけだよね: Perl
- そもそも関数がファーストクラスのオブジェクトならハッシュにだって入るじゃん。これでいいんじゃない？: JavaScript
- そもそも名前空間自体が辞書(ハッシュ)だよね。手軽に名前空間を作れて関数を入れられて、ついでに継承とかメソッドとインスタンスのバインディングとか便利な機能がついてくる！これでよし！: Python
- privateとかいらないよねー派: Perl, JavaScript, Python
- 世間のスクリプト言語がprivateを軽視しすぎ！許せん！派: Ruby
** 真偽値
- 真と偽の値はこちらが用意する。それ以外を条件式に入れたら型エラーだぞ派: Java, Haskell
- 0がfalse、それ以外は真だよ派: C
- #fが偽、それ以外は(0も)真だよ派: Scheme
- falseとnilが偽、それ以外は(0も)真だよ派: Ruby
- falseとnullとundefinedと0と空文字列とNaNが偽だよ: JavaScript
- FalseとNoneと0なオブジェクトと空のオブジェクトが偽だよ: Python (( http://www.python.jp/doc/2.4/lib/truth.html ))
** スコープ
- 静的スコープだよ、だって動的スコープとか大変じゃん派: ALGOL, C, Pascal
- 動的スコープだよ派: 初期のLisp, 初期のPerl
- 動的スコープと静的スコープ両方あるといいよね派: CommonLisp, Perl(my/local)
- Lispが動的スコープいれたのって失敗じゃない？派: Scheme, Python
- スコープ？なにそれおいしいの？: BASIC
** 配列の範囲外アクセス
- 何か適当なものを返す: Ruby(nil), JavaScript(undefined)
- 例外を投げる: Python, Java
- 死ぬかも知れない: C