what the heck is going on here?

M

markscala

I found the following ways to generate permutations on the ASPN:
Python Cookbook page.

SLOW (two defs):

def xcombinations(items,n):
if n == 0: yield[]
else:
for i in xrange(len(items)):
for cc in xcombinations(items[:i]+items[i+1:],n-1):
yield [items]+cc

def xpermutations(items):
return xcombinations(items,len(items))

FAST:

def permutations(L):
if len(L) <= 1:
yield L
else:
a = [L.pop(0)]
for p in permutations(L):
for i in range(len(p)+1):
yield p[:i] + a + p[i:]

The author of the FAST claimed his method was faster, which I wanted
to test. I ran the test as follows:

import time
name = list('python')

faster = time.clock()
for x in range(10000):
map(''.join,list(permutations(name)))
total1 = time.clock() - faster
print "Total time for faster: ", total1

xperm_start = time.clock()
for x in range(10000):
map(''.join,list(xpermutations(name)))
total2 = time.clock() - xperm_start
print "Total time for xperm: ", total2

If you run these tests in the order above, FAST takes about a .1
seconds and slow takes about .17 seconds. BUT if you reverse the
order of the test, SLOW takes almost 10 seconds and FAST is about the
same! What's more, if you take map, join and list out of the tests
(there's no reason for them to be there anyway) the order doesn't
matter any more. Without map/join/list, SLOW and FAST are almost
indistinguishable at 10K loops. What's going on? ( This was done
in Python2.4 )
 
P

Peter Otten

I found the following ways to generate permutations on the ASPN:
Python Cookbook page.

SLOW (two defs):

def xcombinations(items,n):
if n == 0: yield[]
else:
for i in xrange(len(items)):
for cc in xcombinations(items[:i]+items[i+1:],n-1):
yield [items]+cc

def xpermutations(items):
return xcombinations(items,len(items))

FAST:

def permutations(L):
if len(L) <= 1:
yield L
else:
a = [L.pop(0)]
for p in permutations(L):
for i in range(len(p)+1):
yield p[:i] + a + p[i:]

The author of the FAST claimed his method was faster, which I wanted
to test. I ran the test as follows:

import time
name = list('python')

faster = time.clock()
for x in range(10000):
map(''.join,list(permutations(name)))
total1 = time.clock() - faster
print "Total time for faster: ", total1

xperm_start = time.clock()
for x in range(10000):
map(''.join,list(xpermutations(name)))
total2 = time.clock() - xperm_start
print "Total time for xperm: ", total2

If you run these tests in the order above, FAST takes about a .1
seconds and slow takes about .17 seconds. BUT if you reverse the
order of the test, SLOW takes almost 10 seconds and FAST is about the
same! What's more, if you take map, join and list out of the tests
(there's no reason for them to be there anyway) the order doesn't
matter any more. Without map/join/list, SLOW and FAST are almost
indistinguishable at 10K loops. What's going on? ( This was done
in Python2.4 )


permutations() modifies its argument. Try

items = ["a", "b", "c"]
for p in permutations(items):
pass
print items

to see why all measurements after the first pass of permutations() are
bogus. Then modify your code to have permutations() operate on copies of
the 'name' list.

Peter
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top