Title: random.shuffle could be faster
Type: performance Stage:
Components: Library (Lib) Versions: Python 3.4
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Thorney, rhettinger, westurner
Priority: low Keywords: patch

Created on 2013-07-20 00:34 by westurner, last changed 2013-07-20 09:11 by rhettinger. This issue is now closed.

File name Uploaded Description Edit westurner, 2013-07-20 00:34
random-shuffle_v2.7.5.patch westurner, 2013-07-20 00:35 Patch to random.shuffle for v2.7.5
random-shuffle_trunk.patch westurner, 2013-07-20 00:35 Patch to random.shuffle for trunk review
Messages (5)
msg193388 - (view) Author: Wes Turner (westurner) * Date: 2013-07-20 00:34
random.shuffle [1][2] could be faster. 

``xrange(10,1,-1)`` is faster than ``reversed(xrange(1,10))``.

[1] Lib/">
msg193389 - (view) Author: Wes Turner (westurner) * Date: 2013-07-20 00:35
Added patch to random.shuffle for v2.7.5
msg193390 - (view) Author: Wes Turner (westurner) * Date: 2013-07-20 00:35
Added patch to random.shuffle for trunk
msg193400 - (view) Author: Brian Thorne (Thorney) Date: 2013-07-20 05:40
Just did some testing on 2.7 and 3.3 on Windows and Ubuntu, the speedup is  just noticeable - but much less so as the list grows.
msg193403 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-07-20 09:11
Both versions loop over the exact same iterator, so both loops run at the same speed once they are started up.   

Your timeit code isn't measuring shuffle().  Instead, it measures list() which knows how to extract a useful length hint from xrange() but not from an xrange iterator.  The timing difference disappears if you add iter():

   current = '''list(reversed(xrange(1, n)))'''
   proposd = '''list(iter(xrange(n, 1, -1)))'''

If you were to time shuffle() directly, you would see almost no difference between the current version and the patched version (there is a small difference in startup time due to the lookup of the reversed() built-in, but that is it).
Date User Action Args
2013-07-20 09:11:30rhettingersetstatus: open -> closed
resolution: not a bug
messages: + msg193403
2013-07-20 05:40:52Thorneysetnosy: + Thorney
messages: + msg193400
2013-07-20 05:32:35rhettingersetmessages: - msg193399
2013-07-20 05:31:16rhettingersetpriority: normal -> low
versions: - Python 2.6, 3rd party, Python 3.1, Python 2.7, Python 3.2, Python 3.3, Python 3.5
2013-07-20 05:25:36rhettingersetmessages: + msg193399
2013-07-20 05:22:49rhettingersetassignee: rhettinger

nosy: + rhettinger
2013-07-20 00:35:49westurnersetfiles: + random-shuffle_trunk.patch

messages: + msg193390
2013-07-20 00:35:14westurnersetfiles: + random-shuffle_v2.7.5.patch
keywords: + patch
messages: + msg193389
2013-07-20 00:34:04westurnercreate