在一个范围内查找数字对分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

纯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页面，其中包含针对替代实现的基准测试。在