Python Random Access File

Question

Is there a Python file type for accessing random lines without traversing the whole file? I need to search within a large file, reading the whole thing into memory wouldn't be possible.

Any types or methods would be appreciated.

Keyte

Can you explain why you want to read a random line, instead of reading the whole file in parts or something. – Decedent

To do a binary search within the file, as each line starts with an integer. I want to treat the integers as keys and the rest of the line as the value. – Keyte

Answer 1

This seems like just the sort of thing mmap was designed for. A mmap object creates a string-like interface to a file:

>>> f = open("bonnie.txt", "wb")
>>> f.write("My Bonnie lies over the ocean.")
>>> f.close()
>>> f.open("bonnie.txt", "r+b")
>>> mm = mmap(f.fileno(), 0)
>>> print mm[3:9]
Bonnie

In case you were wondering, mmap objects can also be assigned to:

>>> print mm[24:]
ocean.
>>> mm[24:] = "sea.  "
>>> print mm[:]
My Bonnie lies over the sea.  

Academia

But doesn't mmap also loads the entire file into the memory? ` mm = mmap(f.fileno(), 0)` is (as far as I understand) reads the entire file into the memory. Can you elaborate on that please? – Xenocrates

@Xenocrates my understanding is that it does not. Instead, it makes the hard drive addressable as if it were RAM, via virtual memory mechanisms. I don't know all the details, but it definitely doesn't load the whole file into memory at first, as the Mmap article on wikipedia explains. – Academia

Answer 2

You can use linecache:

import linecache
print linecache.getline(your_file.txt, randomLineNumber) # Note: first line is 1, not 0

Barnsley

This is so cool! And it is a build-in Python module! Thanks! – Mohock

Answer 3

Since lines can be of arbitrary length, you really can't get at a random line (whether you mean "a line whose number is actually random" or "a line with an arbitrary number, selected by me") without traversing the whole file.

If kinda-sorta-random is enough, you can seek to a random place in the file and then read forward until you hit a line terminator. But that's useless if you want to find (say) line number 1234, and will sample lines non-uniformly if you actually want a randomly chosen line.

Oblate

I see you're wanting to do a binary search. In that case: yes, seek to a point approximately halfway between your current lower and upper bounds, read a chunk, and look for lines within that chunk. (It's probably obvious, but: Don't try to seek around randomly at the granularity of individual lines, unless they're very long. Read larger pieces. That way you're less dependent on the details of the OS's and Python's buffering, and you avoid some overhead.) – Oblate

Answer 4

file objects have a seek method which can take a value to particular byte within that file. For traversing through the large files, iterate over it and check for the value in each line. Iterating the file object does not load the whole file content into memory.

Choriamb

Answer 5

Yes, you can easily get a random line. Just seek to a random position in the file, then seek towards the beginning until you hit a \n or the beginning of the file, then read a line.

Code:

import sys,random
with open(sys.argv[1],"r") as f:
    f.seek(0,2)                 # seek to end of file
    bytes = f.tell()
    f.seek(int(bytes*random.random()))

    # Now seek forward until beginning of file or we get a \n
    while True:
        f.seek(-2,1)
        ch = f.read(1)
        if ch=='\n': break
        if f.tell()==1: break

    # Now get a line
    print f.readline()

Cholecyst

A couple of notes. (1) You should probably open it as a binary file if you're going to go seeking around in it. (2) You'll probably get better performance (because of better interaction with the underlying buffering, and fewer calls to f.seek) if you look forwards from the point you landed at instead of backward. The downside of that is that you'll never get the first line that way, and may hit the end of the file, but you can work around that by saying: if you hit the end of the file, go to the beginning and read a line from there. – Oblate

True. Going forward is slightly higher performance, but then you need the wrap-around logic. I do most of my development on Unix where the distinction between "binary" and "text" files is not meaningful. – Cholecyst

Answer 6

The File object supports seek but make sure that you open them as binary, i.e. "rb".

You may also wish to use the mmap module for random access, particularly if the data is in an internal format already.

Cystoid

Answer 7

Has fixed-length records? If so, yes, you can implement a binary search algorithm using seeking.

Otherwise, load your file into an SQLlite database. Query that.

Kirst