はじめに

最近競プロをやっている中でしばしば

リスト内包表記の方が少し早く実行ができる

という話を聞いたので、実際にどのくらい速度の違いがあるのかを自分なりに検証してみました。

もっと良い比較検証の方法があればコメント等で教えて下さい！

実装

概要

今回は１重ループの場合と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=',')

参考