【Python】リスト内の特定要素存在チェック方法を比較

はじめに

　Python でリストに特定条件を満たす要素が存在するか判定したい時って結局どう書くのが良いんだろう？　と疑問だったので、いくつかの方法の速度を計測、比較してみました。
　単純に '1' in ['1', '2', '3'] のようにリスト内要素の値をそのまま指定できる場合は悩む必要はないので、要素に対して何らかの操作（ここではメンバ変数参照）が必要な場合を想定しています。

存在チェック方法

　class Person のリストからメンバー変数 last_name が '紀伊田' と一致する要素が存在するかチェックする、という前提で以下 4つの方法を比較しました。

1. in 演算子 ： '紀伊田' in (p.last_name for p in personlist)
   
   → 内包表記によりメンバー変数 last_name のみを抽出して in 演算子を使えるようにしたパターン。
2. any 関数 ： any(p.last_name == '紀伊田' for p in personlist)
   
   → 内包表記により要素ごとに条件を満たすかどうかの bool 値を抽出して any 関数を使ったパターン。
3. any 関数2 ： any(True for p in personlist if p.last_name == '紀伊田')
   
   → 2.の亜種で if 文により条件を満たす要素のみ True を抽出して any 関数を使うパターン。
4. next 関数 ： next((True for p in personlist if p.last_name == '紀伊田'), False)
   
   → 3.と同じことを any 関数ではなく next 関数で判定するパターン。

　personlist の要素数は 10000 個、last_name は Faker で生成し、5001 番目のみ紀伊田で上書きして 1 つだけ存在する状態にしています。
　上記はジェネレーター式で記載していますがリスト内包表記とセット内包表記の場合についても計測しました。

計測結果

　1. ～ 4. の方法を for _ in range(100000): で 100000 回実行するのに掛かった時間です（at Google Colaboratory）。
　3. の if文で条件指定したジェネレーター式を any 関数で評価するのが一番速い という結果になりました。

	1.in 式	2.any 式	3.any if式	4.next if式	in	any	any if	next	forのみ
リスト内包表記	84.067628	99.620646	78.945970	NaN	5.785986	3.312556	0.017510	NaN	0.004489
セット内包表記	71.618741	84.979072	76.397498	NaN	0.008912	0.016706	0.015983	NaN	0.004158
ジェネレーター式	52.239412	58.766906	38.168067	39.631893	NaN	NaN	NaN	NaN	0.004978
※1.　5 ～ 8 列目は 1. ～ 4. の内包表記の式をforの外側に逃がして計測した参考値
※2.　同じジェネレーターを複数回評価できないためジェネレーター式の 5 ～ 8 は未計測

内包表記による違い

　ジェネレーター式 $>$ セット内包表記 $>$ リスト内包表記 の順に速い結果となりました。
ジェネレーター式が速いのは予想どおりですが、リスト内包表記よりセット内包表記の方が速いのは意外でした。Faker の生成した last_name のユニーク値が 52 個しかなかったので、セットの重複チェック処理よりリストのメモリ拡張処理の方が結果に影響したのだと考えられます。

判定方法による違い

　3. any 関数2 $\geqq$ 4. next 関数 $>$ 1. in 演算子 $>$ 2. any 関数 の順に速い結果となりました。
if文のありなしが異なる 2. と 3. で 3. any 関数2 $>$ 2. any 関数 となったのは、2. では p.last_name == '紀伊田' の判定が False のものも列挙されるので、True が出現するまで（今回は 5000 個）の Falseも any で再判定するのに対し、3. では p.last_name == '紀伊田' が True になった要素のみ列挙されるため any の再判定は 1 回のみである点が速度に寄与しているのではないかと思います。この理屈が正しければ 3. any 関数2 $>$ 1. in 演算子 となるのも納得できます。

　1. in 演算子 $>$ 2. any 関数 はどちらも True になるまでの False（5000 個）の要素を判定する点は変わりませんが、1. の方は文字列一致判定が 1 回に対し、2. は == 演算子と any 関数 で 2 回判定される違いが速度差に現れたのだと思われます。

結論

　if文で条件指定したジェネレーター式を any 関数で評価するのが一番速い

おわりに

　以前からの疑問に対して答えが出たので満足です。python の中身を把握しているわけではないので本当のところは違うかも知れませんが、測定結果に対してそれっぽい理由はつけられたと思いますので、結論としては合ってるのではないかと思います。
　ユニーク値の割合や、一致する要素が何番目にあるのかなどで結果も変わってくるでしょうが、基本は if 文つきジェネレーター式と any 関数の組合せが安定すると思います。
　当たり前ですが数回の判定なら体感差は出ないので、速度を気にしない、タイプ量が少ない、分かりやすいとかで in 演算子やその他方法も適宜使えば良いと思います。
　もっと良い方法を知ってるという方は教えていただけると嬉しいです。

