Python在列表或数组中查找范围内的数字

Question

我有一个数值列表，其中包含数百万个数字，这些数字总是逐渐增加到末尾。我需要查找并返回指定范围内的数字，例如大于X但小于Y的数字。列表中的数字可能会发生变化，我要搜索的值也会随之改变。

我一直在使用以下方法，请注意，这只是一个基本示例，数字不是均匀或与程序中显示的相同。

l = [i for i in range(2000000)]
nums = []
for element in l:
    if element > 950004:
        break
    if element > 950000:
        nums.append(element)
#[950001, 950002, 950003, 950004]

虽然速度很快，但由于我的程序所做的事情需要更快一些，因为数字变化很大，所以我想知道是否有更好的方法可以使用pandas系列或numpy数组来完成？但到目前为止，我只是用numpy做了一个例子：

a = numpy.array(l,dtype=numpy.int64)

使用Pandas序列更有效吗？利用query()函数可以实现什么功能？如果使用数组而不是Python对象的列表，最佳方法是什么？

- ragardner

---

你是否正在尝试筛选列表中在一组值之间的数字？ - James

也许使用二分查找来搜索范围边界的索引会更快。 - Calculator

这是每次运行脚本都要选择两个数字的问题吗？ - erasmortg

这些值按递增顺序排序了吗？ - Maor Veitsman

@new_to_coding 正如 @Caculator 所述，基于二分查找算法的解决方案可能会很有趣。在这个问题中，bisect包被建议在评论中使用。据我所知，这个包几乎可以解决你的问题。 - Unatiel

Answer 1

这里有一个使用二分查找的解决方案。你谈论的是数百万个数字。从技术上讲，通过二分查找将算法的运行时间复杂度降至O(log n)，忽略最后的切片步骤。

import bisect

l = [i for i in range(2000000)]
lower_bound = 950000
upper_bound = 950004

lower_bound_i = bisect.bisect_left(l, lower_bound)
upper_bound_i = bisect.bisect_right(l, upper_bound, lo=lower_bound_i)
nums = l[lower_bound_i:upper_bound_i]

- Calculator

---

不知怎么，它比numpy的布尔片段略快O_o; - ragardner

谢谢，如果不是通过文档浏览，我可能找不到这个解决方案。 - ragardner

еңЁbisect.bisect_rightдёӯдҪҝз”ЁеҸӮж•°lo=lower_bound_iеҸҜд»ҘдҪҝе…¶жӣҙеҠ й«ҳж•ҲгҖӮ - ekhumoro

@new_to_coding，你是指这个列表切片吗？是的，布尔切片创建一个与当前数组大小相同的完整布尔数组。Python列表切片非常快速和高效，是用C实现的。 - juanpa.arrivillaga

Answer 2

以下是两种二分查找的实现（基于此处的代码） - 一种搜索上限，另一种搜索下限。这对你有帮助吗？

def binary_search_upper(seq, limit):
    min = 0
    max = len(seq) - 1
    while True:
        if max < min:
            return -1
        m = (min + max) / 2
        if m == (len(seq) -1) or (seq[m] <= limit and seq[m+1] > limit):
            return m
        elif seq[m] < limit:
            min = m+1
        else:
            max = m - 1

def binary_search_lower(seq, limit):
    min = 0
    max = len(seq) - 1
    while True:
        if max < min:
            return -1
        m = (min + max) / 2
        if m == 0 or (seq[m] >= limit and seq[m-1] < limit):
            return m
        elif seq[m] < limit:
            min = m+1
        else:
            max = m - 1


l = [i for i in range(2000000)]
print binary_search_upper(l, 950004)
print binary_search_lower(l, 950000)

- Maor Veitsman

---

你为什么要使用这个已经超过14年的配方，而不是标准库实现（它将具有更好的常数因子）？ - juanpa.arrivillaga

JFTR，这比“bisect”慢大约十倍。 - ekhumoro

@ekhumoro 很有趣，我在哪里可以了解更多关于bisect为什么如此快的信息？ - Maor Veitsman

@MaorVeitsman. 这个模块的源代码展示了一个纯Python实现，但是真正的实现是用C语言编写的。 - ekhumoro

@MaorVeitsman。PS：纯Python bisect实现的速度大约是你的两倍 :P - ekhumoro

Answer 3

你可以使用numpy通过布尔切片获取列表的子集。

import numpy as np
a = np.arange(2000000)
nums = a[(950000<a) & (a<=950004)]
nums
# returns
array([950001, 950002, 950003, 950004])

- James

---

我的程序中数字不一样，这只是一个基本的例子，抱歉。 - ragardner

这将获取整个数组中的所有数字，并在达到停止条件后不退出。 - Moses Koledoye