[SOLVED] More efficient way to handle big lists in python?


I’m writing a python script to solve this exercise:

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.

The script I wrote works fine with N<1000 but when I try it with greater values, it just keeps running without ending. I guessed it’s too slow because of the 3 for-loops and the many .append() to big lists, but how can I solve that? Or am I wrong and there is another problem I don’t see?

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):
        if (len(subseq) > 0):
for max in maxs:
    f_out.write(str(max) + " ")

Here are some examples of input and output.


Algorithm from GeeksforGeeks (with some readability improvements):

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

        if s:
            auxiliary[i] = s[-1]

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:

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

Answered By – Marco Valle

Answer Checked By – Willingham (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *