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

我有一个排序列表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毫秒。考虑到我们知道列表已排序，是否有改进代码的方法以使其更有效？

来源

2014-04-30 Vincent Tjeng

你不能使用'search_sorted'吗？ – EdChum

您是指http://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html？ –

是的，如果你可以使用numpy数组并且它被排序，那么这将会很快，你基本上会做'np.searchsorted（my_array，find_val，side ='right'）' – EdChum

标准库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

来源

2014-04-30 14:34:49 bgporter

感谢您的回答 - 我不知道对分。不过，我认为我在寻找'find_gt'而不是索引。 –

有一个挂起的编辑来解决这个问题。 – chepner

谢谢@chepner。我应该先检查一下。 –

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

回答

相关问题