Python性能検証のメモ

■環境
　Google Colaboratory(無料版)
　CPU

## 検証1. list.remove と del list[index] の比較
~~~list.remove vs del list[index].py
import time
ls1 = list(range(100000))
ls2 = ls1.copy()

# list.remove
start = time.time()
for ele in ls1:
  ls1.remove(ele)
print(f'list.remove: {time.time() - start}')

# del list[index]
start = time.time()
for index, ele in enumerate(ls2):
  del ls2[index]
print(f'del list[index]: {time.time() - start}')
~~~
~~~
list.remove: 19.598609685897827
del list[index]: 0.4855682849884033
~~~
インデックス指定削除（dels list[index]）の方が速かった。
※後述の検証3で示しているが、ループ対象自体の削除は想定している全要素削除になってない。ただこの点は両者とも同条件なので、速度比較自体は出来ていると考える。

## 検証2. listの頭から削除　と　末端からの削除 　の比較
検証1だとlistの頭から削除のため、削除するたびにインデックスがずれるので低速と思われる。末端から削除した場合と比較する。
結果、末端削除の方が遅い。ループ対象の削除自体が変に作用しているのかもしれない。この点を検証する。
~~~ list.remove頭から vs list remove 末端から.py
import time
ls1 = list(range(100000))
ls2 = ls1.copy()

# list.remove 頭から
start = time.time()
for ele in ls1:
  ls1.remove(ele)
print(f'list.remove 頭から: {time.time() - start}')

# list.remove 末端から
start = time.time()
for ele in reversed(ls2):
  ls2.remove(ele)
print(f'list.remove 末端から: {time.time() - start}')
~~~
~~~
list.remove 頭から: 20.381234645843506
list.remove 末端から: 81.50449061393738
~~~
末端削除の方が遅い。ループ対象の削除自体が変に作用しているのかもしれない。

## 検証3. loop対象自体を削除していることの影響を見る
~~~ loop対象削除の影響確認.py
import time
n = 100000
ls1 = list(range(n))
ls2 = ls1.copy()
ls3 = ls1.copy()

# 削除するlist自体をloopしながら要素削除
start = time.time()
for ele in ls1:
  ls1.remove(ele)
print(f'削除list自体をloop: {time.time() - start}')
print(f'削除後の要素数: {len(ls1)}')

# loopのジェネレータ部を固定してlistの頭から要素削除
start = time.time()
for ele in range(n):
  ls2.remove(ele)
print(f'loopジェネレータ固定して頭から削除: {time.time() - start}')
print(f'削除後の要素数: {len(ls2)}')

# loopのジェネレータ部を固定してlistの末端から要素削除
start = time.time()
for ele in reversed(range(n)):
  ls3.remove(ele)
print(f'loopジェネレータ固定して末端から削除: {time.time() - start}')
print(f'削除後の要素数: {len(ls3)}')
~~~
~~~
削除list自体をloop: 19.865585803985596
削除後の要素数: 50000
loopジェネレータ固定して頭から削除: 0.8819541931152344
削除後の要素数: 0
loopジェネレータ固定して末端から削除: 69.22009825706482
削除後の要素数: 0
~~~
考察①  
削除後の要素数を確認すると、そもそもループ対象自体を削除すると想定通りの動きをしてないことが判明。速い遅い以前に、ループ対象自体の削除はNG    
考察②  
list.removeの場合、末端要素から削除の方が遅い。listの頭から要素検索するため、末端削除は探索に時間がかかるためと考える。

## 検証4. list.pop（index指定削除）で検証
~~~list pop削除 頭から vs 末端から.py
import time
n = 100000
ls1 = list(range(n))
ls2 = ls1.copy()

# listの頭から要素削除
start = time.time()
for _ in range(n):
  ls1.pop(0)
print(f'頭からindex指定削除: {time.time() - start}')

# loopのジェネレータ部を固定してlistの末端から要素削除
start = time.time()
for _ in range(n):
  ls2.pop()
print(f'末端からindex指定削除: {time.time() - start}')
~~~
~~~
頭からindex指定削除: 0.9552161693572998
末端からindex指定削除: 0.015168428421020508
~~~
index指定削除だと末端から削除が速い。
削除後のindex振り直しが発生しないためと考える。

## 検証5. del list[index]（index指定削除）で同様の検証
~~~ del削除 頭から vs 末端から.py
import time
n = 100000
ls1 = list(range(n))
ls2 = ls1.copy()

# listの頭からindex指定削除
start = time.time()
for _ in range(n):
  del ls1[0]
print(f'頭からindex指定削除: {time.time() - start}')

