查找排序列表中元素的索引

Question

我有一個排序列表l（大約20000個元素），並且希望找到l中超出給定值t_min的第一個元素。目前，我的代碼如下。

def find_index(l): 
    first=next((t for t in l if t>t_min), None) 
    if first==None: 
     return None 
    else: 
     return l.index(first) 

的基準代碼，我用cProfile運行一個測試循環，以及由時間與一個控制迴路剝離出來隨機生成列表所需的時間：

import numpy 
import cProfile 

def test_loop(n): 
    for _ in range(n): 
     test_l=sorted(numpy.random.random_sample(20000)) 
     find_index(test_l, 0.5) 

def control_loop(n): 
    for _ in range(n): 
     test_l=sorted(numpy.random.random_sample(20000)) 

# cProfile.run('test_loop(1000)') takes 10.810 seconds 
# cProfile.run('control_loop(1000)') takes 9.650 seconds 

每個函數調用對於find_index需要約1.16毫秒。考慮到我們知道列表已排序，是否有改進代碼的方法以使其更有效？

Answer 1

標準庫bisect模塊對此和文檔contain an example是有用的正是這種用例。

def find_gt(a, x): 
    'Find leftmost value greater than x' 
    i = bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError