fast list search?

Dan Gunter dkgunter at lbl.gov
Sat Jun 12 05:06:17 CEST 2004


How about using a dictionary, with the keys being the ints and the 
values being the index in the 'list', i.e. len(dictionary). This is 
quite fast:

 >>> d = {}
 >>> for i in xrange(0,500000):
...     if not d.has_key(i): d[i] = len(d)

-Dan

Javier Zaragozá Arenas wrote:
> I think the better way is sort before the list
> 
> 
>>>thelist.sort()
> 
> 
> And then, a binary search
> 
> 
>>>point_of_insertion = bisect.bisect(thelist, item)
>>>is_present = thelist[point_of_insertion -1:point_of_insertion] == [item]
> 
>  >> if not is_present:
> ....            thelist.insert(point_of_insertion, item)
> 
> and done!
> 
> Fco Javier Zaragozá Arenas
> 
> 
> 
> "ramon aragues" <ramon.aragues at gmx.net> escribió en el mensaje
> news:mailman.747.1086774432.6949.python-list at python.org...
> 
>>Hi,
>>
>>I´ve got a list with more than 500,000 ints. Before inserting new ints,
>>I have to check that it doesn´t exist already in the list.
>>
>>Currently, I am doing the standard:
>>
>>if new_int not in long_list:
>>long_list.append(new_int)
>>
>>
>>but it is extremely slow... is there a faster way of doing this in python?
>>
>>Thanks a lot,
>>
>>Ramon Aragues
>>
>>
> 
> 
> 





More information about the Python-list mailing list