# listの末端からindex指定削除
start = time.time()
for _ in range(n):
  ls2[-1]
print(f'末端からindex指定削除: {time.time() - start}')
~~~
~~~
頭からindex指定削除: 0.8782427310943604
末端からindex指定削除: 0.00836491584777832
~~~
pop削除同様、末端から削除が速い。

## 遭遇した課題
 要素削除の性能比較で、なぜかインデックス指定削除（del dictionary[key], set.discard）　が list.remove　より遅い事象に遭遇。
以下ではこれを検証課題とする。
~~~ 課題事象.py
import time

n = 100000
# 比較対象のコレクション3種
ls1 = list(range(n))
dic1 = dict.fromkeys(ls1)
set1 = set(range(n))
# 削除リスト
del_list = ls1.copy()

# list.remove
print(f'list.remove' + '-' * 20)
print(f'削除前の要素数: {len(ls1)}')
start = time.time()
for x in del_list:
  for _ in ls1:
    break
  ls1.remove(x)
print(f'time: {time.time() - start}')
print(f'削除後の要素数: {len(ls1)}')
print()

# del dictionary[key]
print(f'del dictionary[key]' + '-' * 20)
print(f'削除前の要素数: {len(dic1)}')
start = time.time()
for x in del_list:
  for _ in dic1:
    break
  del dic1[x]
print(f'time: {time.time() - start}')
print(f'削除後の要素数: {len(dic1)}')
print()

# set.discard
print(f'set.discard' + '-' * 20)
print(f'削除前の要素数: {len(set1)}')
start = time.time()
for x in del_list:
  for _ in set1:
    break
  set1.discard(x)
print(f'time: {time.time() - start}')
print(f'削除後の要素数: {len(set1)}')
~~~
~~~
list.remove--------------------
削除前の要素数: 100000
time: 0.8904502391815186
削除後の要素数: 0

del dictionary[key]--------------------
削除前の要素数: 100000
time: 5.543084621429443
削除後の要素数: 0

set.discard--------------------
削除前の要素数: 100000
time: 6.006482362747192
削除後の要素数: 0
~~~

### 以下で原因を深堀する。
まず共通処理を関数化し、3者のコードの違いを分かりすくする。
~~~ delete_from_collection.py
def delete_from_collection(del_target, del_element):
  target_type = type(del_target)
  if target_type is set:
    del_target.discard(del_element)
  elif target_type is list:
    del_target.remove(del_element)
  else:
    del del_target[del_element]  
~~~
~~~ inner_loop.py
def inner_loop(del_target, del_element):
  for _ in del_target:
    break
~~~
~~~ execute_test.py
def execute_test(del_list, del_target, test_name):
  print(test_name + '-' * 20)
  print(f'削除前の要素数: {len(del_target)}')
  start = time.time()

  for del_element in del_list:
    inner_loop(del_target, del_element)
    delete_from_collection(del_target, del_element)
  print(f'time: {time.time() - start}')
  print(f'削除後の要素数: {len(del_target)}')
  print()
~~~

作成した共通関数を使って、事象を再現できることの確認
~~~事象確認.py
import time

n = 100000
# 比較対象のコレクション3種
ls1 = list(range(n))
dic1 = dict.fromkeys(ls1)
set1 = set(range(n))
# 削除リスト
del_list = ls1.copy()

# list.remove
execute_test(del_list, ls1, 'list.remove')

# del dictionary[key]
execute_test(del_list, dic1, 'del dictionary[key]')

# set.discard
execute_test(del_list, set1, 'set.discard')
~~~
~~~
list.remove--------------------
削除前の要素数: 100000
time: 0.916370153427124
削除後の要素数: 0

del dictionary[key]--------------------
削除前の要素数: 100000
time: 4.758455514907837
削除後の要素数: 0

set.discard--------------------
削除前の要素数: 100000
time: 7.24356746673584
削除後の要素数: 0
~~~
削除を末端から行うと、dict と set での削除は高速になることを発見。
なおlist.removeは探索に時間を要するため、超低速になる（検証3考察②の事象）
~~~ execute_test_reverse.py
def execute_test_reverse(del_list, del_target, test_name):
  print(test_name + '-' * 20)
  print(f'削除前の要素数: {len(del_target)}')
  start = time.time()

  for del_element in reversed(del_list):
    inner_loop(del_target, del_element)
    delete_from_collection(del_target, del_element)
  print(f'time: {time.time() - start}')
  print(f'削除後の要素数: {len(del_target)}')
  print()
~~~
~~~ 末端から削除.py
import time

