15

Does f.seek(500000,0) go through all the first 499999 characters of the file before getting to the 500000th? In other words, is f.seek(n,0) of order O(n) or O(1)?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Irrelevant
  • 158
  • 1
  • 6

2 Answers2

27

You need to be a bit more specific on what type of object f is.

If f is a normal io module object for a file stored on disk, you have to determine if you are dealing with:

  • The raw binary file object
  • A buffer object, wrapping the raw binary file
  • A TextIO object, wrapping the buffer
  • An in-memory BytesIO or TextIO object

The first option just uses the 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).

Buffers just clear the buffer if your seek target is outside of the current buffered region and read in new buffer data. That's O(1) too, but the fixed cost is higher.

For text files, things are more complicated as variable-byte-length codecs and line-ending translation mean you can't always map the binary stream position to a text position without scanning from the start. The implementation doesn't allow for non-zero current-position- or end-relative seeks, and does it's best to minimise how much data is read for absolute seeks. Internal state shared with the text decoder tracks a recent 'safe point' to seek back to and read forward to the desired position. Worst-case this is O(n).

The in-memory file objects are just long, addressable arrays really. Seeking is O(1) because you can just alter the current position pointer value.

There are legion other file-like objects that may or may not support seeking. How they handle seeking is implementation dependent.

Etc. So, it depends.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • Do you know if this applies to gzip.py also? – jsmedmar Oct 19 '20 at 17:17
  • 1
    @jsmedmar I already include the `gzip` module in my answer, it shares a common base implementation with the other compression formats and these have to do a full re-read of the compressed stream if you are seeking to a point before the current. – Martijn Pieters Oct 19 '20 at 23:57
  • Is there a way to get `tell` and `seek` on the `gzip` file itself, and not on the underlying decompressed data? – John Strood May 22 '21 at 09:01
  • @JohnStrood: the wrapped file object is available as [`gzipfileobj.fileobj`](https://github.com/python/cpython/blob/099e6a4096382697dda55d58d3a96f68375ea546/Lib/gzip.py#L209). Seeking on that object *will* beak the internal state of the read buffer, however. – Martijn Pieters May 23 '21 at 12:51
  • @JohnStrood you can use `io.FileIO` to read the uncompressed data. – Kenpachi May 21 '22 at 00:34
  • @Kenpachi that’s just the interface for file objects, the `.fileobj` attribute is such an object. – Martijn Pieters May 22 '22 at 20:39
1

It would depend on the implementation of f. However, in normal file-system files, it is O(1).

If python implements f on text files, it could be implemented as O(n), as each character may need to be inspected to manage cr/lf pairs correctly.

  • This would be based on whether f.seek(n,0) gave the same result as a loop of reading chars, and (depending on OS) cr/lf were shrunk to lf or lf expanded to cr/lf

If python implements f on a compressed stream, then the order would b O(n), as decompression may require some working of blocks, and decompression.

mksteve
  • 12,614
  • 3
  • 28
  • 50
  • `However, in normal file-system files, it is O(1).` This seems very wrong. – ninesalt Aug 11 '18 at 15:41
  • Time should not depend on `n` in terms of big-O, however, I'd expect if `n` is close enough to the current offset, seek would not cause any disk access. – bereal Aug 11 '18 at 15:46
  • @mksteve: I was wrong, `zipfile.ZipFile` does support seeking when reading, and it'll try to satisfy that from the current buffer. If it can't it'll seek back to compression section start and re-read data until it reaches the desired position. – Martijn Pieters Aug 11 '18 at 16:05
  • `seek` itself is almost certainly O(1), because any further work can (and should) be delayed until a read or write actually *needs* the new file position. No sense doing an O(N) operation if the next operation on the file is a close. – chepner Aug 11 '18 at 17:03