StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is actually a very interesting question.</p> <p>I used the following script which runs on Python 2.6, 2.7, 3.0, 3.1, and 3.2.</p> <pre><code>from __future__ import print_function from timeit import Timer from math import factorial try: range = xrange except: pass def perms(s): s = tuple(s) N = len(s) if N <= 1: yield s[:] raise StopIteration() for x in perms(s[1:]): for i in range(0,N): yield x[:i] + (s[0],) + x[i:] def testcase(s): for x in perms(s): pass def test(): for i in range(1,11): s = "".join(["%d" % x for x in range(i)]) s = "testcase(\"%s\")" % s t = Timer(s,"from __main__ import testcase") factor = 100000 factor = int(factor/factorial(i)) factor = (factor>0) and factor or 1 yield (i,(1000*min(t.repeat(5,factor))/factor)) if __name__=="__main__": print("args\ttime[ms]") for x in test(): print("%i\t%f" % x) </code></pre> <p>The platform is Ubuntu 10.10, 64 bit, and all versions of Python were compiled from source. I get the following results:</p> <pre><code>case@quad:~$ py27 perms.py args time[ms] 1 0.002221 2 0.005072 3 0.010352 4 0.027648 5 0.111339 6 0.618658 7 4.207046 8 33.213019 9 294.044971 10 2976.780891 case@quad:~$ py32 perms.py args time[ms] 1 0.001725 2 0.004997 3 0.011208 4 0.032815 5 0.139474 6 0.761153 7 5.068729 8 39.760470 9 356.358051 10 3566.874027 </code></pre> <p>After some more experimentation, I tracked the difference in performance to the fragment: <code>x[:i] + (s[0],) + x[i:]</code> If I just calculate one tuple at the beginning of the loop and return it for every yield statement, both versions of Python run at the same speed. (And the permutations are wrong, but that's not the point.)</p> <p>If I time that fragment by itself, it is significantly slower.</p> <pre><code>case@quad:~$ py27 -m timeit -s "s=(1,2,3,4,5);x=(1,2,3,4,5,6,7,8)" "x[:3] + (s[0],) + x[3:]" 1000000 loops, best of 3: 0.549 usec per loop case@quad:~$ py32 -m timeit -s "s=(1,2,3,4,5);x=(1,2,3,4,5,6,7,8)" "x[:3] + (s[0],) + x[3:]" 1000000 loops, best of 3: 0.687 usec per loop </code></pre> <p>I next used dis.dis() to look at the bytecode generated by both versions.</p> <pre><code>case@quad:~/src/Python-3.0.1$ py32 Python 3.2b2 (r32b2:87398, Dec 21 2010, 21:39:59) [GCC 4.4.5] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> import dis >>> s=(1,2,3,4,5) >>> x=(1,2,3,4,5,6,7,8) >>> def f(s,x): ... return x[:3] + (s[0],) + x[3:] ... >>> dis.dis(f) 2 0 LOAD_FAST 1 (x) 3 LOAD_CONST 0 (None) 6 LOAD_CONST 1 (3) 9 BUILD_SLICE 2 12 BINARY_SUBSCR 13 LOAD_FAST 0 (s) 16 LOAD_CONST 2 (0) 19 BINARY_SUBSCR 20 BUILD_TUPLE 1 23 BINARY_ADD 24 LOAD_FAST 1 (x) 27 LOAD_CONST 1 (3) 30 LOAD_CONST 0 (None) 33 BUILD_SLICE 2 36 BINARY_SUBSCR 37 BINARY_ADD 38 RETURN_VALUE >>> exit() case@quad:~/src/Python-3.0.1$ py26 Python 2.6.6 (r266:84292, Oct 24 2010, 15:27:46) [GCC 4.4.5] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> import dis >>> s=(1,2,3,4,5) >>> x=(1,2,3,4,5,6,7,8) >>> def f(s,x): ... return x[:3] + (s[0],) + x[3:] ... >>> dis.dis(f) 2 0 LOAD_FAST 1 (x) 3 LOAD_CONST 1 (3) 6 SLICE+2 7 LOAD_FAST 0 (s) 10 LOAD_CONST 2 (0) 13 BINARY_SUBSCR 14 BUILD_TUPLE 1 17 BINARY_ADD 18 LOAD_FAST 1 (x) 21 LOAD_CONST 1 (3) 24 SLICE+1 25 BINARY_ADD 26 RETURN_VALUE >>> </code></pre> <p>The generated bytecode is very different between the two versions. Unfortunately, I don't know why the bytecode is different so I really haven't answered the question. But there really is a significant difference in performance for slicing and building tuples.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload