その演算って遅くない？

その演算って遅くない？（最終更新：2003年9月16日）

常日頃より「Pythonは遅い」と言われているわけですが、コードの書き方によってもずいぶん速度が異なるものです。ここでは、私が実際に仕事で使っていて気づいたことを書きます。

浮動小数点数の2乗編
以下のコードを実行してみてください。
```
import time
import math

N = 1000000
a = math.pi

def aa():
  start = time.time()
  for i in xrange(N):
    a ** 2
  t = time.time() - start
  print 'aa: Time= %f\n' % t
  return t

def bb():
  start = time.time()
  for i in xrange(N):
    a * a
  t = time.time() - start
  print 'bb: Time= %f\n' % t
  return t

def cc():
  start = time.time()
  for i in xrange(N):
    math.pow(a, 2)
  t = time.time() - start
  print 'cc: Time= %f\n' % t
  return t


if __name__ == '__main__':
  out = []
  out.append(aa())
  out.append(bb())
  out.append(cc())
  minval = min(out)
  print 'aa : bb : cc = %f : %f : %f\n' % (out[0]/minval, out[1]/minval, out[2]/minval)
```
ご覧の通り、これは円周率の2乗を100万回実行する関数が3つ、それぞれ別の演算方法で記述してあるコードです。結果はどれも同じですが、実行時間に以下のような差が出てきます。
```
C:\TEMP>python t1.py
aa: Time= 1.302000

bb: Time= 1.032000

cc: Time= 3.936000

aa : bb : cc = 1.261628 : 1.000000 : 3.813954
```
上記の結果の動作環境はPentiumIII 1GHz、メモリ512MBのWindows2000Pro上のActivePython 2.11ですが、PentiumPro 233MHz×2、メモリ128MBのSolaris8 Intel版上のPython2.1（gcc2.95.2でコンパイル）の上でも概ね似た結果が出ています。（無論実行時間の差はありますが、実行時間の比は似た傾向が出た）以上の結果から、浮動小数点数を2乗するときは n**2 演算を行うよりも n * n 演算を行う方が速度的に有利、math.powはこの用途では使わない方がいい、ということになります。

以下のコードを実行してみてください。


import time

N = 50
group = \
  (0, 48, 54, 87, 141, 156, 192, 201, 255, 279, 282, 333, 432, 450, 483, \
  525, 531, 618, 636, 714, 759, 765, 780, 804, 873, 888, 918, 939, 942, \
  969, 984, 1050, 1101, 1107, 1110, 1137, 1140, 1146, 1206, 1269, 1323, \
  1377, 1491, 1683, 1704)

def aa():
  start = time.time()
  for j in xrange(N):
    out = []
    for i in xrange(1705):
      if not i in group:
        out.append(i)
    t = time.time() - start
  print 'aa: Time= %f\n' % t
  return t

def bb():
  start = time.time()
  for j in xrange(N):
    d_group = {}
    for n in group:
      d_group[n] = 1
    out = []
    for i in xrange(1705):
      if not d_group.has_key(i):
        out.append(i)
  t = time.time() - start
  print 'bb: Time= %f\n' % t
  return t

if __name__ == '__main__':
  out = []
  out.append(aa())
  out.append(bb())
  minval = min(out)
  print 'aa : bb = %f : %f\n' % (out[0]/minval, out[1]/minval)

このコードには、0～1704の間の整数、かつタプルgroupに含まれない数の集合を求める関数を記述しています。関数aaでは単純にメンバシップのテストを行うためにin演算子を使っています。
一方関数bbでは、タプルgroupをそのまま使わずに、まずgroupの各値をキーとして持つ辞書を作り（キーが存在することのみが重要。値自体はどうでもよい。）、その辞書のhas_keyメソッドをメンバシップのテストに使っています。
実行結果は以下の通りです。


C:\TEMP>python t2.py
aa: Time= 1.172000

bb: Time= 0.330000

aa : bb = 3.551514 : 1.000000

比較対象のシーケンスが大きくなるとinは遅くなるだろうと思っていましたが、ここまで差が出るとは思いませんでした。おまけに、上記のコードでは関数bbでは比較用の辞書をループ毎に作り直しています！それでも、この差が出てしまいます。

