time consuming loops over lists

[Andrea Griffini]

On Tue, 07 Jun 2005 23:38:29 +0200, "Diez B. Roggisch" <deets at web.de>
wrote:

>> I don't see a "break" so why the "/2" ? also IIUC the
>
>That was the assumption of an equal distribution of the data. In 
>O-notationn this would be O(n) of course.

It was a joke ... the issue is that there was no break
statement :-) i.e. your code kept searching even after
finding the proper range!

Actually that break (with 10 bins) is not terribly
important because the cost of the comparision is
small compared to the cost of append. The timings
I got are..

your code                 1.26 sec
adding break              0.98 sec
direct index computation  0.56 sec

10 bins are so few that with just low-level speedups
(i.e. precomputing a list of ranges and str(j)) the
code that does a linear scan requires just 0.60 seconds.

Hand optimizing the direct computation code the
execution time gets down to 0.3 seconds; the inner loop
i used is:

     for i, x in enumerate(data):
          j = int((x - dmin)/rng)
          tkns[i] = tks + js[j]

with data = range(20, 123120)


Andrea