给定一个降序列表,例如[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]
这是蟒蛇的方式,但我们不使用递减属性,并且当发现一个不大于阈值的元素时,就不能爆发。如果满意的元素很少,但orial列表很大,则性能不好。
方法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)
然而,这段代码并不是很像蟒蛇。
有没有一种方法可以让我把蟒蛇的风格和表演结合起来?
Python 3.10+
二进制搜索是快速排序数据,O(log n(时间。Python的bisect
模块已经做到了。它希望增加数据,而您的正在减少,但我们实际上可以使其增加。只需使用其闪亮的新key
参数来否定O(logn(访问的元素(并搜索否定的阈值(:
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,即比较每个元素的列表理解,您写道:"如果满意的元素很少,但orial列表很大,则性能不好">。如果这不仅仅是一个反对列表理解的论点,而且你确实有大多数非常的满足元素和一个很长的列表,那么指数搜索可能比二进制搜索更好。但这将是更多的代码(我想,除非你找到一个包(。
在这种极端情况下,像Method2(我确实觉得这是蟒蛇式的(、Chris的答案或itertools.takewhile
这样的简单迭代搜索也会很快,但对于满足元素数的情况,它们会比二进制搜索和指数搜索慢得多。
itertools.takewhile
就像我说的,一般情况下它会更慢,但在最好的情况下它很快,而且它非常简单和干净:
from itertools import takewhile
lst = list(takewhile(lambda x: x > threshold, orgin_lst))
更快的循环
就像我说的,我确实觉得你的环形蟒蛇,这对最好的情况很好。但是调用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]
我认为您的代码非常接近:
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]
>>>