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

Question

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

pythoniterationlist-comprehensionlazy-evaluation

4

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

方法1：

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的方法，但我们没有使用降序属性，也不能在找到一个不大于阈值的元素时退出。如果有很少满足条件的元素，但原始列表非常大，性能就不好。

方法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)

然而，这段代码还不够符合Pythonic风格。

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

- maplemaple

@j1-lee 这是面试问题的一部分。面试官希望我提高最佳性能并保持代码简洁。 - maplemaple

1

@j1-lee 那个问题不是关于排序列表的，因此那里的答案不包括此问题的最佳解决方案。请重新打开。(或者找到一个真正的重复项...如果有的话，我不会感到惊讶。) - Kelly Bundy

@Shayan 过滤器将遍历整个列表，不使用降序属性。假设第一个元素小于阈值，则实际上我们可以在 O(1) 时间内得到结果为空的列表。然而，这种方法仍然是 O(n)。 - maplemaple

@maplemaple 没错，我明白你的意思。不错的问题。 - Shayan

@j1-lee 谢谢。我刚刚注意到另一个区别：那个问题想要列表的后缀，而这个问题想要一个前缀。这意味着我甚至不能在这里应用我的基准测试赢家 :-) - Kelly Bundy

显示剩余2条评论

2个回答

1

我认为你的代码非常接近:

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(take_until(lambda x: x <= 1.2, lst))
[10, 9, 8, 7, 6, 5, 4, 3, 2]
>>>

- Chris

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kelly Bundy · Accepted Answer

Python 3.10+

二分查找对于有序数据快速，并且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的答案或使用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[:]

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

我为另一个问题撰写的类似解决方案在那里的基准测试中排名第二快。

替代实现：

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