time consuming loops over lists

[Diez B. Roggisch]

querypk at gmail.com wrote:
> X-No-Archive: yes
> Can some one help me improve this block of code...this jus converts the
> list of data into tokens based on the range it falls into...but it
> takes a long time.Can someone tell me what can i change to improve
> it...
> 


>                if data[i] in xrange(rngs[j],rngs[j+1]):
> 

That's a bummer: You create a list and then search linearily in in - 
where all you want to know is

if rngs[j] <= data[i] < rngs[j+1]

Attached is a script that does contain  your old and my enhanced version 
- and shows that the results are equal. Running only your version takes 
~35s, where mine uses ~1s!!!

Another optimization im too lazy now would be to do sort of a "tree 
search" of data[i] in rngs - as the ranges are ordered, you could find 
the proper one in log_2(len(rngs)) instead of len(rngs)/2.

Additional improvements can be achieved when data is sorted - but that 
depends on your application and actually sizes of data.

Diez
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: test.py
URL: <http://mail.python.org/pipermail/python-list/attachments/20050607/c478bdd8/attachment.ksh>