常规O(N)读取N行文件，是否存在O(logN)时间复杂度的读取算法？

Great question! Let's break this down clearly to understand what's possible and why.

First, the hard truth for standard plain text files: You can't do this out of the box. Here's the reason:

• Text files store lines as variable-length chunks—each line can have a different number of characters, plus line endings like \n or \r\n that vary by OS. There's no built-in "map" telling you where each line starts, so to get to the k-th line, you have to scan from the beginning, counting newlines as you go. That's inherently O(N) time in the worst case.

But there are practical workarounds that let you achieve O(logN) access if you're willing to do a little preprocessing or use a different file format:

1. Precompute a line offset index #

If you need to access the file multiple times, spend a one-time O(N) cost to build an index:

• Run through the file once, recording the byte offset of each line's start (e.g., an array where offsets[i] holds the byte position of the i-th line).
• Once the index exists, use binary search on the offset array to find the exact byte position of any line in O(logN) time. Then use your programming language's seek() function (most file systems support this in O(1) time) to jump straight to that spot and read the line.
• Here's a quick pseudocode example to illustrate:

  # One-time preprocessing step
  line_offsets = []
  with open("my_file.txt", "r") as f:
      line_offsets.append(0)  # Offset for first line
      for _ in f:
          line_offsets.append(f.tell())  # Record end of current line (start of next)
  
  # O(logN) access to the 500th line (0-indexed)
  target_line = 500
  with open("my_file.txt", "r") as f:
      f.seek(line_offsets[target_line])
      desired_line = f.readline()
  

2. Use fixed-length record files #

If you control how the file is created, design it with fixed-length lines:

• Make every line exactly the same length (pad shorter lines with spaces or null characters if needed).
• The byte offset of the k-th line becomes k * line_length, so you can jump directly to it in O(1) time (even better than O(logN)). This is a common trick in systems where fast random access is critical, like legacy databases or log storage.

3. Use specialized file formats #

Some formats are built from the ground up for fast random access:

• Columnar formats like Parquet or ORC store data with built-in indexes, letting you jump to specific rows (which map to lines in your use case) quickly.
• Embedded databases like SQLite use B-tree indexes under the hood, which give you O(logN) lookups for individual rows if you structure your data as a table.

Key takeaway #

You can't get O(logN) access to a plain text file without preprocessing, but with a one-time O(N) index build or by using a structured file format, you can achieve fast random line access that's effectively O(logN) for all subsequent reads.

内容的提问来源于stack exchange，提问作者Dinesh