🤖

Pythonのlistとsetでの値の含み判定の所要時間について

2025/10/29に公開

5件

今回はPythonのlistとsetでデータが含まれているかどうかを判定するためのロジックの所要時間の差について調べてみました。Pythonの仕様として、単純にデータを列挙しておきたいだけの場合にlistを利用せずsetを利用する方が良い場合もあり個人的に気をつけていましたが、以下の記事をみて実際にlistとsetでどれくらい差が出るかを調べてみようと思いました。今回は値の一覧に特定の値が含まれているかを判定するのにかかる時間を調べてみました。

検証内容

Pythonを利用していると、以下のような構文でlistやsetに値が含まれているかを判定したい時があると思います。

items = [...]

if item in items:
    # do something
else:
    # do something

Pythonのlistで値が含まれているか判定する場合は、以下のリンクにあるように最初の要素から順番に確認し、見つかるまで一つずつ確認されるようです。つまりデータをnとすると検索にはO(n)の計算量が必要となります。

static int
list_contains(PyObject *aa, PyObject *el)
{

    for (Py_ssize_t i = 0; ; i++) {
        PyObject *item = list_get_item_ref((PyListObject *)aa, i);
        if (item == NULL) {
            // out-of-bounds
            return 0;
        }
        int cmp = PyObject_RichCompareBool(item, el, Py_EQ);
        Py_DECREF(item);
        if (cmp != 0) {
            return cmp;
        }
    }
    return 0;
}

一方setを利用すると、ハッシュテーブルが内部で利用されているので検索がO(1)でできるとのことです。

static int
set_contains_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
    setentry *entry;

    entry = set_lookkey(so, key, hash);
    if (entry != NULL)
        return entry->key != NULL;
    return -1;
}

static int
set_contains_key(PySetObject *so, PyObject *key)
{
    Py_hash_t hash = _PyObject_HashFast(key);
    if (hash == -1) {
        set_unhashable_type(key);
        return -1;
    }
    return set_contains_entry(so, key, hash);
}

早速検証してみる

それでは検証してみます。100から1000000まで10倍ずつでリストの要素を増やし、一番大きい値（つまり最後の要素）を見つけるのにかかる時間を計測してみます。

まずはuvを利用して環境構築しました。

uv init list_set_search -p 3.12
cd list_set_search
uv add matplotlib

コードはこちらになります。

list_set_search.py

import time
import matplotlib.pyplot as plt

exponent = [2, 3, 4, 5, 6]

list_times = []
set_times = []

for e in exponent:
    item_list = [i for i in range(10**e)]
    item_set = set(item_list)

    target_item = item_list[-1]

    st = time.time()
    if target_item in item_list:
        pass
    et = time.time()
    list_times.append(et-st)

    st = time.time()
    if target_item in item_set:
        pass
    et = time.time()
    set_times.append(et-st)


plt.plot(exponent, list_times, color="red", label="list")
plt.plot(exponent, set_times, color="blue", label="set")
plt.legend()
plt.xlabel("Exponent")
plt.ylabel("Duration[s]")
plt.show()

list_timesとset_timesには検索時間を保存するようにしており、forでは10の指数をループさせることでループごとに値を増やしています。結果については指数ごとに検索時間をまとめるようにしています。

コードを実行すると以下のような結果になります。グラフをみると、赤色のlistについては要素数が10,000くらいまではほぼ横ばいですが100,000を超えてから急激に時間が増えていることが確認できます。一方setではほぼ横ばいで定数時間で検索できていることがわかりました。

uv run list_set_search.py

まとめ

今回はPythonのlistとsetで値が含まれているか判定するのに所要する時間に差があるか確認してみました。実際のコーディングにおいては、要素が可変的な場合やそのほかのlist特有の演算が必要な場合はlistを使い、値が初期化時点で固定されたり検索スピードを優先したい場合はsetを利用するといいでしょう。~~また、setの方がインスタンスのメモリ消費量が少ないのも特徴なので、ぜひ使い分けてみてください。~~（こちらの言及はsetではなくtuple使用時のものでした。ご指摘いただきありがとうございます）

Discussion

shiracamus

setの方がインスタンスのメモリ消費量が少ないのも特徴

そうとも限らないのでは？
重複要素が多ければ少なくなりますけど。
要素はオブジェクトIDを保持するだけなので、1要素8バイト（64ビット版の場合）。

>>> list().__sizeof__()
40
>>> set().__sizeof__()
200
>>> list(range(100)).__sizeof__()
840
>>> set(range(100)).__sizeof__()
8392
>>> list([1]*100).__sizeof__()
840
>>> set([1]*100).__sizeof__()
200
>>> help(set().__sizeof__)
Help on built-in function __sizeof__:

__sizeof__(...) method of builtins.set instance
    S.__sizeof__() -> size of S in memory, in bytes

Akasan

コメントありがとうございます！
過去にこのような議論していてその時の前提条件なしで記載していたので問題でしたね！ご指摘ありがとうございます！！

修正させていただきます！

Akasan

こちら、メモリのけんはsetではなくtupleの間違いでした 🙇

shiracamus

記事の修正はされないのでしょうか？

Akasan

本件、対応しました！ご指摘ありがとうございます！