うわっ…pythonのdeepcopy、遅過ぎ…？
最近、アルゴリズムの勉強をしようと「プログラマ脳を鍛える数学パズル」という本をやっています。
CodeIQの「今週の問題」というコーナーの出題を集めたものです。
ついでにCodeIQにも登録して、最新の今週の問題も平行してやり始めたのですが、ある問題をpythonで再帰を使って解いたところ、高々10万回程度の計算なのに実行時間が数十秒かかるようになってしまいました。
どうやら再帰しているメソッドに渡している、2次元配列をdeepcopyしているのが原因だったようです。
そもそも2次元配列を再帰で渡さないといけないルゴリズムがよくない気もしますが、あまりに遅くてびっくりしたので、ちょっと速度を計ってみました。
配列のcopyの速度計測
pythonの配列のコピー速度
pythonでは通常の配列のコピー(shallow copy)はarr[:]といったスライス操作で行います。
2次元配列をただコピーすると、中身が一緒の配列になってしまいますが、copy.deepcopyを使うと中身までちゃんとコピーしてくれます。
問題で使っていたのは5*3のbooleanの2次元配列です。
これを
i)copy.deepcopyを使った場合 : copy.deepcopy(arr)
ii)サイズ15の１次元配列をスライス操作でコピーした場合 : arr2[:]
iii)2次元配列をshallow copyを繰り返して手動deepcopyした場合 : [i[:] for i in arr]
の3つを10万回やった場合の速度を計ってみました。
import timeit import time print(timeit.timeit(stmt='copy.deepcopy(arr)',setup='import copy; arr=[[False for j in range(3)] for i in range(5)];',number=100000,timer=time.clock)) print(timeit.timeit(stmt='arr2[:]',setup='arr2=[False for i in range(15)]',number=100000,timer=time.clock)) print(timeit.timeit(stmt='[i[:] for i in arr]',setup='arr=[[False for j in range(3)] for i in range(5)];',number=100000,timer=time.clock))
結果(python 2.7)
i)2.29
ii)0.02
iii)0.08
うわっ…pythonのdeepcopy、遅過ぎ…？
なんとdeepcopyだと同じサイズの１次元配列のコピーの100倍遅くなりました。
メモリが連続してないので、１次元配列と比べて2次元配列のコピーが遅くなるのは当然ですが、手動コピーと比べても遅すぎですね。
結果(python 3.5)
python3でもやってみました。
i)2.5700000000000003
ii)0.009999999999999787
iii)0.11000000000000032
うわっ…python3のdeepcopy、遅過ぎ…？
だいたい似たようなかんじです。
考察
深いコピー操作には、しばしば浅いコピー操作の時には存在しない 2 つの問題がついてまわります:
- 再帰的なオブジェクト (直接、間接に関わらず、自分自身に対する参照を持つ複合オブジェクト) は再帰ループを引き起こします。
- 深いコピーでは、何もかも をコピーするため、例えば複数のコピー間で共有されるべき管理データ構造までも、余分にコピーしてしまいます。
deepcopy() 関数では、これらの問題を以下のようにして回避しています:
- 現在のコピー過程ですでにコピーされたオブジェクトからなる、”メモ” 辞書を保持します; かつ
- ユーザ定義のクラスでコピー操作やコピーされる内容の集合を上書きできるようにします。
とあります。
deepcopyで問題を起こさないよう色々やってて遅くなってるということでしょうか。(適当)
高々2次元配列程度に使うのはオーバースペックなのかもしれません。
rubyの場合
せっかくなのでrubyでもやってみました。
rubyでdeepcopyをする場合は、一度シリアライズして戻すというのが一般的なようです。
いかにも遅そうなかんじですが、どうなるでしょうか？
i)シリアライズして戻した場合 :Marshal.load(Marshal.dump(arr))
ii)サイズ15の１次元配列をcloneでコピーした場合 : arr2.clone
iii)2次元配列をshallow copyを繰り返して手動deepcopyした場合 : arr.map{|x| x.clone}
require 'benchmark'
arr=Array.new(5){ Array.new(3,false) }
arr2=Array.new(15,false)
puts Benchmark::CAPTION puts Benchmark.measure{ 100000.times{|i| Marshal.load(Marshal.dump(arr)) } }
puts Benchmark.measure{ 100000.times { arr2.clone } }
puts Benchmark.measure{ 100000.times { arr.map{|x| x.clone} } }
結果
user system total real
0.490000 0.000000 0.490000 ( 0.488846)
0.030000 0.000000 0.030000 ( 0.030627)
0.200000 0.000000 0.200000 ( 0.201839)
iii)の手動コピーよりは遅いですが、まあリーズナブルな結果ではないでしょうか。
もしかしてpythonでもシリアライズしてもどした方が、早いんじゃなかろうか？
まとめ
pythonのdeepcopyはかなり遅いので反復して使うのは避けた方がよい。
2次元配列程度をコピーしたい場合は手動でコピーした方が10倍以上早い。