在一个范围内查找数字对分python

Question

我有一个整数列表，我想写一个函数，返回一个范围内的一个子集。比如NumbersWithinRange（list，interval）函数名。。。在

也就是说

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]

也许我忘了在结果里再写一个数字，但这就是我的想法。。。在

列表可以大到1000/2000万的长度，范围通常是几百个。在

关于如何使用python高效地实现这一点的任何建议-我正在考虑使用bisect。在

谢谢。在

Answer 1

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

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

如果列表是排序的，则可以使用bisect来查找 限制你的射程。在

^{pr2}$

因为扫描列表是O（n），排序是O（nlgn），所以除非您计划进行大量的范围提取，否则仅仅为了使用bisect对列表进行排序可能是不值得的。在

Answer 2

纯Python Python sortedcontainers module有一个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)

这种方法比扫描整个列表要快得多。sortedcontainers模块非常快，并且有一个performance comparison页面，其中包含针对替代实现的基准测试。在

Answer 3

我会用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