在 python 中处理大列表的更有效方法？

Question

我正在编写一个 python 脚本来解决这个练习：

Given in input a vector V of N integers we want to find, for each size between 1 and N, the maximum of the minimum’s of every contiguous subsequence in the vector.

我编写的脚本在 N<1000 时工作正常，但当我尝试使用更大的值时，它只是保持运行没有结束。我猜它太慢了，因为有 3 个 for 循环和许多 .append() 到大列表，但我该如何解决呢？还是我错了，还有另一个我没有看到的问题？

f_name = input("Inserire nome del file: ")
 
f_in = open("inputs/"+f_name, "r")
f_out = open("outputs/"+f_name, "w")
 
# n = int(input())
n = int(f_in.readline())
 
v_s = f_in.readline().rstrip('\n').split()
v = [int(i) for i in v_s]
 
maxs = []
 
for size in range(1, n+1):
    mins = []
    for i in range(n):
        subseq = []
        if (i+size <= n):
            for j in range(size):
                subseq.append(v[i+j])
        if (len(subseq) > 0):
            mins.append(min(subseq))
    maxs.append(max(mins))
 
for max in maxs:
    f_out.write(str(max) + " ")
 
f_in.close()
f_out.close()

Here are some examples of input and output.

Answer 1

python 中的追加速度非常快，但是您的算法太慢了——您有三个嵌套循环，每个循环都有 N 个元素，总复杂度为 O(n^3) .

这意味着通过仔细优化，也许您可以处理 2000 个值或 3000 个值...但是您最大的示例是 500000 个值，所以这不会有帮助。

如果你想解决这个问题，你需要重写程序，让它没有三个嵌套循环。这个问题是well-known，你可以在网上找到解决方案，没有嵌套循环，O(n) 复杂度。

Answer 2

来自 GeeksforGeeks 的算法（具有一些可读性改进）：

def fill(array, auxiliary, my_range):
    s = []
    for i in my_range:
        while s and array[s[-1]] >= array[i]:
            s.pop()

        if s:
            auxiliary[i] = s[-1]
        s.append(i)


def solution(array, n, left, right):
    ans = [0] * (n + 1)
    for i in range(n):
        my_len = right[i] - left[i] - 1
        ans[my_len] = max(ans[my_len], array[i])

    for i in range(n - 1, 0, -1):
        ans[i] = max(ans[i], ans[i + 1])
    return ans[1:]


def main(filename):

    with open("{}/{}".format("input", filename), "r") as fp:
        lines = fp.readlines()

    n = int(lines[0])
    v = [int(s.strip()) for s in lines[-1].split()]

    left = [-1] * (n + 1)
    right = [n] * (n + 1)

    fill(v, left, range(n))
    fill(v, right, range(n-1, -1, -1))
    result = solution(v, n, left, right)
    result = [str(res) for res in result]

    output = " ".join(result)
    with open("{}/{}".format("output", filename), "w") as fp:
        fp.write(output)
    print(output)


if __name__ == '__main__':
    f_name = input("Inserire nome del file: ")
    main(f_name)

在 python 中处理大列表的更有效方法？

More efficient way to handle big lists in python?

python

algorithm

performance

list