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集合に変換しましょう。
以上