Pythonのパフォーマンス測定

setはそもそもが常にユニーク判定が必要なのでデータの検索は速いデータ構造です。 hashmapのようなアルゴリズムでO(1)に近いデータの存在チェックができるのは、まぁそうだろうなと理解はしていました。

だがしかし、10万個の要素から10万回存在チェックすると思いのほか差が大きい。

listはsetよりかなり遅い、そしてarray.arrayがlistよりもさらに遅い。

array.arrayは'i'を指定してintが格納されることを宣言しています。

setはhash計算で格納場所を決めると思っていて、だとすると要素の数が多い場合かつ徐々に要素を追加していくと格納先のサイズが拡張されて再計算のためにrehashがたくさん走るんじゃないかと思ったりしたのですが、そんなに変わりませんでした。

• for

  forでloopを回して追加する方式で生成

• Comprehension

  リスト内包表記やセット内包表記で生成

• convert from list Comprehension

  setに徐々に要素を追加していくよりlistを生成してから一気にsetを生成

その昔Javaでコレクションを使うときにはイニシャルと増分のキャパシティを指定したりしてた気がするのだけれど、そういう時代じゃないんですかね？特にHashMapとかの場合は結構気を使って気がするんですが。

cProfileは今回何がどれだけ呼び出されているかは明らかなのであまり有用ではなく。GitHubの方に結果を貼ってあるので気になる人はそちらで。

line_profilerで行ごとの実行回数や処理時間を確認します。

  Timer unit: 1e-06 s

  Line #      Hits         Time  Per Hit   % Time  Line Contents
  ==============================================================
      12                                           @profile
      13                                           def proc():
      14         3          9.0      3.0      0.0      cnt = 0
      15         3    1558856.0 519618.7      0.4      data = create_data()
      16    300003     205982.0      0.7      0.0      for i in range(100000):
      17    300000  441637215.0   1472.1     99.6          if randint(1, 10000000) in data:
      18      3039       3107.0      1.0      0.0              cnt += 1

  Timer unit: 1e-06 s

  Line #      Hits         Time  Per Hit   % Time  Line Contents
  ==============================================================
      11                                           @profile
      12                                           def proc():
      13         3          8.0      2.7      0.0      cnt = 0
      14         3    1593041.0 531013.7     48.2      data = create_data()
      15    300003     114824.0      0.4      3.5      for i in range(100000):
      16    300000    1596492.0      5.3     48.3          if randint(1, 10000000) in data:
      17      2936       1242.0      0.4      0.0              cnt += 1

  Timer unit: 1e-06 s

  Line #      Hits         Time  Per Hit   % Time  Line Contents
  ==============================================================
      13                                           @profile
      14                                           def proc():
      15         3          5.0      1.7      0.0      cnt = 0
      16         3    1586118.0 528706.0      0.2      data = create_data()
      17    300003     200262.0      0.7      0.0      for i in range(100000):
      18    300000  873139503.0   2910.5     99.8          if randint(1, 10000000) in data:
      19      2905       2835.0      1.0      0.0              cnt += 1

memory_profilerで行ごとにどのくらいメモリの増減があるか見ていきます。

  Line #    Mem usage    Increment   Line Contents
  ================================================
       5   35.980 MiB   35.980 MiB   @profile
       6                             def create_data():
       7   35.980 MiB    0.000 MiB       l = list()
       8   41.668 MiB    0.000 MiB       for i in range(100000):
       9   41.668 MiB    0.699 MiB           l.append(randint(1, 10000000))
      10   41.668 MiB    0.000 MiB       return l

  Line #    Mem usage    Increment   Line Contents
  ================================================
       5   35.984 MiB   35.984 MiB   @profile
       6                             def create_data():
       7   41.645 MiB    0.699 MiB       return [randint(1, 10000000) for i in range(100000)]

Line #    Mem usage    Increment   Line Contents
================================================
     5   36.062 MiB   36.062 MiB   @profile
     6                             def create_data():
     7   36.062 MiB    0.000 MiB       s = set()
     8   45.277 MiB    0.000 MiB       for i in range(100000):
     9   45.277 MiB    4.000 MiB           s.add(randint(1, 10000000))
    10   45.277 MiB    0.000 MiB       return s

  Line #    Mem usage    Increment   Line Contents
  ================================================
       5   36.094 MiB   36.094 MiB   @profile
       6                             def create_data():
       7   45.312 MiB    4.000 MiB       return {randint(1, 10000000) for i in range(100000)}

  Line #    Mem usage    Increment   Line Contents
  ================================================
       5   36.047 MiB   36.047 MiB   @profile
       6                             def create_data():
       7   47.770 MiB    6.043 MiB       return set([randint(1, 10000000) for i in range(100000)])

  Line #    Mem usage    Increment   Line Contents
  ================================================
       6   36.051 MiB   36.051 MiB   @profile
       7                             def create_data():
       8   36.059 MiB    0.008 MiB       a = array('i')
       9   36.484 MiB    0.000 MiB       for i in range(100000):
      10   36.484 MiB    0.070 MiB           a.append(randint(1, 10000000))
      11   36.484 MiB    0.000 MiB       return a

  Line #    Mem usage    Increment   Line Contents
  ================================================
       6   36.109 MiB   36.109 MiB   @profile
       7                             def create_data():
       8   41.797 MiB    0.699 MiB       return array('i', [randint(1, 10000000) for i in range(100000)])

だいたい思っていた通りなのだけれど次のような感想を得られた。

• ループが思ったより遅い

• 要素の多いsetを作っても思ったほど遅くない

• メモリ使用量は、へー、という感じ

• array.array遅すぎだろ、そしてメモリは謎い

そしてsetに関して、以下は感覚的にわかるのだけれど。

• setは通常はO(1)

• ハッシュ衝突時には最悪O(n)になる

ハッシュ衝突のあたりのコードとかアルゴリズムとか知らないので勉強が必要。

そもそもhashmapのアルゴリズムとか、10年くらい前にLightCloudチラ見してたときに出くわしたConsistent Hash Ringのイメージくらいしかなくて、Pythonのhashmap的なものがどういう設計なのかもわかってない。

次はdisモジュールでちゃんと確認しよう。