使用itertools.accumulate计算后缀最大值
使用itertools.accumulate计算后缀最大值
提问于 2018-02-20 22:58:22
计算整数序列后缀最大值的推荐方法是什么？
以下是基于问题定义的蛮力方法(O(n**2)time)：
>>> A
[9, 9, 4, 3, 6]
>>> [max(A[i:]) for i in range(len(A))]
[9, 9, 6, 6, 6]使用O(n)的一种itertools.accumulate()方法如下所示，它使用两个列表构造函数：
>>> A
[9, 9, 4, 3, 6]
>>> list(reversed(list(itertools.accumulate(reversed(A), max))))
[9, 9, 6, 6, 6]有没有更多的琵琶方法可以做到这一点？
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-02-20 23:20:21
切片反转使事情更简洁，更少嵌套：
list(itertools.accumulate(A[::-1], max))[::-1]不过，您仍然希望将其捆绑到一个函数中：
from itertools import accumulate
def suffix_maximums(l):
return list(accumulate(l[::-1], max))[::-1]如果你在使用NumPy，你会想要numpy.maximum.accumulate
import numpy
def numpy_suffix_maximums(array):
return numpy.maximum.accumulate(array[::-1])[::-1]Stack Overflow用户
发布于 2018-02-20 23:41:31
就我个人而言，当我想到" Pythonic“时，我会想到”简单易懂“，下面是我的Pythonic版本：
def suffix_max(a_list):
last_max = a[-1]
maxes = []
for n in reversed(a):
last_max = max(n, last_max)
maxes.append(last_max)
return list(reversed(maxes))就其价值而言，这看起来比itertools.accumulate方法慢了大约50%，但是我们谈论的是25毫秒对17毫秒的100000个ints的列表，所以这可能并不重要。
如果最关心的是速度，并且您期望看到的数字范围比您正在处理的列表长度小得多，那么使用雷尔可能是值得的。
def suffix_max_rle(a_list):
last_max = a_list[-1]
count = 1
max_counts = []
for n in a_list[-2::-1]:
if n <= last_max:
count += 1
else:
max_counts.append([last_max, count])
last_max = n
count = 1
if n <= last_max:
max_counts.append([last_max, count])
return list(reversed(max_counts))对于范围为0~10000的100000个ints的列表，这大约比上面的速度快4倍，比迭代工具方法快2.5倍。如果您的数字范围明显小于您的列表的长度，它将占用更少的内存，同样。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48895575
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号