python：从大于阈值的降序列表中获取子列表的高效且Pythonic的方法

Question

给定一个降序列表，例如[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, -1, -2, -2]和threshold = 1.2，我想从原始列表中获取子列表，其中所有元素都大于threshold

方法一：

orgin_lst = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, -1, -2, -2]
lst = [i for i in orgin_lst if i > threshold]

这是Pythonic方式，但我们不使用降序属性，并且当找到不大于阈值的元素时无法突破。如果满足的元素很少，但原始列表很大，则性能不好。

方法二：

orgin_lst = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, -1, -2, -2]
lst = []
for i in orgin_lst:
    if i <= threshold:
        break
    lst.append(i)

然而这段代码不太Pythonic。

有没有一种方法可以将 pythonic 风格和性能结合起来？

Answer 1

Python 3.10+

对于已排序的数据，二分查找速度很快，时间为 O(log n)。Python 的bisect模块已经做到了这一点。它想要增加数据，而你的数据正在减少，但我们实际上可以让它增加。只需使用其闪亮的新key参数来否定 O(log n) 访问的元素（并搜索否定阈值）：

from bisect import bisect_left
from operator import neg

i = bisect_left(orgin_lst, -threshold, key=neg)
lst = orgin_lst[:i]

或者，使用一个键函数，该函数返回False大于阈值的值，True否则返回。由于False小于True（它们的作用分别类似于0和1），我们再次得到一个单调递增序列，并且可以bisect与此一起使用：

from bisect import bisect

i = bisect(orgin_lst, False, key=lambda x: x <= threshold)
lst = orgin_lst[:i]

如果您不需要单独的新列表，del orgin_lst[i:]则可以使用删除不需要的元素。

Python 3.10 之前

以前我会编写一个代理类来完成现在由更方便的关键参数完成的工作：

from bisect import bisect_left

class Negate:
    def __getitem__(_, i):
        return -orgin_lst[i]

i = bisect_left(Negate(), -threshold, 0, len(orgin_lst))
lst = orgin_lst[:i]

或者我可能自己编写了二分搜索，但我已经这样做了很多次，以至于在某些时候我开始讨厌它。

指数搜索

在您的 Method1 下，比较每个元素的列表理解，您写道：“如果满足的元素很少，但原始列表非常大，则性能不好”。如果这不仅仅是反对列表理解的论点，而且实际上您确实几乎没有满足的元素和很长的列表，那么指数搜索可能比二分搜索更好。但它会是更多的代码（除非你找到它的包，我猜）。

在这种极端情况下，像您的 Method2 （顺便说一句，我确实找到了 pythonic）或 Chris 的答案或 with 之itertools.takewhile类的简单迭代搜索也会很快，但对于具有大量满足元素的情况，它们会比二分搜索慢得多，指数搜索。

itertools.takewhile

就像我说的，一般来说它会慢一些，但对于那些最好的情况来说它很快，而且非常简单和干净：

from itertools import takewhile

lst = list(takewhile(lambda x: x > threshold, orgin_lst))

更快的循环

就像我说的，我确实找到了你的循环 pythonic，并且它对于最好的情况很有用。但是调用append将元素单独附加到结果中的成本相当高。首先找到第一个太小的元素，然后找到它的索引和切片可能会更快：

for i in orgin_lst:
    if i <= threshold:
        lst = orgin_lst[:orgin_lst.index(i)]
        break
else:
    lst = orgin_lst[:]

再次强调，如果您同意从现有列表中删除不需要的元素，请del在 the 内部使用if，然后您不需要else此处的部分。

我为另一个问题编写的类似解决方案最终在基准测试中排名第二。

替代实施：

cut = None
for i in orgin_lst:
    if i <= threshold:
        cut = orgin_lst.index(i)
        break
lst = orgin_lst[:cut]