はじめに
最近競プロをやっている中でしばしば
リスト内包表記の方が少し早く実行ができる
という話を聞いたので、実際にどのくらい速度の違いがあるのかを自分なりに検証してみました。
もっと良い比較検証の方法があればコメント等で教えて下さい！
実装
概要
今回は１重ループの場合と2重ループの場合それぞれで比較しました。
1重ループの場合は0からsizeまでの連番のリストを生成する関数を10回行いその平均値をとりました。
2重ループの場合は0からsizeまでの99表を表すリストを生成する関数を10回実行しその平均値をとりました。
なので、２重ループの方では i * j の掛け算の実行時間が含まれていることになるので、純粋な loop回数の比較 にはなっていないません。
実装例
以下のようなコードで実装を行いました。
また今回の実行環境は以下のとおりです
case1 ~ case4の関数はそれぞれ以下のような内容です.
| 関数名 | 概要 |
|---|---|
| case1 | 1重ループ |
| case2 | 1重ループの内包表記 |
| case3 | 2重ループ |
| case4 | 2重ループの内包表記 |
import time
import matplotlib.pyplot as plt
def case1(size) -> int:
start = time.time()
lst = []
for i in range(size):
lst.append(i)
end = time.time()
del lst
return end - start
def case2(size) -> int:
start = time.time()
lst = [i for i in range(size)]
end = time.time()
del lst
return end - start
# 2重loopだと
def case3(size) -> int:
start = time.time()
lst = []
for i in range(size):
row = []
for j in range(size):
row.append(i * j)
lst.append(row)
end = time.time()
del lst
return end - start
def case4(size) -> int:
start = time.time()
lst = [[i * j for j in range(size)] for i in range(size)]
end = time.time()
del lst
return end - start
def save_figure(results):
x = list(results.keys())
case1_values = [y1 for y1, _, _, _ in results.values()]
case2_values = [y2 for _, y2, _, _ in results.values()]
case3_values = [y3 for _, _, y3, _ in results.values()]
case4_values = [y4 for _, _, _, y4 in results.values()]
plt.figure(figsize=(10, 6))
plt.plot(x, case1_values, label='y1', marker='o')
plt.plot(x, case2_values, label='y2', marker='x')
plt.plot(x, case3_values, label='y3', marker='^')
plt.plot(x, case4_values, label='y3', marker=',')
plt.xscale('log')
plt.yscale('log')
plt.xlabel('size')
plt.ylabel('time')
plt.title('Speed Comparison between Comprehension and Extension (Log Scale)')
plt.legend()
plt.savefig('result.png')
# plt.show()
if __name__ == '__main__':
results = dict()
TRIAL = 10
size = 1
while size <= 10000:
sum1, sum2, sum3, sum4 = 0, 0, 0, 0
for _ in range(TRIAL):
sum1 += case1(size)
sum2 += case2(size)
sum3 += case3(size)
sum4 += case4(size)
results[size] = (sum1 / TRIAL, sum2 / TRIAL, sum3 / TRIAL, sum4 / TRIAL)
size *= 10
for k,v in results.items():
print(k, v)
save_figure(results)
実行結果
macbook airでの実行結果
M2macbookair (メモリ24GB)で実行を行いました。
グラフ
数値
| size | case1 | case2 | case3 | case4 |
|---|---|---|---|---|
| 1 | 1.9073486328125e-07 | 1.1920928955078125e-07 | 4.0531158447265624e-07 | 7.390975952148438e-07 |
| 10 | 6.914138793945312e-07 | 7.152557373046875e-07 | 7.843971252441406e-06 | 6.055831909179687e-06 |
| 100 | 7.915496826171876e-06 | 3.5762786865234375e-06 | 0.0006830453872680664 | 0.0004465818405151367 |
| 1,000 | 5.4168701171875e-05 | 2.4700164794921874e-05 | 0.07407045364379883 | 0.04849963188171387 |
| 10,000 | 0.0004548311233520508 | 0.00023338794708251953 | 7.839904356002807 | 5.50420355796814 |
google colaboratoryでの実行結果
グラフ
数値
| size | case1 | case2 | case3 | case4 |
|---|---|---|---|---|
| 1 | 7.390975952148438e-07 | 9.059906005859375e-07 | 1.0967254638671874e-06 | 2.0503997802734374e-06 |
| 10 | 1.6689300537109375e-06 | 1.2636184692382812e-06 | 1.7380714416503908e-05 | 1.6641616821289062e-05 |
| 100 | 1.3613700866699219e-05 | 7.343292236328125e-06 | 0.006212687492370606 | 0.0012163639068603516 |
| 1,000 | 0.00012297630310058593 | 5.755424499511719e-05 | 0.3006119966506958 | 0.20244963169097902 |
| 10,000 | 0.0007847785949707031 | 0.00036656856536865234 | 14.431228184700013 | 10.632153582572936 |
結果を見て
- size = 1の時はどちらの実行結果でも内包表記の方が遅くなっている。
- データ数が少ない場合は内包表記の方が遅い可能性がある。
- データ数と時間は比例している。データ数が増えても大きな速度向上はない?
- colabのcase3ででsize = 100のところが膨らんでいる
- 通信周りの影響を受けているのか？
最後に
今回はシンプルな数字の連番のリストを生成したので他のデータ構造だとどうなるかも検証してみたいなと思いいました。
また、内包表記の方が遅い区間がありそうなのでそこも突き止めてみると面白そうです。
今回の記事の比較方法で比較方法に問題等ありそうだったらコメント等で指摘もらえると幸いです
追記・補足
- グラフのラベルで
y4となるるべき場所がy3となっていました。- 誤:
plt.plot(x, case4_values, label='y3', marker=',') - 正:
plt.plot(x, case4_values, label='y4', marker=',')
- 誤:
参考