[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'.


More information about the Tutor mailing list