[Tutor] A faster x in S
Dinesh B Vadhia
dineshbvadhia at hotmail.com
Wed Jan 16 18:01:24 CET 2008
I used the s.intersection(t) function in the set type as it was the most appropriate. The performance was phenomenal. Thank-you!
Dinesh
----- Original Message -----
From: bob gailer
To: Dinesh B Vadhia
Cc: tutor at python.org
Sent: Tuesday, January 15, 2008 2:03 PM
Subject: Re: [Tutor] A faster x in S
Dinesh B Vadhia wrote:
> For some significant data pre-processing we have to perform the
> following simple process:
>
> Is the integer x in a list of 13K sorted integers. That's it except
> this has to be done >100m times with different x's (multiple times).
> Yep, a real pain!
>
> I've put the 13K integers in a list S and am using the is 'x in S'
> function.
>
> I was wondering if there is anything faster?
I agree with Kent.
>>> l = range(13000)
>>> s=set(l)
>>> d=dict(enumerate(l))
>>> import time
>>> def f(lookupVal, times, values):
.. st=time.time()
.. for i in range(times):
.. z = lookupVal in values
.. return time.time()-st
>>> f(6499,1000,l)
0.31299996376037598
>>> f(6499,1000000,s)
0.31200003623962402
So set is 1000 times faster than list!
>>> f(6499,1000000,d)
0.31300020217895508
And dict is (as expected) about the same as set.
So 100,000,000 lookups should take about 30 seconds. Not bad, eh?
Let's explore another angle. What range are the integers in (min and max)?
Bob
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20080116/090d0053/attachment-0001.htm
More information about the Tutor
mailing list