list.index()ってどれくらい早いの？

Pythonのリスト（配列）の要素のインデックス、つまり、その要素が何番目に格納されているかを取得するにlistのindex()メソッドを使う。

>>> [10,20,30,40,50].index(20)
1

これがどのくらいの実行速度か気になったので測定してみた。

測定環境

python3 --version
Python 3.10.11

測定対象

他の方法と比較した方が分かりやすいので、いくつかと比較してみる。

比較対象
- 線形探索(linear_search)
- list.index (index_search) <- 今回気になるヤツ
- 二分探索(binary_search)
- bisectライブラリ(bisect_search)

bisectは挿入位置を見つけるためのライブラリだが、要素自体のインデックス取得もやれるので候補に入れてみる。

測定内容

0 <= n < 50000の値が昇順に格納された配列から、すべての値のindexを見つけ出す速度を測定する。
つまり50000回インデックスの取得を実行する。
見つからない場合はテストケースに入れない。

コード

import bisect
import time


def linear_search(arr: list[int], target: int):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1


def index_search(arr: list[int], target: int):
    try:
        return arr.index(target)
    except ValueError:
        return -1


def binary_search(arr: list[int], target: int):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
    return -1


def bisect_search(arr: list[int], target: int):
    index = bisect.bisect_left(arr, target)
    if index != len(arr) and arr[index] == target:
        return index
    else:
        return -1


def keisoku(search):
    ELEMENT_COUNT = 50000
    arr = [i for i in range(ELEMENT_COUNT)]

    start = time.time()
    for target in range(ELEMENT_COUNT):
        search(arr, target)
    end = time.time()

    print(f"{search.__name__: <13}: {end - start}")


if __name__ == "__main__":
    keisoku(linear_search)
    keisoku(index_search)
    keisoku(binary_search)
    keisoku(bisect_search)

keisoku関数はsearch関数を実行して、実行速度を標準出力するだけのWrapper。

結果

linear_search: 56.06361961364746
index_search : 11.071388006210327
binary_search: 0.1294879913330078
bisect_search: 0.022607803344726562

Python上で実装した線形探索より約5倍早い。結構早い。
これはlist.index()がCPythonで実装されているからだろうけども、実装コード自体は公開されていないのか、見れない（場所知ってる人教えてください）。
https://github.com/python/cpython/blob/main/Objects/listobject.c

二分探索よりはかなり遅い。list.index()は配列がソートされていることを前提にしていないので当然。二分探索はソート済みの配列でないとサーチ自体できない。
とはいえ、速度差があるのは事実なので、配列がソートされているならば二分探索を自分で実装してでもやったほうが早い。

自分で実装してでもと言ったが、それならばbisectを使った方がいい。
binary_searchとbisect_searchでも5倍以上差がある。これもbisectは処理系がCPythonだから。
下記のbisectの実装を見る限り、実装自体は上記binary_searchのコードとさほど変わらない。

まとめ

list.index()はまぁまぁ早い。CPythonだから。
とはいっても二分探索よりは遅い。Pythonで実装した二分探索よりも遅い。
配列が巨大でソート済前提ならばbisectは有効な選択肢