92
83

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2021-01-29

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]

爆速:laughing:

検索のまとめ

検索の計測値

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

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

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

以上 :peach:

92
83
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
92
83

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?