在Python中快速比较数字是否在范围列表中

Question

我需要把一组数字和一组范围进行比较，看看这些数字是否在任何一个范围内。

举个例子：

list1 = [23,100,1,50,60,73]
list2 = [[0-10],[25-35],[100-110],[75-85]]

所以我需要遍历第一组数字，把每个数字和范围列表进行比较，看看这个数字是否落在任何一个范围内。如果是的话，我就会把那个范围的计数器加一。

这两组列表都会非常大（可能有十万到几百万个数字或者更多），而且这些数字是随机的。

那么，处理这个问题的最佳方法是什么呢？

补充一下，列表的格式可以是像 [低值, 高值, 计数器] 这样的形式。上面的例子只是数据样本，并不完全符合 Python 代码的语法。这两组列表都会很庞大。

另外，这些数字都是整数。

谢谢。

Answer 1

一种简单的方法是把第二个列表变成元组（或者两个元素的列表），然后使用 any 函数：

list1 = [23,100,1,50,60,73]
list2 = [(0,10), (25,35), (100,110), (75,85)]

[any(y[0] <= x <= y[1] for y in list2) for x in list1]

使用 timeit 测试的结果是：

100000 loops, best of 3: 4.17 us per loop

---

现在，我假设你的范围是包含边界的，也就是说像85和25这样的数字是包括在内的。如果 list1 中的数字是整数，而 list2 是静态的（也只包含整数，并且范围是不重叠的），那么你可以把它们扁平化，排序，然后把边界移动0.5来处理边界情况，这样你就可以使用非常高效的 bisect 算法，复杂度是 O(log(N))：

list2 = [(0,10),(25,35),(100,110),(75,85)]
list2 = [x for tup in list2 for x in tup]
list2.sort()
list2 = [l - 0.5 + i%2 for i,l in enumerate(list2)]
timeit [bisect_left(list2, x)%2 == 1 for x in list1]
100000 loops, best of 3: 1.64 us per loop

这种方法的可读性稍差，因为你有一堆数字，但没有明显的标记来指示左边界和右边界在哪里。不过，它的速度更快，扩展性也更好。在这里，如果 list1 中的数字落在一个偶数索引的位置，它就处于范围之间，否则，它就在范围内。

---

不过，这种方法的速度还是比直接把所有数字存储在集合中并使用 in 要慢（这种方法只适用于 list1 中的数字都是 int）：

list3 = set(range(0,11) + range(25,36) + range(100,111) + range(75,86))
[x in list3 for x in list1]

结果是：

1000000 loops, best of 3: 376 ns per loop

这个解决方案可能不适合你，因为如果你的第二个列表确实很大，它可能根本无法放进内存里。