Pythonにおけるリストの高速処理

pythonにおいて、リストを利用する機会は多々ありますが、
リストの生成、検索においてどのように処理するのが一番速いのかを調べました。

環境

Python 3.7.8

生成

まずはじめに、こんなプログラムを用意しました。
リストの生成にかかる平均秒数を計測する簡単なプログラムです。

import random
from time import time

#### List Tests ####

# テスト回数
num_tests = 25

# テスト回数分の測定値を保存するリスト
timeList = []

for i in range(0, num_tests):

    # 10万まで要素を生成
    end = 100_000

    # 開始時刻
    startTime = time()

##### リスト生成プログラム #########################
    listComp = [i for i in range(0, end)]
##################################################

    # 終了時刻
    endTime = time()
    
    # 測定値保存
    timeList.append(endTime - startTime)

# テストの平均値[s]
avg = sum(timeList) / len(timeList)
print(avg, '[s]')

リスト生成プログラムの所を書き換えて計測していきましょう。

内包表記

まずは内包表記の場合です。

listComp = [i for i in range(0, end)]

結果

0.006156406402587891 [s]

appendメソッド

次はappendメソッドです。リスト生成プログラムを書き換えましょう。

append_list = []
for i in range(0,end):
  append_list.append(i)

結果

0.01742997169494629 [s]

初期化済みリスト

最後は、指定サイズ分要素を用意しておいて、
そこに値を代入しましょう。

preAllocate = [0] * end
for i in range(0, end):
  preAllocate[i] = i

結果

0.014672718048095702 [s]

生成のまとめ

リスト生成の計測値

方法	時間[ms]
内包表記	6.16
appendメソッド	17.42
初期化済みリスト	14.67

内包表記 > 初期化済みリスト > append の順で速いのが分かると思います。
生成する要素数を変えてみても、内包表記が一番速いのは変わりませんでした。

検索

次は検索の計測をしてみます。
先ほどのプログラムを少し書き換え、
1から30000の数値がランダムに入る、30000の要素を持つ配列を2つ用意して検索してみます。

import random
from time import time

# Initialize Random
random.seed(time())

#### List Tests ####

# テスト回数
num_tests = 3 

# テスト回数分の測定値を保存するリスト
timeList = []

for i in range(0, num_tests):

    # 3万まで要素を生成
    end = 30_000

    # リストの生成
    list_a = [random.randint(1, end) for i in range(0, end)]
    list_b = [random.randint(1, end) for i in range(0, end)]

    # 開始時刻
    startTime = time()

##### リスト検索プログラム #########################
    for i in list_a:
        for j in list_b:
            if i == j:
                break
###############################################

    # 終了時刻
    endTime = time()

    # 測定値保存
    timeList.append(endTime - startTime)

# テストの平均値[s]
avg = sum(timeList) / len(timeList)
print(avg, '[s]')

リスト検索プログラムの所を書き換えて計測していきましょう。

ダブルループ

まずはダブルループの場合です。

for i in list_a:
    for j in list_b:
        if i == j:
            break

結果

34.66531833012899 [s]

In検索

次はInを使って検索を行ってみましょう。

for i in list_a:
  if i in list_b:
    continue

結果

7.02125096321106 [s]

Set集合

次は検索する対象をSet集合にして、重複を無くしてみましょう。
Set集合の場合は、ハッシュ値を利用してアクセスするので、
1回の検索に必要な計算量はO(1)。n要素だったらO(n)。

unique = set(list_b)
for i in list_a:
  if i in unique:
    continue

結果

0.0038799444834391275 [s]

爆速

検索のまとめ

検索の計測値

方法	時間[s]	計算量[O]
ダブルループ	34.6653	O(n^2)
In検索	7.0213	?
Set集合	0.0039	O(n)

やっぱりハッシュを使うSet集合は爆速です。ダブルループの比ではないですね。
in検索だけでもループに比べると1/5くらいになるのが分かります。

リストから値を検索したい場合は、inを使いましょう。
そして、可能な場合はハッシュが使えるSet集合に変換しましょう。

以上