Pythonのパフォーマンス測定

2019/07/16 09:15

cover

休み中にlistとsetのパフォーマンスについての話が流れてきたので少し気になったところを確認してみました。

コードや詳細は GitHubのリポジトリに あります。

Pythonでパフォーマンスを計測するときのお約束的な以下の4つで見ていきます。

※ Python3.7でline_profilerの2.1.2がインストールできなかったので line_profilerのREADME を見て書かれてる通りにインストールしました

データの存在チェック

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

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

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

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

data structure

loop

time

script

list

for

450.540

append_to_list_with_loop.py

list

Comprehension

456.691

append_to_list_with_comp.py

set

for

0.909

add_to_set_with_loop.py

set

Comprehension

0.889

add_to_set_with_comp.py

set

convert from list Comprehension

0.889

add_to_set_with_comp.py

array

for

873.938

append_to_array_with_loop.py

array

Comprehension

867.495

append_to_array_with_comp.py

データ生成

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

data structure

loop

time

script

list

for

0.251

append_to_list_with_loop.py

list

Comprehension

0.220

append_to_list_with_comp.py

set

for

0.259

add_to_set_with_loop.py

set

Comprehension

0.237

add_to_set_with_comp.py

set

convert from list Comprehension

0.237

add_to_set_with_comp.py

array

for

0.257

append_to_array_with_loop.py

array

Comprehension

0.227

append_to_array_with_comp.py

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

呼び出し回数など

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

行ごとの実行時間など

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

append_to_list_with_loop.py

17行目、listから要素の検索でほぼ全ての時間を使っています。

  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

add_to_set_with_loop.py

14行目のデータ生成と17行目のsetから要素の検索のトータル時間がほぼ同じになっています。

  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

append_to_array_with_loop.py

18行目、array.arrayからの要素の検索はとても遅くlistの2倍近い時間がかかっています。

  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で行ごとにどのくらいメモリの増減があるか見ていきます。

append_to_list_with_loop.py

listの場合は10万要素で0.7MiBくらい増加します。1要素7byteくらい?

  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

append_to_list_with_comp.py

リスト内包表記を使ってもメモリの使用量は変わらないようです。

  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)]

add_to_set_with_loop.py

9行目、setの場合はlistの6倍近いメモリを使っているようです。1要素40byteくらい?

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

add_to_set_with_comp.py

リスト内包表記と同様、セット内包表記にしてもメモリ利用量は変わりません。

  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)}

append_to_list_with_comp_and_create_set.py

リスト内包表記でデータを作ってからsetを生成するとメモリ使用量は増えました。1要素60byteくらいに。list生成分とset生成分よりも多く増えているのでrandintの影響があるかも?今更ですが、そもそもrandintである必要はなかった気がします。

  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)])

append_to_array_with_loop.py

んー。70KiBしか増えないのはちょっとおかしい気が。はてはて?別の世界に行ってる?

  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

append_to_array_with_comp.py

リスト内包表記からarrayの生成。リスト内包表記分だけ増えてますね…

  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に関して、以下は感覚的にわかるのだけれど。

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

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

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