Python とコピーコスト

python を覚えたので、最近はスクリプト言語に ruby じゃなくて python を使うようにしています。でも、本屋に行ってもあまりよさげな本がない。サイボウズラボの西尾さんの blog がなかなかいい tips を公開しているので、チェック。

さて、本題。

• 西尾泰和のブログ @ Cybozu Labs: Python2.4以降での高速なソート

sort に comparator を渡せるのは、いかにも関数型的要素をたくさんとりいれんとする python 的である。それはさておき、こういう風に一時的に配列のコピーをとっても実行時間に差はないよという指摘は、結構大事だと思う。C++ なんかで戻り値を vector にしても、どうせその vector の生成に O(n) かかってるんだから、コピーコストなんてたいしたことないでしょ！なんてことをよくいってますが、特にこのケースの場合だと O(n log n)なのでなおさら。問題があるとすれば、この n が実は 2GB でしたとかそういうときだろうか。