Python 中 f.seek() 的复杂性
Complexity of f.seek() in Python
f.seek(500000,0) 是否在到达第 500000 个之前检查了文件的所有前 499999 个字符？
换句话说，f.seek(n,0) 的阶数是 O(n) 还是 O(1)？
这取决于f的实现。但是，在普通文件系统文件中，它是 O(1)。
如果 python 在文本文件上实现 f，它可以实现为 O(n)，因为可能需要检查每个字符以正确管理 cr/lf 对。
- 这将基于
f.seek(n,0) 是否给出与读取字符循环相同的结果，并且（取决于 OS）cr/lf 被缩小为 lf 或 lf 扩展为cr/lf
如果python在压缩流上实现 f，那么顺序将为 b O(n)，因为解压缩可能需要一些块工作，然后解压缩。
您需要更具体地说明 f 是什么类型的对象。
如果 f 是存储在磁盘上的文件的普通 io module 对象，您必须确定您是否正在处理：
- 原始二进制文件对象
- 一个缓冲区对象，包装原始二进制文件
- 一个 TextIO 对象，包装缓冲区
- 内存中的
BytesIO 或 TextIO 对象
第一个选项只使用 lseek system call to reposition the file descriptor position. If this call is O(1) depends on the OS and what kind of file system you have. For a Linux system with ext4 filesystem, lseek is O(1)。
缓冲区只是清除缓冲区 if your seek target is outside of the current buffered region 并读入新的缓冲区数据。那也是 O(1)，但固定成本更高。
对于文本文件，情况更为复杂，因为可变字节长度的编解码器和行尾转换意味着您不能总是将二进制流位置映射到文本位置而不从头开始扫描。该实现不允许非零当前位置或结束相对寻道，并且最好尽量减少绝对寻道所读取的数据量。 Internal state shared with the text decoder tracks a recent 'safe point' to seek back to 并向前阅读到所需的位置。最坏的情况是 O(n)。
内存中的文件对象实际上只是很长的可寻址数组。寻找是 O(1) 因为你可以改变当前位置指针值。
有许多其他类似文件的对象可能支持也可能不支持搜索。他们如何处理搜索取决于实现。
zipfile module supports seeking on zip files opened in read-only mode, and seeking to a point that lies before the data section covered by the current buffer requires a full re-read and decompression of the data up to the desired point, seeking after requires reading from the current position until you reach the new. The gzip, lzma and bz2 modules all use the same shared implementation, that also starts reading from the start if you seek to a point before the current read position（并且没有更大的缓冲区可以避免这种情况）。
chunk module 允许在块边界内查找并委托给底层对象。如果底层文件查找操作是 O(1)，那么这是一个 O(1) 操作。
等所以，这取决于。
f.seek(500000,0) 是否在到达第 500000 个之前检查了文件的所有前 499999 个字符？
换句话说，f.seek(n,0) 的阶数是 O(n) 还是 O(1)？
这取决于f的实现。但是，在普通文件系统文件中，它是 O(1)。
如果 python 在文本文件上实现 f，它可以实现为 O(n)，因为可能需要检查每个字符以正确管理 cr/lf 对。
- 这将基于
f.seek(n,0)是否给出与读取字符循环相同的结果，并且（取决于 OS）cr/lf 被缩小为 lf 或 lf 扩展为cr/lf
如果python在压缩流上实现 f，那么顺序将为 b O(n)，因为解压缩可能需要一些块工作，然后解压缩。
您需要更具体地说明 f 是什么类型的对象。
如果 f 是存储在磁盘上的文件的普通 io module 对象，您必须确定您是否正在处理：
- 原始二进制文件对象
- 一个缓冲区对象，包装原始二进制文件
- 一个 TextIO 对象，包装缓冲区
- 内存中的
BytesIO或TextIO对象
第一个选项只使用 lseek system call to reposition the file descriptor position. If this call is O(1) depends on the OS and what kind of file system you have. For a Linux system with ext4 filesystem, lseek is O(1)。
缓冲区只是清除缓冲区 if your seek target is outside of the current buffered region 并读入新的缓冲区数据。那也是 O(1)，但固定成本更高。
对于文本文件，情况更为复杂，因为可变字节长度的编解码器和行尾转换意味着您不能总是将二进制流位置映射到文本位置而不从头开始扫描。该实现不允许非零当前位置或结束相对寻道，并且最好尽量减少绝对寻道所读取的数据量。 Internal state shared with the text decoder tracks a recent 'safe point' to seek back to 并向前阅读到所需的位置。最坏的情况是 O(n)。
内存中的文件对象实际上只是很长的可寻址数组。寻找是 O(1) 因为你可以改变当前位置指针值。
有许多其他类似文件的对象可能支持也可能不支持搜索。他们如何处理搜索取决于实现。
zipfilemodule supports seeking on zip files opened in read-only mode, and seeking to a point that lies before the data section covered by the current buffer requires a full re-read and decompression of the data up to the desired point, seeking after requires reading from the current position until you reach the new. Thegzip,lzmaandbz2modules all use the same shared implementation, that also starts reading from the start if you seek to a point before the current read position（并且没有更大的缓冲区可以避免这种情况）。chunkmodule 允许在块边界内查找并委托给底层对象。如果底层文件查找操作是 O(1)，那么这是一个 O(1) 操作。
等所以，这取决于。