[Tutor] A faster x in S
Kent Johnson
kent37 at tds.net
Tue Jan 15 18:38:40 CET 2008
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?
Yes. Put the integers in a set and test for membership there. If for
some reason the integers have to be in a list, and the list is sorted,
use the bisect module to do a binary search, rather than the linear
search used by 'x in S'.
http://docs.python.org/lib/module-bisect.html
Kent
More information about the Tutor
mailing list