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]

或者，对于大于阈值的值，使用 returns 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

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

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]

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

指数搜索

根据您的方法 1，列表理解比较每个元素，您写道： "如果满足的元素很少，但原始列表非常大，性能不好。如果这不仅仅是反对该列表理解的论点，但你实际上确实有大部分 very 几个令人满意的元素和一个 very 长列表，那么 exponential search 可能比二进制搜索更好。但这会是更多的代码（除非你找到它的包，我猜）。

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

`itertools.takewhile`

就像我说的一般来说它会更慢，但对于那些 best-cases 来说它很快而且它非常简单干净：

from itertools import takewhile

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

更快的循环

就像我说的那样，我发现你的循环 pythonic，它对 best-cases 很有用。但是调用 append 将元素单独附加到结果是非常昂贵的。首先找到第一个太小的元素，然后找到它的索引和切片可能会更快：

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

同样，如果您可以从现有列表中删除不需要的元素，请在 if 中使用 del 然后您不需要 else 部分这里。

一个 I wrote for another question ended up second-fastest in the .

替代实施：

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

Answer 2

我认为您的代码非常接近：

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)

但是让我们使用一个生成器。

def take_until(f, it):
    for x in it:
        if f(x): return
        yield x

现在，我们可以编写类似下面的内容，例如。

>>> for x in take_until(lambda x: x <= 1.2, lst):
...     print(x)
...
10
9
8
7
6
5
4
3
2
>>>

哎呀，如果我们真的想要 list，那也很简单。

>>> list(take_until(lambda x: x <= 1.2, lst))
[10, 9, 8, 7, 6, 5, 4, 3, 2]
>>>

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

python: efficient and pythonic way to get sublist from a descending list which is larger than threshold

python

iteration

list-comprehension

lazy-evaluation

Python 3.10+

之前 Python 3.10

指数搜索

`itertools.takewhile`

更快的循环