■環境
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