-----Original Message-----
From: Tim Chase [mailto
[email protected]]
Sent: Thursday, January 17, 2008 10:30 AM
To: Reedick, Andrew
Cc: breal; (e-mail address removed); (e-mail address removed)
Subject: Re: Creating unique combinations from lists
Yick...a nice demo of the power of eval, but definitely filed
under the "Hack" heading
You hurt my feeling. *sniffle* Given how late python
compiles/evaluates code blocks, I'm thinking that eval() is less hack
and more paradigm ..err.. pythonic. ;-)
I think Martin's solution/recommendation[1] is better
(readability-wise, and "less apt to shoot yourself in the foot
with some bogus generated code"-wise) if you don't mind building
the whole result set in memory which your eval() solution does as
well. I'm curious to see the timing results from adding that
recipe to your test-suite.
Cookbook is relatively decent. 5 deep, 100 iterations:
list comprehension: 11.02
nested for loop : 13.16 +19%
cookbook : 18.85 +71%
recursion : 69.00 +526%
eval : 13.30 +20%
The advantage to the recursive-generator solution is that it
should really only keep your initial input and the current result
in memory as the generated item, so you can reasonably iterate
over millions of rows without having gigs of RAM. I don't
believe the recursion will go deeper than the number of lists
you're iterating over, so the stack shouldn't explode.
Excellent point about memory usage. However, since we're dealing with
exponential algorithms, will you run out of time or memory first?
Here's the test code if anyone wants to play with it. It will let you
specify the levels of nested loops and display the generated code.
Usage: foo.py num_nested_loops num_iterations
import sys
from timeit import Timer
def CreateComprehension(lists):
out = '[' + ','.join(["v%s" % i for i in range(len(lists))]) +
']'
comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
return '[ ' + out + comp + ' ]'
num_loops = int(sys.argv[1])
iterations = int(sys.argv[2])
results = []
lists = '''lists = []
for i in range(%d):
lists.append(range(i, i+10))
''' % (num_loops)
print "################################################"
print lists
print
print "################################################"
code = 'r = ' + CreateComprehension(range(num_loops))
t = Timer(code, lists)
results.append("list comprehension: %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print
print "################################################"
code = 'r = []\n'
for i in range(num_loops):
code += " " * i
code += "for v%d in lists[%d]:\n" % (i, i)
code += ' ' * num_loops
code += 'r.append(['
code += ','.join( ['v%d' % i for i in range(num_loops)])
code += '])'
t = Timer(code, lists)
results.append("nested for loop : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print
print "################################################"
code = '''r=[[]]
for x in lists:
t = []
for y in x:
for i in r:
t.append(i+[y])
r = t
'''
t = Timer(code, lists)
results.append("cookbook : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print
print "################################################"
code = '''
r = []
def iterall(*iterables):
if iterables:
for head in iterables[0]:
for remainder in iterall(*iterables[1:]):
yield [head] + remainder
else:
yield []
for thing in iterall(%s):
r.append(thing)
''' % ( ','.join([ 'lists[%d]' % i for i in range(num_loops) ]) )
t = Timer(code, lists)
results.append("recursion : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print
print "################################################"
code = '''
def gen(lists):
out = '[' + ','.join(["v%s" % i for i in range(len(lists))]) + ']'
comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
return eval('[ ' + out + comp + ' ]')
gen(lists)
'''
t = Timer(code, lists)
results.append("eval : %4.2f" % t.timeit(iterations))
print results[-1:][0]
print code
print
print '\n'.join(results)
*****
The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA622