No Such Blog or Diary

フィボナッチ数の計算で C の 70倍遅いとかいうことを聞いて，何となく今までの体感と違かったので手元で測ってみた．PyPy だけど．

プログラム達：

#include
int fib(int n) {
	if(n  <= 1) return 1;
	return fib(n-1)+fib(n-2);
}
int main(int argc, char *argv[])
{
	printf("%d\n", fib(42));
	return 0;
}

def fib(n):
	if n  <= 1:
		return 1
	else:
		return fib(n-1)+fib(n-2)
print(fib(42))

結果：

hogehoge:~/work/pypytest$ gcc -O3 -o fib fib.c
hogehoge:~/work/pypytest$ time ./fib
433494437
 
real    0m0.902s
user    0m0.900s
sys    0m0.000s
hogehoge:~/work/pypytest$ time pypy fib.py
433494437
 
real    0m9.285s
user    0m9.240s
sys    0m0.044s 

もう一回：

hogehoge:~/work/pypytest$ time ./fib
433494437
 
real    0m0.883s
user    0m0.880s
sys    0m0.000s
hogehoge:~/work/pypytest$ time pypy fib.py
433494437
 
real    0m9.429s
user    0m9.372s
sys    0m0.056s 

10倍？　大体このくらいな気がする．

それぞれの --version の結果：

gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
Python 2.7.10 (5.1.2+dfsg-1~16.04, Jun 16 2016, 17:37:42)
[PyPy 5.1.2 with GCC 5.3.1 20160413]

Python のライブラリの NetworkX が実験用のグラフをちょちょいと生成しようと思った時に便利だった．よくある生成の仕方に対して各種生成器が提供されているので．あとは目的の形にファイルに書き出すスクリプトを書いてあげれば OK．

インストールも pip で入るので楽．cygwin でも OK だった(setuptools 入れて easy_install pip して)．

どこまで大きなサイズまで実用できるのかはわからないけれど．

幾つかの言語で 0.5, 1.5, 2.5, 3.5, 4.5 を round 関数を使って丸めてみる．

C: 1, 2, 3, 4, 5 （直感的な四捨五入）

Java: 1, 2, 3, 4, 5 （直感的な四捨五入）

Haskell: 0, 2, 2, 4, 4 （偶数しか出てこない……）

ということで，Haskell は X.5 の時には偶数に丸めてくれるらしい．累積誤差を小さくできるとかで銀行で好まれるとか．Haskell は銀行に優しいのかもしれない．

これを知らずに微妙にハマった．

普通の Haskell ソース(.hs) だと下のような {-# LANGUAGE ... #-} をファイルの頭に書くのだけど，.lhs でそのまま同じに書いといたら ghc が認識してくれなくて困った．

{-# LANGUAGE FlexibleInstances,MultiParamTypeClasses,FunctionalDependencies #-}

で，{- -} がコメントだから，コメントがデフォルトになってる Literate Haskell では # LANGUAGE ... # と書くのか？　とかアホなことをしつつ，最終的にプラグマはプログラムの一部なんだから頭に > つけなきゃ認識されないよなとかいうことを理解した．

ということで，こう書けばよかった：

> {-# LANGUAGE FlexibleInstances,MultiParamTypeClasses,FunctionalDependencies #-}

今まで Literate Haskell でプラグマが必要なプログラムなんか書いてなかったのでアホなことに躓いた．

Hackage は基本的に「テストしたバージョンまでで依存パッケージのバージョン上限を設けとけよ」的なノリなので，実際には問題ないんだけど上限よりも上のバージョンの依存パッケージしか入れられないから目的のパッケージがインストール出来ない，とかいう状況がチラホラある．バージョン上限を書き換えるためだけにデプロイやり直すのも作者が面倒だろうし．

んで，この状況にハマった時には目的のパッケージのソースを持ってきて手動でコンパイルするかとかやってたのだけど，cabal install のヘルプを良く見てみたら --allow-newer とかいう便利なオプションがあることに（今更ながら）気づいた．これつけとくとバージョン上限を無視してくれる．ほんと便利．

閑話休題．

cabal install を使った時とパッケージのソースで runghc Setup.hs configure とかやった時とでオプション無しの時の振る舞いが異なっていてハマった．cabal install がデフォルトでユーザ個別にパッケージをインストールをする（--user オプションがデフォルト？）のに対して，手元に持ってきたパッケージで runghc Setup.hs configure とかやった時にはグローバルにインストールされたものを探しに行っていた（--global オプションがデフォルト）．おかげで入れたはずのパッケージが見つからないと怒られて，でも ghci で確かめると普通に import できて，何がおかしいのか暫く悩みまくった． runghc Setup.hs configure --verbose=3 とかやったら ghc-pkg を呼ぶときに --global をつけているのが見えて分かったのだけど，ここらのデフォルトの違いはどこから出てきたのやら．

リストの長さを意味する述語 p を作ろうかと思った人が次のコードを書いた．空リストの長さはゼロという意味で．

p([],O).

そして p([],N). とやって，N = 0 と返ってくることを期待してみると……

?- p([],N).
true.

期待と違う答えが返ってくる．何故だ……

ということで，このコードのデバッグに結構時間を食った．実際には元のプログラムはもう少し大きかったのだけど，本質的には上のコードのバグ探し．

んで，デバッグ後のコードは次のとおり．

p([],0).

つまり，大文字の O（オー）と 0（ゼロ）を間違えて書かれていたことに気が付かなかったというオチ．本人が最終的に気づいたので解決したけれど，本人がその場に居なかったら誰も気づかずにさらなる時間を無駄にしたに違いない．

まあ，紛らわしいフォントを使うのが悪い．プログラミングに使うって分かってんだから .emacs のひな形にプログラミングしやすいフォントを指定するよう書いておけばいいのに（学生が演習で使う端末室の計算機なのだから）．

閑話休題．

O と 0 を書き間違えても正しいコードになるってのは高級言語ならではの面倒さかね．C言語やJavaではコンパイルエラー一発でしょう．