查找bisect python范围内的数字

Question

我有一个整数列表,我想写一个函数,返回一个范围内的数字子集.像NumbersWithinRange(列表,间隔)函数名称...

也就是说,

list = [4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100]
interval = [4,20]
results = NumbersWithinRange(list, interval)  # [4,4,6,8,7,8]

也许我忘了在结果中再写一个数字,但这就是想法......

该列表可以长达10/20百万,范围通常为几百.

关于如何使用python高效地完成任何建议 - 我正在考虑使用bisect.

谢谢.

Answer 1

我会使用numpy,特别是如果列表那么长.例如:

In [101]: list = np.array([4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100])
In [102]: list
Out[102]: 
array([  4,   2,   1,   7,   9,   4,   3,   6,   8,  97,   7,  65,   3,
         2,   2,  78,  23,   1,   3,   4,   5,  67,   8, 100])
In [103]: good = np.where((list > 4) & (list < 20)) 
In [104]: list[good]
Out[104]: array([7, 9, 6, 8, 7, 5, 8])

# %timeit says that numpy is MUCH faster than any list comprehension: 
# create an array 10**6 random ints b/w 0 and 100
In [129]: arr = np.random.randint(0,100,1000000)
In [130]: interval = xrange(4,21)
In [126]: %timeit r = [x for x in arr if x in interval]
1 loops, best of 3: 14.2 s per loop

In [136]: %timeit good = np.where((list > 4) & (list < 20)) ; new_list = list[good]
100 loops, best of 3: 10.8 ms per loop

In [134]: %timeit r = [x for x in arr if 4 < x < 20]
1 loops, best of 3: 2.22 s per loop 

In [142]: %timeit filtered = [i for i in ifilter(lambda x: 4 < x < 20, arr)]
1 loops, best of 3: 2.56 s per loop

Answer 2

pure-Python Python sortedcontainers模块有一个SortedList类型可以帮助你.它按排序顺序自动维护列表,并经过测试,通过了数千万个元素.排序列表类型具有可以使用的平分功能.

from sortedcontainers import SortedList
data = SortedList(...)

def NumbersWithinRange(items, lower, upper):
    start = items.bisect(lower)
    end = items.bisect_right(upper)
    return items[start:end]

subset = NumbersWithinRange(data, 4, 20)

与扫描整个列表相比,这种方式的对等和索引要快得多.已排序的容器模块非常快,并且具有性能比较页面,其中包含针对替代实现的基准.

Answer 3

如果列表未排序，则需要扫描整个列表：

lst = [ 4,2,1,...]
interval=[4,20]
results = [ x for x in lst if interval[0] <= x <= interval[1] ]

如果列表已排序，您可以使用bisect来查找限制范围的左索引和右索引。

left = bisect.bisect_left(lst, interval[0])
right = bisect.bisect_right(lst, interval[1])

results = lst[left+1:right]

由于扫描列表的时间复杂度为 O( n )，排序的时间复杂度为 O( n lg n )，因此仅仅为了使用而对列表进行排序可能不值得bisect，除非您计划进行大量范围提取。