Creating unique combinations from lists

[Reedick, Andrew]

> -----Original Message-----
> From: Tim Chase [mailto:python.list at tim.thechases.com]
> Sent: Thursday, January 17, 2008 10:30 AM
> To: Reedick, Andrew
> Cc: breal; python-list at python.org; martin at v.loewis.de
> 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