数据结构 - 我能否在 Python 中提高有限长度 deque(循环缓冲区)中的随机访问速度

Question

我正在用Python编写一个小型日志抓取程序，该程序处理滚动日志文件并将偏移量存储在文件中以用于感兴趣的行。

我最初的解决方案在大文件上运行得相当快，但我没有清除存储的方法，这意味着如果程序继续运行，内存使用量将稳步增加，直到程序消耗所有可用的内存。我的解决方案是将collections.deque与 set 一起使用maxlen以便列表将作为循环缓冲区运行，随着更多日志的出现而丢弃最旧的日志行。

虽然这解决了内存问题，但我在按索引调用 deque 中的项目时面临着重大的性能损失。例如，此代码的运行速度比旧的等效代码慢得多，其中 self.loglines 不是 deque。有没有办法提高它的速度，或者制作一个循环缓冲区，其中随机访问是一个恒定的时间操作(而不是，我假设，O(n((？

    def get_logline(self, lineno):
            """Gets the logline at the given line number.
            Arguments:
            lineno - The index of the logline to retrieve
            Returns: A string containing the logline at the given line number
            """
            start = self.loglines[lineno].start
            end = self.loglines[lineno+1].start
            size = end - start
            if self._logfile.closed:
                    self._logfile = open(self.logpath, "r")
            self._logfile.seek(start)
            logline = self._logfile.read(size)
            return logline

Answer 1

与所有双向链表一样，collections.deque中的随机访问是 O(n(。考虑使用有界列表列表，以便即使有数十万个条目，旧条目(del outer[0](的清除仍然可以及时进行。