Home Original page

fast list search?

Phil Frost indigo at bitglue.com
Sat Jun 12 01:09:14 EDT 2004 
Perhaps the standard 'sets' module would be of use? It's implemented
with dictionaries, and seems to do the thing that is needed.

On Fri, Jun 11, 2004 at 08:06:17PM -0700, Dan Gunter wrote:
> 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