おまけ：計測コード（Colaboratory）

（折りたたみ）

!pip install Faker > /dev/null
import time

from faker import Factory
import pandas as pd

class Person:
    def __init__(self, first_name: str, last_name: str):
        self.first_name = first_name
        self.last_name = last_name
        
    def __str__(self):
        return f'{self.last_name} {self.first_name}'

fake = Factory.create('ja_JP')
personlist = [
    Person(fake.first_name(), fake.last_name()) for _ in range(10000)
]
print(f'紀伊田 in persons : {"紀伊田" in (p.last_name for p in personlist)}')
personlist[5000].first_name = 'きい太'
personlist[5000].last_name = '紀伊田'
print(f'紀伊田 in persons : {"紀伊田" in (p.last_name for p in personlist)}')
print('')
print(' / '.join(str(p) for p in personlist[4996:5005]))

紀伊田 in persons : False
紀伊田 in persons : True

工藤 太郎 / 中津川 淳 / 工藤 加奈 / 原田 幹 / 紀伊田 きい太 / 若松 涼平 / 廣川 さゆり / 大垣 零 / 斉藤 英樹

trials = 1
index = ['in 式', 'any 式', 'any if式', 'next if式', 'in', 'any', 'any if', 'next if', 'forのみ']

# リスト内包表記
series1 = pd.Series(0., index=index)
series1['next if式'] = None
series1['next if'] = None

for _ in range(trials):
    tm = time.time()
    for _ in range(100000):
        '紀伊田' in [p.last_name for p in personlist]
    series1['in 式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        any([p.last_name == '紀伊田' for p in personlist])
    series1['any 式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        any([True for p in personlist if p.last_name == '紀伊田'])
    series1['any if式'] += time.time() - tm

    persons = [p.last_name for p in personlist]
    tm = time.time()
    for _ in range(100000):
        '紀伊田' in persons
    series1['in'] += time.time() - tm

    persons = [p.last_name == '紀伊田' for p in personlist]
    tm = time.time()
    for _ in range(100000):
        any(persons)
    series1['any'] += time.time() - tm

    persons = [True for p in personlist if p.last_name == '紀伊田']
    tm = time.time()
    for _ in range(100000):
        any(persons)
    series1['any if'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        pass
    series1['forのみ'] += time.time() - tm

series1 /= trials

# セット内包表記
series2 = pd.Series(0., index=index)
series2['next if式'] = None
series2['next if'] = None

for _ in range(trials):
    tm = time.time()
    for _ in range(100000):
        '紀伊田' in {p.last_name for p in personlist}
    series2['in 式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        any({p.last_name == '紀伊田' for p in personlist})
    series2['any 式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        any({True for p in personlist if p.last_name == '紀伊田'})
    series2['any if式'] += time.time() - tm

    persons = {p.last_name for p in personlist}
    tm = time.time()
    for _ in range(100000):
        '紀伊田' in persons
    series2['in'] += time.time() - tm

    persons = {p.last_name == '紀伊田' for p in personlist}
    tm = time.time()
    for _ in range(100000):
        any(persons)
    series2['any'] += time.time() - tm

    persons = {True for p in personlist if p.last_name == '紀伊田'}
    tm = time.time()
    for _ in range(100000):
        any(persons)
    series2['any if'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        pass
    series2['forのみ'] += time.time() - tm

series2 /= trials

# ジェネレーター式
series3 = pd.Series(0., index=index)
series3['in'] = None
series3['any'] = None
series3['any if'] = None
series3['next if'] = None

for _ in range(trials):
    tm = time.time()
    for _ in range(100000):
        '紀伊田' in (p.last_name for p in personlist)
    series3['in 式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        any(p.last_name == '紀伊田' for p in personlist)
    series3['any 式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        any(True for p in personlist if p.last_name == '紀伊田')
    series3['any if式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        next((True for p in personlist if p.last_name == '紀伊田'), False)
    series3['next if式'] += time.time() - tm

    tm = time.time()
    for _ in range(100000):
        pass
    series3['forのみ'] += time.time() - tm

series3 /= trials

df = pd.DataFrame({
    'リスト内包表記': series1,
    'セット内包表記': series2,
    'ジェネレータ式': series3,
})
df.T