Numericのconcatenate

Numerical Pythonをよく使います。
Numericのarrayは、arrayのままsinやcosなどといった演算が行える等いろいろ便利で助かるのですが反面リストと違ってarrayとarrayを連結するのに＋は使えません。（当たり前ですよね。arrayでは各要素同士の加算ですから。） arrayとarrayを連結する場合にはconcatenateを使うのが一番手っ取り早いわけですが、実は...
以下のコードを実行してみてください。


from Numeric import *

def aa():
  a = range(1000)
  for n in range(1000):
    a[n] = arange(n*1000, (n+1)*1000, typecode=Float)
  return a

def b1():
  a = aa()
  b = array([], Float)
  for n in range(len(a)):
    b = concatenate((b, a[n]))
  return b

def b2():
  a = aa()
  b = zeros(1000*1000, Float)
  idx = 0
  for n in range(len(a)):
    b[idx:idx+len(a[n])] = a[n]
    idx = idx + len(a[n])
  return b

def b3():
  a = aa()
  b = array([], Float)
  idx = 0
  for n in range(len(a)):
    b.resize(len(b) + len(a[n]))
    b[idx:idx+len(a[n])] = a[n]
    idx = idx + len(a[n])
  return b

if __name__ == '__main__':
  import profile
  print 'Executing "profile.run(\'z1 = b1()\')"'
  profile.run('z1 = b1()')

  print 'Executing "profile.run(\'z2 = b2()\')"'
  profile.run('z2 = b2()')

  z3 = z1 - z2
  if min(z3) == 0.0 and max(z3) == 0.0:
    print 'z1 and z2 are the same.\n'
  else:
    print 'z1 and z2 are different.\n'

実行結果は、これ。


C:\TEMP>python t3.py
Executing "profile.run('z1 = b1()')"
         1004 function calls in 80.956 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.006    0.006   80.928   80.928 :1(?)
     1000   79.928    0.080   79.928    0.080 Numeric.py:229(concatenate)
        0    0.000             0.000          profile:0(profiler)
        1    0.028    0.028   80.956   80.956 profile:0(z1 = b1())
        1    0.122    0.122    0.122    0.122 zzz.py:3(aa)
        1    0.872    0.872   80.922   80.922 zzz.py:9(b1)


Executing "profile.run('z2 = b2()')"
         4 function calls in 0.345 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.006    0.006    0.344    0.344 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.345    0.345 profile:0(z2 = b2())
        1    0.212    0.212    0.338    0.338 zzz.py:16(b2)
        1    0.127    0.127    0.127    0.127 zzz.py:3(aa)


z1 and z2 are the same.

この例では、実に235倍遅い！な、なんと0.4秒かからない演算がconcatenateを使うと80秒以上のかかってしまうのです！
よって予め大きさがわかっているarrayを単に連結するだけなら、かつarrayが結構大きいなら、concatenateは使うべきではなーい、というのが結論です。

リストの演算で + は遅い！

リストってmutableなので、いつでも要素を書き換えたり追加したりできて便利ですよね。でも使い方をよく考えないと、えらく遅いコードが書けてしまいます。
例えば + 演算子。リストに要素を追加する場合や、リスト同士の連結を行う場合に使えますが、以下のコードをお試しあれ。


def a1():
  a = []
  for n in range(10000):
    a = a + [n]
  return a

def a2():
  a = []
  for n in range(10000):
    a.append(n)
  return a

def b1():
  a = []
  for n in range(100):
    b = range(n*100)
    a = a + b
  return a

def b2():
  a = []
  for n in range(100):
    b = range(n*100)
    a.extend(b)
  return a

