Find an Item in a Sorted List

[Mike Dean]

Greetings, and welcome to Python!

Python does have a (very fast) way to do a search such as you are
looking at with its Dictionaries (hash tables in other languages).  For
example:

# The data - these can be lines in a file rather than a list of strings;
# in that case, use the file reading and looping code in a previous
# recommendation
data = ['Arty,1000',
'Bobby,2000',
'Charlie,3000']

d2={}    # Initialize an empty dictionary

for line in data:
    d2[line.split(',')[0]] = line    # Store the line in the dictionary,
                                     # using the first comma-delimited
                                     # item as the key

# Later on...
print d2['Bobby']

Dictionary searches are implemented in C in the Python core, and execute
very quickly (IIRC, they use b-tree indexes so that the search time is
relatively flat, even with very large dictionaries).

HTH,
Michael


P.S.  I remembered to test my code this time :-)

* HankC <hankc at nospam.com> [2002-26-02 23:50]:
> Greetings:
> 
> I'm 2 days new to Python and hope I can get some pointers here...
> 
> I have a sorted, delimited text file such as:
> 
> Arty,1000
> Bobby,2000
> Charlie,3000
> 
> Knowing a name, I want to return the entire line from the file.  My
> approach/problems (any comments appreciated):
> 
> # use the filter method
> # filter fxn
> def Match(line): return line[:toklen] == tok
> 
> # find match fxn
> def FindMatch:
>       fp = open(fname)
>       flist = fp.readlines()
>       dataline = filter(Match, eodflist)
> 
> My problem is that I don't understand how, if it's even possible, to
> set tok and toklen values in the FindMatch fxn and pass them to Match.
> Is it possible to pass multiple values to the function used by
> filter()?
> 
> More general...  does filter() have any performance advantage over
> just using a for loop?  The datafile list has 10,000+ items.  My
> background is in object pascal where I would read the items into a
> list then use a binary search to find the target.  I'm hoping there's
> an efficient python method to perform a search easily on a sorted
> list.
> 
> Suppose I want to make tok and toklen global to the module.  Is this
> possible?
> 
> TIA!
> -- 
> http://mail.python.org/mailman/listinfo/python-list