python - Python 中 f.seek() 的复杂性

Question

f.seek(500000,0) 是否在到达第 500000 个之前遍历文件的所有前 499999 个字符？换句话说，f.seek(n,0) 的阶数是 O(n) 还是 O(1)？

Answer 1

您需要更具体地说明 f 是什么类型的对象。

如果 f 是一个正常的 io module对于存储在磁盘上的文件对象，您必须确定您是否正在处理:

• 原始二进制文件对象
• 一个缓冲对象，包装原始二进制文件
• 一个 TextIO 对象，包装缓冲区
• 内存中的 BytesIO 或 TextIO 对象

第一个选项只使用 lseek system call重新定位文件描述符位置。此调用是否为 O(1) 取决于操作系统和您拥有的文件系统类型。对于具有 ext4 文件系统的 Linux 系统，lseek is O(1) .

缓冲区只是清除缓冲区 if your seek target is outside of the current buffered region并读入新的缓冲区数据。这也是 O(1)，但固定成本更高。

对于文本文件，事情要复杂得多，因为可变字节长度编解码器和行尾翻译意味着您不能总是将二进制流位置映射到文本位置而不从头开始扫描。该实现不允许非零当前位置或结束相对寻道，并且最好尽量减少绝对寻道所读取的数据量。 Internal state shared with the text decoder跟踪 recent 'safe point' to seek back to并向前阅读到所需的位置。最坏的情况是 O(n)。

内存中的文件对象实际上只是很长的可寻址数组。寻找是 O(1)，因为您可以改变当前位置指针值。

有许多其他类似文件的对象可能支持也可能不支持查找。他们如何处理搜索取决于实现。

• zipfile module支持对以只读模式打开的 zip 文件进行搜索，搜索到位于当前缓冲区覆盖的数据部分之前的点需要完全重新读取数据并解压缩到所需点，搜索后需要从中读取当前位置，直到到达新位置。 gzip , lzma和 bz2模块都使用 same shared implementation ，那也是starts reading from the start if you seek to a point before the current read position (并且没有更大的缓冲区可以避免这种情况)。

• chunk module允许在 block 边界内查找并委托(delegate)给底层对象。如果底层文件查找操作是 O(1)，则这是一个 O(1) 操作。

等等。所以，视情况而定。