n = 100000
# 比較対象のコレクション3種
ls1 = list(range(n))
dic1 = dict.fromkeys(ls1)
set1 = set(range(n))
# 削除リスト
del_list = ls1.copy()

# list.remove
execute_test_reverse(del_list, ls1, 'list.remove')

# del dictionary[key]
execute_test_reverse(del_list, dic1, 'del dictionary[key]')

# set.discard
execute_test_reverse(del_list, set1, 'set.discard')
~~~
~~~
list.remove--------------------
削除前の要素数: 100000
time: 77.07931065559387
削除後の要素数: 0

del dictionary[key]--------------------
削除前の要素数: 100000
time: 0.030425310134887695
削除後の要素数: 0

set.discard--------------------
削除前の要素数: 100000
time: 0.02913355827331543
削除後の要素数: 0

~~~
原因調査のため、プロファイリングを行う
まずは専用の関数を定義
~~~ profile.py
import cProfile
import pstats
def profile(fn, del_list, del_target, test_name, display_row_cnt=5, reverse = False):
  """
  与えられたfn関数について、tottime(消費された合計時間)  トップn の実行された関数を表示
  """
  pr = cProfile.Profile()
  pr.enable()
  fn(del_list, del_target, test_name)
  pr.disable()
  stats = pstats.Stats(pr)
  stats.sort_stats('tottime')
  stats.print_stats(display_row_cnt)
~~~
~~~ profile(頭から削除).py
n = 100000
# 比較対象のコレクション3種
ls1 = list(range(n))
dic1 = dict.fromkeys(ls1)
set1 = set(range(n))
# 削除リスト
del_list = ls1.copy()

# list.remove
profile(execute_test, del_list, ls1, 'list.remove')

# del dictionary[key]
profile(execute_test, del_list, dic1, 'del dictionary[key]')

# set.discard
profile(execute_test, del_list, set1, 'set.discard')
~~~
~~~
list.remove--------------------
削除前の要素数: 100000
time: 1.1237337589263916
削除後の要素数: 0

         300144 function calls in 1.127 seconds

   Ordered by: internal time
   List reduced from 21 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    0.941    0.000    0.941    0.000 {method 'remove' of 'list' objects}
        1    0.080    0.080    1.127    1.127 <ipython-input-20-ca44e91a24d1>:1(execute_test)
   100000    0.077    0.000    1.017    0.000 <ipython-input-3-ea7b3102765b>:1(delete_from_collection)
   100000    0.026    0.000    0.026    0.000 <ipython-input-19-f9ce8f25d64e>:1(inner_loop)
       11    0.003    0.000    0.003    0.000 /usr/local/lib/python3.10/dist-packages/zmq/sugar/socket.py:543(send)


del dictionary[key]--------------------
削除前の要素数: 100000
time: 5.413957357406616
削除後の要素数: 0

         200136 function calls in 5.416 seconds

   Ordered by: internal time
   List reduced from 20 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    5.192    0.000    5.192    0.000 <ipython-input-19-f9ce8f25d64e>:1(inner_loop)
        1    0.159    0.159    5.416    5.416 <ipython-input-20-ca44e91a24d1>:1(execute_test)
   100000    0.063    0.000    0.063    0.000 <ipython-input-3-ea7b3102765b>:1(delete_from_collection)
       10    0.001    0.000    0.001    0.000 /usr/local/lib/python3.10/dist-packages/zmq/sugar/socket.py:543(send)
        9    0.000    0.000    0.002    0.000 /usr/local/lib/python3.10/dist-packages/ipykernel/iostream.py:384(write)


set.discard--------------------
削除前の要素数: 100000
time: 6.14174222946167
削除後の要素数: 0

         300136 function calls in 6.143 seconds

   Ordered by: internal time
   List reduced from 21 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    5.942    0.000    5.942    0.000 <ipython-input-19-f9ce8f25d64e>:1(inner_loop)
        1    0.132    0.132    6.143    6.143 <ipython-input-20-ca44e91a24d1>:1(execute_test)
   100000    0.051    0.000    0.068    0.000 <ipython-input-3-ea7b3102765b>:1(delete_from_collection)
   100000    0.017    0.000    0.017    0.000 {method 'discard' of 'set' objects}
       10    0.001    0.000    0.001    0.000 /usr/local/lib/python3.10/dist-packages/zmq/sugar/socket.py:543(send)
~~~
~~~ profile(末端から削除).py
n = 100000
# 比較対象のコレクション3種
ls1 = list(range(n))
dic1 = dict.fromkeys(ls1)
set1 = set(range(n))
# 削除リスト
del_list = ls1.copy()