if __name__ == '__main__':
  import profile

  print 'リストにスカラ要素を追加'
  print 'Executing "profile.run(\'z1 = a1()\')"（+を使用）'
  profile.run('z1 = a1()')
  print 'Executing "profile.run(\'z1 = a2()\')"（appendを使用）'
  profile.run('z2 = a2()')

  if z1 == z2:
    print 'z1 and z2 are the same.\n'
  else:
    print 'z1 and z2 are different.\n'

  print '--------\n'

  print 'リストにリストを連結'
  print 'Executing "profile.run(\'y1 = b1()\')"（+を使用）'
  profile.run('y1 = b1()')
  print 'Executing "profile.run(\'y2 = b2()\')"（extendを使用）'
  profile.run('y2 = b2()')

  if y1 == y2:
    print 'y1 and y2 are the same.\n'
  else:
    print 'y1 and y2 are different.\n'

実行結果でーす。


C:\Temp>python z4.py
リストにスカラ要素を追加
Executing "profile.run('z1 = a1()')"（+を使用）
         3 function calls in 1.644 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.469    1.469 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.174    0.174    1.644    1.644 profile:0(z1 = a1())
        1    1.469    1.469    1.469    1.469 z4.py:1(a1)


Executing "profile.run('z1 = a2()')"（appendを使用）
         3 function calls in 0.016 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.015    0.015 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.016    0.016 profile:0(z2 = a2())
        1    0.015    0.015    0.015    0.015 z4.py:7(a2)


z1 and z2 are the same.

--------

リストにリストを連結
Executing "profile.run('y1 = b1()')"（+を使用）
         3 function calls in 4.617 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    4.616    4.616 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    4.617    4.617 profile:0(y1 = b1())
        1    4.615    4.615    4.615    4.615 z4.py:13(b1)


Executing "profile.run('y2 = b2()')"（extendを使用）
         3 function calls in 0.462 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.460    0.460 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.002    0.002    0.462    0.462 profile:0(y2 = b2())
        1    0.459    0.459    0.459    0.459 z4.py:20(b2)


y1 and y2 are the same.

ちょっとオクサマぁ。ごらん遊ばせ。
この例では要素の追加にappendメソッドではなく + を使うと100倍遅い！
またリスト同士の連結にextendメソッドではなく + を使うと、これまた10倍遅い！
追加するものがスカラ値かリストかを気にしないで使える + 演算子はある意味便利ではあるのだけれど、でもループ内に置いたりするとえらく遅くなってしまうので要注意ですぞ。

文字列演算も + は遅い！

Pythonの文字列演算ではperlなんかと違って + で連結ができるので表記上も自然だし、ついつい多用してしまいますよね。でも使う場所によっては、結構な処理時間をかけてしまうこともあるようですよ。
以下のコードを実行してみてください。


LOOP = 2048

def f1():
  ss = ''
  r = ord('A')
  for n in range(LOOP):
    ss = ss + chr(n % 26 + r) * 1024
  return ss

def f2():
  t = []
  r = ord('A')
  for n in range(LOOP):
    t.append(chr(n % 26 + r) * 1024)
  return ''.join(t)

if __name__ == '__main__':
  import profile

  print '文字列の連結'
  print 'Executing "profile.run(\'r1 = f1()\')"（そのまま + を使用）'
  profile.run('r1 = f1()')
  print 'Executing "profile.run(\'r2 = f2()\')"（リストを使用）'
  profile.run('r2 = f2()')

  if r1 == r2:
    print 'r1 and r2 are the same.\n'
  else:
    print 'r1 and r2 are different.\n'

実行結果でーす。



c:\users\futot>python z5.py
文字列の連結
Executing "profile.run('r1 = f1()')"（そのまま + を使用）
         3 function calls in 29.074 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   28.901   28.901 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.173    0.173   29.074   29.074 profile:0(r1 = f1())
        1   28.901   28.901   28.901   28.901 z5.py:3(f1)


Executing "profile.run('r2 = f2()')"（リストを使用）
         3 function calls in 0.137 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.136    0.136 :1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.137    0.137 profile:0(r2 = f2())
        1    0.134    0.134    0.134    0.134 z5.py:10(f2)


r1 and r2 are the same.

うわ、驚きの結果！
なんと200倍以上の差が出た。リストを使う方法では、最後にひとつの文字列にするためにjoin使っているにもかかわらず、この差が出ました。
こういうところを気をつけて使わないと、やっぱPythonて遅いんだよね～とか言われちゃいますね。