使用计算后缀最大值累计工具

Question

计算整数序列后缀最大值的推荐方法是什么？你知道吗

以下是基于问题定义的暴力方法（O(n**2)时间）：

>>> 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]

有没有更像Python的方法？你知道吗

Answer 1

就我个人而言，当我认为“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%，但是对于100000 int的列表，我们讨论的是25ms和17ms，所以这可能没什么关系。你知道吗

如果最关心的是速度，并且您希望看到的数字范围明显小于您正在处理的列表长度，那么使用RLE可能是值得的：

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个int的列表，这比上面的方法快4倍，比itertools方法快2.5倍。同样，如果你的数字范围比你的列表长度小得多，那么它也会占用更少的内存。你知道吗

Answer 2

切片反转使内容更简洁，嵌套更少：

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]