# list.remove
profile(execute_test_reverse, del_list, ls1, 'list.remove')

# del dictionary[key]
profile(execute_test_reverse, del_list, dic1, 'del dictionary[key]')

# set.discard
profile(execute_test_reverse, del_list, set1, 'set.discard')
~~~
~~~
list.remove--------------------
削除前の要素数: 100000
time: 71.36500406265259
削除後の要素数: 0

         300144 function calls in 71.366 seconds

   Ordered by: internal time
   List reduced from 21 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000   70.461    0.001   70.461    0.001 {method 'remove' of 'list' objects}
   100000    0.687    0.000   71.148    0.001 <ipython-input-3-ea7b3102765b>:1(delete_from_collection)
        1    0.161    0.161   71.366   71.366 <ipython-input-25-14cc60f8d230>:1(execute_test_reverse)
   100000    0.056    0.000    0.056    0.000 <ipython-input-19-f9ce8f25d64e>:1(inner_loop)
       11    0.001    0.000    0.001    0.000 /usr/local/lib/python3.10/dist-packages/zmq/sugar/socket.py:543(send)


del dictionary[key]--------------------
削除前の要素数: 100000
time: 0.08414053916931152
削除後の要素数: 0

         200128 function calls in 0.085 seconds

   Ordered by: internal time
   List reduced from 20 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.039    0.039    0.085    0.085 <ipython-input-25-14cc60f8d230>:1(execute_test_reverse)
   100000    0.030    0.000    0.030    0.000 <ipython-input-3-ea7b3102765b>:1(delete_from_collection)
   100000    0.015    0.000    0.015    0.000 <ipython-input-19-f9ce8f25d64e>:1(inner_loop)
        9    0.001    0.000    0.001    0.000 /usr/local/lib/python3.10/dist-packages/zmq/sugar/socket.py:543(send)
        9    0.000    0.000    0.001    0.000 /usr/local/lib/python3.10/dist-packages/ipykernel/iostream.py:384(write)


set.discard--------------------
削除前の要素数: 100000
time: 0.1130373477935791
削除後の要素数: 0

         300136 function calls in 0.126 seconds

   Ordered by: internal time
   List reduced from 21 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.046    0.046    0.126    0.126 <ipython-input-25-14cc60f8d230>:1(execute_test_reverse)
   100000    0.037    0.000    0.050    0.000 <ipython-input-3-ea7b3102765b>:1(delete_from_collection)
   100000    0.018    0.000    0.018    0.000 <ipython-input-19-f9ce8f25d64e>:1(inner_loop)
       10    0.013    0.001    0.013    0.001 /usr/local/lib/python3.10/dist-packages/zmq/sugar/socket.py:543(send)
   100000    0.013    0.000    0.013    0.000 {method 'discard' of 'set' objects}
~~~
### 結果
del dictionary[key] や set.discard は削除処理自体は速いが、頭から削除すると、inner loopが非常に遅い。  
inner loop自体はイテレータ作成のみ。よって、dictionary や setでは、要素を頭から削除すると、listに比べイテレータ作成に時間が非常にかかると言える。

### 確認
inner loopを消すとインデックス指定削除が速い。
やはりイテレータ作成が処理のボトルネックだったと言える。
~~~ execute_test_no_inner_loop.py
def execute_test_no_inner_loop(del_list, del_target, test_name):
  print(test_name + '-' * 20)
  print(f'削除前の要素数: {len(del_target)}')
  start = time.time()

  for del_element in del_list:
    delete_from_collection(del_target, del_element)
  print(f'time: {time.time() - start}')
  print(f'削除後の要素数: {len(del_target)}')
  print()
~~~
~~~ inner loopなしで確認.py
import time

n = 100000
# 比較対象のコレクション3種
ls1 = list(range(n))
dic1 = dict.fromkeys(ls1)
set1 = set(range(n))
# 削除リスト
del_list = ls1.copy()

# list.remove
execute_test_no_inner_loop(del_list, ls1, 'list.remove')

# del dictionary[key]
execute_test_no_inner_loop(del_list, dic1, 'del dictionary[key]')

# set.discard
execute_test_no_inner_loop(del_list, set1, 'set.discard')
~~~
~~~
list.remove--------------------
削除前の要素数: 100000
time: 0.9077644348144531
削除後の要素数: 0

del dictionary[key]--------------------
削除前の要素数: 100000
time: 0.017519235610961914
削除後の要素数: 0

set.discard--------------------
削除前の要素数: 100000
time: 0.023037195205688477
削除後の要素数: 0
~~~