Python で要素の検索速度の比較

Python で複数の要素から特定のものが存在するかを検索する場合の，効率がよい方法を検討します．

課題

• 10万個の要素から特定の要素が存在するかどうかを返す．

set を使用する方法， list を使用する方法をすぐに思いつきます．list を set に変換してから検索してもよいかもしれません．速度を比較してみましょう．

ベンチマーク

import math

from benchmarker import Benchmarker

with Benchmarker(loop=1000, cycle=1, width=20) as bench:
    n = 100 * 1000
    target = math.floor(n / 2)

    @bench(None)
    def _(bm):
        for _ in bm:
            pass

    @bench("list-search")
    def _(bm):
        s = list(range(n))
        for _ in bm:
            target in s

    @bench("list-set-search")
    def _(bm):
        s = list(range(n))
        for _ in bm:
            target in set(s)

    @bench("set-search")
    def _(bm):
        s = set(range(n))
        for _ in bm:
            target in s

実行したところ，以下のような結果が得られました．

## benchmarker:         release 4.0.1 (for python)
## python version:      3.11.6
## python compiler:     Clang 13.0.0 (clang-1300.0.29.30)
## python platform:     macOS-13.6.3-arm64-arm-64bit
## python executable:   ***
## cpu model:           Apple M1 
## parameters:          loop=1000, cycle=1, extra=0

##                        real    (total    = user    + sys)
(Empty)                 0.0000    0.0000    0.0000    0.0000
list-search             0.4431    0.4400    0.4400    0.0000
list-set-search         1.5494    1.5600    1.2200    0.3400
set-search              0.0029    0.0000    0.0000    0.0000

## Ranking                real
set-search              0.0029  (100.0) ********************
list-search             0.4431  (  0.6) 
list-set-search         1.5494  (  0.2) 

set と list の検索速度は，set が O(1) であり， list が O(n) であると記載されています *1． したがって多くの要素から検索する場合は set を使用するのがよさそうです．しかし，list から毎回 set を生成する方が時間がかかるので，list から検索する場合は素直に list のまま処理をした方が速いようです．

*1:https://wiki.python.org/moin/TimeComplexity