主页 / 问题 / 1183462
Accepted
RoyalGoose
Asked:2020-09-28 19:27:46 +0800 CST2020-09-28 19:27:46 +0800 CST

Python 队列任务中超过时间限制

  • 772

Python中的队列任务

他们在研究所设置了一个实验室，用于用python编写队列，解决了问题，将其上传到平台（ejudge），但是在第13次测试它给出了错误“程序时间超过> 3秒”，我无法理解问题是什么。这是条件：

队列问题 仅使用数组实现队列。数据的输入和输出是通过文件进行的。输入和输出文件的名称通过命令行参数（分别为第一个和第二个）指定。输入数据格式 输入文件指定命令序列。空行被忽略。第一行始终包含“set_size N”，其中 N 是最大队列大小，一个整数。随后的每一行只包含一个命令：push X、pop 或 print，其中 X 是没有空格的任意字符串。结果格式 print 命令将队列的内容（从头到尾）打印在一行上，用空格分隔。如果队列为空，则显示“empty”。如果队列溢出，则显示“溢出”。pop 命令输出一个元素或“下溢” 如果队列为空。调用“set_size”命令时，队列的内存必须分配不超过一次。在任何不清楚的情况下，任何命令的结果都将是“错误”。

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，由于某种原因报错 在此处输入图像描述

为了清楚起见，我向这个 git 上传了两个文件，“input”是测试平台作为输入提交的文件，“output”是任务的正确答案。我的程序被强行停止（由于超时）并且没有返回任何东西 https://github.com/RoyalGoose/testrepos

可能是什么问题呢？如何修复代码以使其运行更快并通过此测试？

python

3 个回答

    1. text您在结果缓冲区（变量）中持有很多。字符串插值和字符串操作本身从未便宜过。特别是如果您在内存中保留了一个巨大的字符串。要解决这个问题 - 尝试逐行编写结果。也就是说 - 处理了一条消息 - 在文件中写下答案。或者使用字符串集合。此外，您仍然首先将整个输入文件读入队列 - 因此内存中一次有许多对象。

    您可以采取不同的方式 - 从输入文件中读取 N 个元素到队列中，处理队列，将 N 个结果写入输出文件，然后再次开始读取输入文件。一种或另一种方式，有一个队列。一种或另一种方式 - 结果是一件工作。您在内存中恰好保存了 N 个元素。

    1. 大量的字符串工作。您首先将字符串分成字符串数组，然后按索引检查字符串。尝试使用正则表达式！
    • 1
  2. Best Answer

    我重做了您的版本，没有检查是否考虑了所有内容以及是否完全对应任务，但结果看起来相似并且应该更快

    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()
    • 1 
  3. del self.queue[0]

    我怀疑这是在线性时间内完成的，而不是恒定时间。

    做一个循环队列并存储起始索引。

    • 1

相关问题