Time Limit Exceeded в задаче на очередь Python

Question

Задача про очередь в Python

Задали лабораторную в институте по написанию очереди в python, задачу решил, загрузил на платформу (ejudge), но вот на 13 тесте выдало ошибку "Превышено время работы программы >3 сек", в чем проблема вообще понять не могу. Вот условие:

Задача про очередь Реализуйте очередь, используя только массив. Ввод и вывод данных осуществляется через файлы. Имена входного и выходного файлов задаются через аргументы командной строки (первый и второй соответственно). Формат входных данных Во входном файле задаётся последовательность команд. Пустые строки игнорируются. Первая строка всегда содержит "set_size N", где N - максимальный размер очереди, целое число. Каждая последующая строка содержит ровно одну команду: push X, pop или print, где X - произвольная строка без пробелов. Формат результата Команда print выводит содержимое очередь (от головы к хвосту) одной строкой, значения разделяются пробелами. Если очередь пуста, то выводится "empty". В случае переполнения очереди выводится "overflow". Команда pop выводит элемент или "underflow", если очередь пуста. Память под очередь должна быть выделена не более одного раза, при вызове команды "set_size". В любой непонятной ситуации результатом работы любой команды будет "error".

import sys
class Queue:
    def __init__(self, size):
        self.queue = []
        self.size = size
    def push(self, value):
        if len(self.queue) < self.size:
            return self.queue.append(value)
        else:
            return 'overflow'
    def pop(self):
        if self.queue:
            first = self.queue[0]
            del self.queue[0]
            return first
        else:
            return 'underflow'
    def print(self):
        global text
        if len(self.queue) > 0:
            for i, element in enumerate(self.queue):
                if i + 1 < len(self.queue):
                    text += element + ' '
                else:
                    text += element
        else:
            text += 'empty'
        text += '\n'
        return
names = []
if __name__ == "__main__":
    for args in sys.argv[1:]:
        names.append(args)
in_file = names[0]
out_file = names[1]
f = open(in_file)
defined = False
text = ''
for i in f:
    com = i.strip('\n')
    if com.split(' ')[0] == 'set_size' and not defined:
        size = int(com.split(' ')[1])
        q = Queue(size)
        defined = True
    elif com == 'pop' and defined:
        text += q.pop() + '\n'
    elif com.split(' ')[0] == 'push' and len(com.split(' ')) == 2 and defined:
        value = com.split(' ')[1]
        pt = q.push(value)
        if pt is not None:
            text += pt + '\n'
    elif com == 'print' and defined:
        q.print()
    elif com == '':
        continue
    else:
        text += 'error\n'
f.close()
f = open(out_file, 'w')
f.write(text)
f.close()

Окно выполнения тестов, на 13, почему то выдало ошибку

Для понятности залил на этот гит два файла, "input" - файл, который платформа тестирования подает на вход, а "output", это правильный ответ на задачу. Мою программу принудительно остановили (из-за превышения времени), и она ничего не выдала https://github.com/RoyalGoose/testrepos

В чем может быть проблема? Как я могу исправить код, чтобы он работал быстрее и прошел бы этот тест?

Answer 1

Вы очень много держите в результирующем буфере (переменная text). Интерполяция строк, да и сама работа со строками, никогда не была дешевой. Тем более если держать в памяти огромную строку. Для решения данной проблемы - старайтесь писать результат по строчно. То есть - обработали одно сообщение - записали ответ в файл. Или используйте коллекцию строк. Тем более Вы еще читаете сначала в очередь весь входной файл - следовательно много объектов в памяти в один момент времени.

Можно еще по другому сделать - читать в очередь N элементов из входного файла, обрабатывать очередь, записать N результатов в выходной файл и опять приняться за чтение входного файла. Так или иначе - фигурирует очередь. Так или иначе - получается порционная работа. Вы держите в памяти ровно N элементов.

Много работы со строками. Вы сначала строку сепарируете на массив строк, потом по индексам проверяете строки. Попробуйте использовать регулярные выражения!

Answer 2

Переделал ваш вариант, не проверял все ли учтено и полностью ли соответствует задаче, но на вид результат похож и должно работать быстрее

class Queue:
    def __init__(self, file_in, file_out):
        self.size = None
        self.queue = []
        self.file_in = file_in
        self.file_out = file_out
        return

    def set_size(self, size):
        try:
            assert self.size is None
        finally:
            self.size = int(size)
            self.queue.clear()

    def push(self, value):
        self.queue.append(value if len(self.queue) < self.size else 'overflow')

    def pop(self):
        return (self.queue.pop(0) if self.queue else 'underflow') + '\n'

    def print(self):
        return (' '.join(self.queue) if self.queue else 'empty') + '\n'

    def work(self):
        with open(self.file_in) as f, open(self.file_out, 'w') as f2:
            fr = filter(bool, map(str.rstrip, f))
            for line in fr:
                try:
                    try:
                        (cmd, arg) = line.split(' ', 1)
                    except ValueError:
                        f2.write(getattr(self, line)())
                    except Exception:
                        raise
                    else:
                        getattr(self, cmd)(arg)
                except Exception as e:
                    f2.write('error\n')
                continue
        return


if __name__ == '__main__':
    q = Queue('input', 'outfile')
    q.work()

Answer 3

del self.queue[0]

Подозреваю что это выполняется за линейное время, а не за константное.

Делай циклическую очередь и храни индекс начала.

БЛОГ НА HUSL

Time Limit Exceeded в задаче на очередь Python

Задача про очередь в Python

Ответы (3 шт):