うどんコード

スパゲッティからうどんへ

Raging Stream

Pythonで要素検索の高速化

by ·

Pythonでデータ型による要素検索の性能について調べてみました

リスト型、マップ型、セット型による要素の存在確認 (inオペレーション)の性能を比較

  • 1から1億の間の整数値を持つサイズ10万のリストをそれぞれ作成 (マップ型、セット型は値の重複ができないので、若干サイズが小さくなる)
  • それぞれランダムに生成した1から1億の間の整数を1000回検索し、その時間を計測

(*) 実際のコードはブログ末に掲載

上記ベンチマークを実行すると、以下のような結果になりました。listが約1.3秒、dictとsetが約0.1ミリ秒とlistが圧倒的に遅いです。

list search (size:100000) ... 1.339225
dict search (size: 99947) ... 0.000178
set  search (size: 99947) ... 0.000139

また、リストのサイズを10万から100万にすると

list search (size:1000000) ... 12.171807
dict search (size: 995006) ...  0.000237
set  search (size: 995006) ...  0.000169

となり、listは10倍、dictとsetはほぼ同値となっていることから、listのinオペレーションはO(N)、dictとsetはO(1)であることがわかります。

こちらによるとCPythonではdictとsetは実際に同様の実装のようです

ベンチマークコード

import time
import random


class count_scope:
    """時間計測用クラス"""

    def __init__(self, name):
        self.name = name

    def __enter__(self):
        self.start = time.perf_counter()

    def __exit__(self, *args):
        print(f'{self.name} ... {time.perf_counter() - self.start:.6f}')


def main():
    r = random.Random(1)  # 実行毎の結果をそろえるためにシードを指定
    d_list = [r.randrange(100000000) for x in range(100000)]
    d_dict = {x: 'a' for x in d_list}
    d_set = set(d_list)

    search_value = [r.randrange(100000000)
                    for k in range(1000)]

    with count_scope(f"list search (size:{len(d_list)})") as p:
        for x in search_value:
            t = x in d_list

    with count_scope(f"dict search (size:{len(d_dict)})") as p:
        for x in search_value:
            t = x in d_dict

    with count_scope(f"set search (size:{len(d_set)})") as p:
        for x in search_value:
            t = x in d_set

    return


if __name__ == "__main__":
    main()

タグ:

おすすめ