classification
Title: Added test to test_random.py testing Random.shuffle
Type: enhancement Stage: resolved
Components: Tests Versions: Python 3.4
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: eng793, ezio.melotti, pitrou, python-dev, r.david.murray, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2012-09-01 02:06 by eng793, last changed 2012-11-04 01:11 by pitrou. This issue is now closed.

Files
File name Uploaded Description Edit
random.patch eng793, 2012-09-01 08:38 review
Messages (17)
msg169603 - (view) Author: Alessandro Moura (eng793) * Date: 2012-09-01 02:06
Random.shuffle does not have a test in test_random.py; the attached patch adds this test. In addition, I rewrote the documentation string for Random.shuffle, which apparently did not reflect recent changes in the code and was inconsistent with the definition of the method. This change is also part of this patch; I was not sure if this merited a separate issue, so I just included this here.

On a related matter: in Random.shuffle there is a third optional argument which looks very odd to me:

def shuffle(self, x, random=None, int=int):
....

Besides being confusing to a user typing help(shuffle), what the "int" argument does in shuffle is to convert a float to an integer. But one could pass any one-argument function in principle, and it would be then very hard to predict what shuffle would do... it would not "shuffle" any more in the traditional sense - not with a uniform probability distribution. In summary, I don't see how that argument could be useful, although the people who wrote the library must have had something in mind... if so it would be a good idea to document it.
msg169605 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2012-09-01 02:16
The patch seems to be missing.

The int=int is probably some sort of micro-optimization and perhaps should be removed.
msg169614 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-01 08:37
> The int=int is probably some sort of micro-optimization and perhaps should be removed.

Agree, this micro-optimization has no effect here.
msg169615 - (view) Author: Alessandro Moura (eng793) * Date: 2012-09-01 08:38
Sorry, here it is the patch.
msg169790 - (view) Author: Alessandro Moura (eng793) * Date: 2012-09-03 18:06
Comparing the execution time with and without the int=int argument of this command:

amoura@amoura-laptop:~/cpython$ time ./python -c "from random import shuffle; lst=list(range(1000000)); shuffle(lst); print (len(lst))"

I get with int=int:

real	0m13.755s
user	0m13.777s
sys	0m0.124s

and without it:

real	0m13.876s
user	0m13.701s
sys	0m0.116s

So it makes no difference in practice. On the other hand, removing this has a chance of braking existing code, if someone somewhere actually uses the third argument for something - I can't image what, but still...
msg169806 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-03 20:59
Third parameter (int) plays a role only in the presence of a second one (random).
msg169809 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2012-09-03 21:59
No, it always has an effect.  It means that the name 'int' is bound in locals instead of being looked up via globals.  That is what makes it a micro-optimization (LOAD_FAST vs LOAD_GLOBAL, if you do a dis on the two variants).
msg169810 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2012-09-03 22:01
Oh, I see what you are saying.  The lookup of int is only done if random is not None.  Yes, that is true.
msg169811 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2012-09-03 22:03
If the optimization is actually useful, it can be preserved by just putting 'int=int' (with an 'optimization' comment :) before the loop.
msg169812 - (view) Author: Alessandro Moura (eng793) * Date: 2012-09-03 22:55
The int=int still makes no difference, but if the second argument is set to random.random, we get a big speedup, regardless of whether the third argument is there:

without int=int:

amoura@amoura-laptop:~/cpython$ time ./python -c "import random; lst=list(range(1000000)); random.shuffle(lst,random.random); print (len(lst))"
1000000

real	0m7.082s
user	0m6.952s
sys	0m0.116s

With int=int:

amoura@amoura-laptop:~/cpython$ time ./python -c "import random; lst=list(range(1000000)); random.shuffle(lst,random.random); print (len(lst))"
1000000

real	0m7.281s
user	0m7.156s
sys	0m0.100s

Without second argument:

amoura@amoura-laptop:~/cpython$ time ./python -c "import random; lst=list(range(1000000)); random.shuffle(lst); print (len(lst))"
1000000

real	0m13.783s
user	0m13.609s
sys	0m0.108s

This could be because of the many tests of whether the 2nd argument is None in the loop.
msg169813 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-03 23:04
> This could be because of the many tests of whether the 2nd argument is None
> in the loop.

This is because Random._randbelow (and therefore randrange, randint) is 
relatively slow.
msg169814 - (view) Author: Alessandro Moura (eng793) * Date: 2012-09-03 23:14
Yup. This is the result of simply eliminating the condition in the loop and just using the second argument (for the purposes of testing this only):


amoura@amoura-laptop:~/cpython$ time ./python -c "import random; lst=list(range(1000000)); random.shuffle(lst,random.random); print (len(lst))"
1000000

real	0m7.330s
user	0m7.148s
sys	0m0.092s
msg169854 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2012-09-05 03:11
The patch look fine as-is and it can be applied in 3.4.  (BTW, I miss having a Resolution status of Accepted, meaning that the patch passed review and is ready to apply).

FWIW, I'll remove the int=int optimization in Py3.4.  It doesn't provide much benefit anymore.
msg172166 - (view) Author: Ezio Melotti (ezio.melotti) * (Python committer) Date: 2012-10-06 04:26
I left a review on rietveld.

FWIW these are the results of the tests using timeit:

# with int=int
$ ./python -m timeit -s 'from random import random, shuffle; lst = list(range(100000))'  'shuffle(lst, random)'
10 loops, best of 3: 507 msec per loop

# without int=int
$ ./python -m timeit -s 'from random import random, shuffle; lst = list(range(100000))'  'shuffle(lst, random)'
10 loops, best of 3: 539 msec per loop
msg172234 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-10-06 18:32
I am not sure that None as default should be documented. It's implementation details (as third "int" argument) and can be silently changed in future versions.
msg174730 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2012-11-04 01:11
New changeset 58776cc74e89 by Antoine Pitrou in branch 'default':
Issue #15837: add some tests for random.shuffle().
http://hg.python.org/cpython/rev/58776cc74e89
msg174731 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-11-04 01:11
I've committed the patch, thank you Alessandro.
History
Date User Action Args
2012-11-04 01:11:50pitrousetstatus: open -> closed

assignee: rhettinger ->

nosy: + pitrou
messages: + msg174731
resolution: fixed
stage: resolved
2012-11-04 01:11:07python-devsetnosy: + python-dev
messages: + msg174730
2012-10-06 18:32:03serhiy.storchakasetmessages: + msg172234
2012-10-06 04:26:21ezio.melottisetnosy: + ezio.melotti
messages: + msg172166
2012-09-05 03:11:30rhettingersetmessages: + msg169854
versions: + Python 3.4, - Python 3.3
2012-09-05 02:53:09rhettingersetassignee: rhettinger
2012-09-03 23:14:08eng793setmessages: + msg169814
2012-09-03 23:04:19serhiy.storchakasetmessages: + msg169813
2012-09-03 22:55:55eng793setmessages: + msg169812
2012-09-03 22:03:38r.david.murraysetmessages: + msg169811
2012-09-03 22:01:25r.david.murraysetmessages: + msg169810
2012-09-03 21:59:35r.david.murraysetmessages: + msg169809
2012-09-03 20:59:49serhiy.storchakasetmessages: + msg169806
2012-09-03 18:06:24eng793setmessages: + msg169790
2012-09-01 08:38:56eng793setfiles: + random.patch
keywords: + patch
messages: + msg169615
2012-09-01 08:37:11serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg169614
2012-09-01 02:16:14r.david.murraysetnosy: + rhettinger, r.david.murray
messages: + msg169605
2012-09-01 02:06:18eng793create