python - Python では、並べ替えられたリストでしきい値を超える最初の値のインデックスをどのように見つけますか?

Question

Python では、並べ替えられたリストでしきい値を超える最初の値のインデックスをどのように見つけますか?

これを行う方法はいくつか考えられますが (線形検索、手書きの二分法など)、クリーンで合理的に効率的な方法を探しています。これはおそらくかなり一般的な問題なので、経験豊富な SO 担当者がお手伝いできると確信しています。

ありがとう！

Answer 1

bisectを見てください。

import bisect

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

bisect.bisect(l, 55) # returns 7

線形検索と比較します。

timeit bisect.bisect(l, 55)
# 375ns


timeit next((i for i,n in enumerate(l) if n > 55), len(l))
# 2.24us


timeit next((l.index(n) for n in l if n > 55), len(l))
# 1.93us

Answer 2

itertoolsを使用した列挙/ジェネレーターアプローチよりも良い時間を得ることができます。itertoolsは、私たち全員のパフォーマンスマネージャーに、基盤となるアルゴリズムのより高速な実装を提供すると思います。しかし、bisectはまだ速いかもしれません。

from itertools import islice, dropwhile

threshold = 5
seq = [1,4,6,9,11]
first_val = islice(dropwhile(lambda x: x<=threshold, seq),0,1)
result = seq.index(first_val)

イディオム/速度に関しては、ここに示されているバイセクトアプローチと、ドキュメントの例で質問にリストされているアプローチとの違いについて疑問に思います。これらは値を見つけるためのアプローチを示していますが、最初の行に切り捨てられ、インデックスを返します。「bisect」ではなく「bisect_right」と呼ばれているので、おそらく一方向からしか見えないと思います。あなたのリストがソートされていて、それ以上のものが欲しいとすれば、これは最大の検索経済かもしれません。

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value(switching this to index) greater than x'
    return bisect_right(a, x)

興味深い質問です。