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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) |
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) * |
Date: 2012-11-04 01:11 |
I've committed the patch, thank you Alessandro.
|
|
Date |
User |
Action |
Args |
2022-04-11 14:57:35 | admin | set | github: 60041 |
2012-11-04 01:11:50 | pitrou | set | status: open -> closed
assignee: rhettinger ->
nosy:
+ pitrou messages:
+ msg174731 resolution: fixed stage: resolved |
2012-11-04 01:11:07 | python-dev | set | nosy:
+ python-dev messages:
+ msg174730
|
2012-10-06 18:32:03 | serhiy.storchaka | set | messages:
+ msg172234 |
2012-10-06 04:26:21 | ezio.melotti | set | nosy:
+ ezio.melotti messages:
+ msg172166
|
2012-09-05 03:11:30 | rhettinger | set | messages:
+ msg169854 versions:
+ Python 3.4, - Python 3.3 |
2012-09-05 02:53:09 | rhettinger | set | assignee: rhettinger |
2012-09-03 23:14:08 | eng793 | set | messages:
+ msg169814 |
2012-09-03 23:04:19 | serhiy.storchaka | set | messages:
+ msg169813 |
2012-09-03 22:55:55 | eng793 | set | messages:
+ msg169812 |
2012-09-03 22:03:38 | r.david.murray | set | messages:
+ msg169811 |
2012-09-03 22:01:25 | r.david.murray | set | messages:
+ msg169810 |
2012-09-03 21:59:35 | r.david.murray | set | messages:
+ msg169809 |
2012-09-03 20:59:49 | serhiy.storchaka | set | messages:
+ msg169806 |
2012-09-03 18:06:24 | eng793 | set | messages:
+ msg169790 |
2012-09-01 08:38:56 | eng793 | set | files:
+ random.patch keywords:
+ patch messages:
+ msg169615
|
2012-09-01 08:37:11 | serhiy.storchaka | set | nosy:
+ serhiy.storchaka messages:
+ msg169614
|
2012-09-01 02:16:14 | r.david.murray | set | nosy:
+ rhettinger, r.david.murray messages:
+ msg169605
|
2012-09-01 02:06:18 | eng793 | create | |