can Bisect be applied using Dict instead of lists?

Question

i have a file with information in the pattern of:

.343423 1
.434322 1
.453434 1
.534342 1

Equal size each line and row in sorted order..I have a variable "a" with a value and need to get the row number which it closest to "a" comparing with the values in the 1st column..

Till now i was coping the 1st column element into list and then using bisect method i am getting the row_num...but as i need to perform this many times..this has become painfully slow as i need to copy some 4000 element to list everytime..

so now i am thinking of doing it with dict instead of datastructure as i would be faster...but i dont know whether we can use dict in bisect if possible how can we use for this case please suggest... if not possible are they any method for loading data into list faster then normal??? thanking you...

Answer 1

I don't get why you need to copy the elements. This is the slow part. Can't you load the list one time on startup, and then always use the same list ?

A dict will be slower than a list anyway (and I belive [not sure] it is implemented as a hash_map, thus there is no order, thus you can't use bisect).

Answer 2

Dicts are unordered, so using bisect on them is meaningless.

I can think of a couple of options:

1) Keep the data in a sorted list of (key, value) tuples. This will allow you to use bisect to find the closest element. This is fine if this is the only thing you ever want to do with the list, and if the list does not change much over time (since it will need to be resorted each time, which will have a cost).

2) use a balanced binary tree datastructure - there are several Python implementations available on PyPi. This will give you dictionary-like semantics while being able to find the closest element like bisect does. The first item in the PyPi search is bintrees, which looks like it will do everything you want. It acts like a dictionary but has additional methods to get the items before and after a given value. This will let you efficiently find the closest number.

Answer 3

If you are reading the whole file in, a dictionary will be faster than a list because the list must be searched (O(lg n)), while a dictionary provides fast lookups regardless of the size (O(1)). Of course, you would not use bisection (binary search) on a dictionary. If you are only looking for a single row in any particular file, you don't even need to do that -- you can just read the file until you find the row you're looking for.

If you have few lookups per file, you might be able to make it go faster by doing a binary search directly on the file itself. Since you know the file is sorted and each record is the same length, you could easily write the code to just read in the bytes of the file you need for your search.

Answer 4

Here is a way to use bisect without reading the entire file. The OS will end up reading much more of the file than you need regardless, so you won't see a performance gain until data.txt big enough

from os import SEEK_END
from bisect import bisect

class ListProxy(object):
    def __init__(self, f):
        self.f = f
        self.line_len = len(f.readline())
        self.f.seek(0, SEEK_END)
        self.num_lines = self.f.tell()//self.line_len

    def __len__(self):
        return self.num_lines

    def __getitem__(self, idx):
        self.f.seek(idx*self.line_len)
        return float(self.f.read(7))

with open("data.txt") as f:
    lp = ListProxy(f)    
    num = .44
    idx = bisect(lp, num)
    if idx != 0 and num - lp[idx-1] < lp[idx] - num:
        idx -=1
    print num, idx