fast list search?

[ramon aragues]

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

[Thomas Guettler]

Am Wed, 09 Jun 2004 11:49:19 +0200 schrieb ramon aragues:

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?

Hi,

Use a dictionary instead of the list:

if not long_dict.has_key(new_int):
long_dict[new_int]=1

Thomas

[Peter Otten]

ramon aragues wrote:

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?

import sets
int_set = sets.Set()
for i in [1,2,2,3,4,4,4]: .... int_set.add(i)
.... int_set Set([1, 2, 3, 4])

This requires Python 2.3.

Peter

[Terry Reedy]

"Thomas Guettler" <gu*****@thomas-guettler.de> wrote in message
news:pa***************************@thomas-guettler.de...

Am Wed, 09 Jun 2004 11:49:19 +0200 schrieb ramon aragues:

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?
Hi,

Use a dictionary instead of the list:

if not long_dict.has_key(new_int):
long_dict[new_int]=1

Or use a set, which I believe will be faster (more C-coded) in 2.4. That
eliminates the dummy value.

TJR

[Javier Zaragozá Arenas]

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" <ra***********@gmx.net> escribió en el mensaje
news:ma*************************************@pytho n.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

[Dan Gunter]

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" <ra***********@gmx.net> escribió en el mensaje
news:ma*************************************@pytho n.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

[Phil Frost]

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" <ra***********@gmx.net> escribi? en el mensaje
news:ma*************************************@pyth on.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