Re: time consuming loops over lists
Diez B. Roggisch
> 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
que...@gmail.com
difference. Thanks you very much. that really improves the performance
Peter Otten
> 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...
>
> def Tkz(tk,data):
> no_of_bins = 10
> tkns = []
> dmax = max(data)+1
> dmin = min(data)
> rng = ceil(abs((dmax - dmin)/(no_of_bins*1.0)))
> rngs = zeros(no_of_bins+1)
> for i in xrange(no_of_bins+1):
> rngs[i] = dmin + (rng*i)
> for i in xrange(len(data)):
> for j in xrange(len(rngs)-1):
> if data[i] in xrange(rngs[j],rngs[j+1]):
> tkns.append( str(tk)+str(j) )
> return tkns
Use bisect(), e. g., with a slightly modified function signature:
from __future__ import division
import bisect
from math import ceil
def tkz(tk, data, no_of_bins=10):
dmax = max(data) + 1
dmin = min(data)
rng = ceil((dmax - dmin)/no_of_bins)
rngs = [dmin + rng*i for i in xrange(1, no_of_bins+1)]
tokens = [tk + str(i) for i in xrange(no_of_bins)]
return [tokens[bisect.bisect(rngs, v)] for v in data]
if __name__ == "__main__":
print tkz("token_", [5, 7, 8, 9, 70, 200])
What are the tokens for, by the way? I'd recommend using the indices
directly if possible.
Peter
Andrea Griffini
wrote:
>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.
I don't see a "break" so why the "/2" ? also IIUC the
ranges are more than just ordered... they're all equal
and computed by
for i in xrange(no_of_bins+1):
rngs[i] = dmin + (rng*i)
so my guess is that instead of searching with
for j in xrange(len(rngs)-1):
if rngs[j] <= data[i] < rngs[j+1]:
one could just do
j = int((data[i] - dmin)/rng)
The code with this change gets roughly about twice faster.
Andrea
Diez B. Roggisch
That was the assumption of an equal distribution of the data. In
O-notationn this would be O(n) of course.
Diez
John Machin
Make these changes/additions:
=================================================
# from Numeric import *
# +1 for Overkill-of-the-Year
def zeros(n):
return n * [0.0]
def Tkz3(tk, data, no_of_bins):
# indent 5 ???????
# change other funcs to have no_of_bins as an arg
tkns = []
dmax = max(data)+1
dmin = min(data)
rng = int(ceil(abs((dmax - dmin)/(no_of_bins*1.0))))
for datum in data:
j = (datum - dmin) // rng
tkns.append( str(tk)+str(j) )
return tkns
for func in (Tkz, Tkz2, Tkz3):
t0 = time.time()
result = func('A', data, nbins)
t1 = time.time()
results.append(result)
print "function %s took %.2f seconds to produce %d tokens" %
(func.__name__, t1 - t0, len(result))
allsame = results [0] == results[1] == results[2]
print "\nIdentical results:", allsame
=======================================================
and get this:
C:\junk>ranges.py
C:\junk\ranges.py:46: DeprecationWarning: integer argument expected, got
float
if data[i] in xrange(rngs[j], rngs[j+1]):
function Tkz took 12.13 seconds to produce 12292 tokens
function Tkz2 took 0.08 seconds to produce 12292 tokens
function Tkz3 took 0.02 seconds to produce 12292 tokens
Identical results: True
==================================================
using Python 2.4.1 (win32) on a 3.2Ghz Intel P4
==================================================
Notes: (1) The OP's code as well as being deliciously O(N**2) depends on
the data beint *integers* -- otherwise it goes rapidly pear-shaped; see
the deprecation warning above, and try running it with data = [0.00001*
x for x in range(20, 12312)]. Consequently the use of math.* is a /mild/
overkill.
(2) The OP's code produces bins of equal nominal width but depending in
the range, the population of the last bin may be much less than the
population of the other bins. Another way of doing it would be to
produce bin widths so that the populations were more evenly spread. In
any case determining the appropriate bin could still be done by formula
rather than by searching.
Cheers,
John
Andrea Griffini
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
Peter Otten
> 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...
>
> def Tkz(tk,data):
> no_of_bins = 10
> tkns = []
> dmax = max(data)+1
> dmin = min(data)
> rng = ceil(abs((dmax - dmin)/(no_of_bins*1.0)))
> rngs = zeros(no_of_bins+1)
> for i in xrange(no_of_bins+1):
> rngs[i] = dmin + (rng*i)
> for i in xrange(len(data)):
> for j in xrange(len(rngs)-1):
> if data[i] in xrange(rngs[j],rngs[j+1]):
> tkns.append( str(tk)+str(j) )
> return tkns
On second thought, with bins of equal size you have an option that is even
faster than bisect:
def bins_calc(tk, data, no_of_bins=10):
dmax = max(data) + 1
dmin = min(data)
delta = dmax - dmin
rng = int(ceil((dmax - dmin)/no_of_bins))
tokens = [tk + str(i) for i in xrange(no_of_bins)]
return [tokens[(v-dmin)//rng] for v in data]
Peter