Add List.shuffle().

Add List.shuffle().

Will add tests too.

R=floitsch@google.com

Committed: https://code.google.com/p/dart/source/detail?r=28206

[Lasse Reichstein Nielsen, 2013-09-26 13:02:36]

I hope I have all the "implements List" covered. 
We should see if some could be made to extend ListBase or mixin ListMixin
instead.

[rakudrama, 2013-09-26 13:33:25]

https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart
File sdk/lib/collection/list.dart (right):

https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart#...
sdk/lib/collection/list.dart:305: Random random = new Random();
This needs to be an optional parameter to assist in the generation of
deterministic but arbitrary state, e.g. you should not use shuffle in the
generation of a benchmark input unless you can arrange all platforms do the same
shuffle.

[floitsch, 2013-09-26 14:25:21]

LGTM.

https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart
File sdk/lib/collection/list.dart (right):

https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart#...
sdk/lib/collection/list.dart:305: Random random = new Random();
On 2013/09/26 13:33:25, rakudrama wrote:
> This needs to be an optional parameter to assist in the generation of
> deterministic but arbitrary state, e.g. you should not use shuffle in the
> generation of a benchmark input unless you can arrange all platforms do the
same
> shuffle.

I don't think that the additional parameter is worth it. If you can pass in your
own Random source, you are advanced enough to simply shuffle the list yourself.
This makes the benchmark robust against changes in the shuffle function itself.

[rakudrama, 2013-09-26 14:50:54]

On 2013/09/26 14:25:21, floitsch wrote:
> LGTM.
> 
> https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart
> File sdk/lib/collection/list.dart (right):
> 
>
https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart#...
> sdk/lib/collection/list.dart:305: Random random = new Random();
> On 2013/09/26 13:33:25, rakudrama wrote:
> > This needs to be an optional parameter to assist in the generation of
> > deterministic but arbitrary state, e.g. you should not use shuffle in the
> > generation of a benchmark input unless you can arrange all platforms do the
> same
> > shuffle.
> 
> I don't think that the additional parameter is worth it. If you can pass in
your
> own Random source, you are advanced enough to simply shuffle the list
yourself.
> This makes the benchmark robust against changes in the shuffle function
itself.

The benchmark was just an example.
The statement about being advanced enough applies to lots of APIs. Perhaps if
you feel this way it is a sign that shuffle is not worth it.

There are no tests. Some tests would benefit from the parameter.  It is hard to
write tests when you do not control the inputs. How do you test that the
implementation consume enough random state to produce an even distribution of
permutations?

[floitsch, 2013-09-26 15:06:23]

On 2013/09/26 14:50:54, rakudrama wrote:
> On 2013/09/26 14:25:21, floitsch wrote:
> > LGTM.
> > 
> > https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart
> > File sdk/lib/collection/list.dart (right):
> > 
> >
>
https://codereview.chromium.org/24740003/diff/1/sdk/lib/collection/list.dart#...
> > sdk/lib/collection/list.dart:305: Random random = new Random();
> > On 2013/09/26 13:33:25, rakudrama wrote:
> > > This needs to be an optional parameter to assist in the generation of
> > > deterministic but arbitrary state, e.g. you should not use shuffle in the
> > > generation of a benchmark input unless you can arrange all platforms do
the
> > same
> > > shuffle.
> > 
> > I don't think that the additional parameter is worth it. If you can pass in
> your
> > own Random source, you are advanced enough to simply shuffle the list
> yourself.
> > This makes the benchmark robust against changes in the shuffle function
> itself.
> 
> The benchmark was just an example.
> The statement about being advanced enough applies to lots of APIs. Perhaps if
> you feel this way it is a sign that shuffle is not worth it.
We have seen way too many examples where people used JavaScript's sort with a
random comparator.
This was basically the main-reason we decided to add `shuffle`.

> 
> There are no tests.
Agreed. I missed that.
@Lasse: please add tests.

> Some tests would benefit from the parameter.  It is hard to
> write tests when you do not control the inputs. How do you test that the
> implementation consume enough random state to produce an even distribution of
> permutations?
You don't. This needs to be caught by the code-review. If Lasse had used the
wrong shuffling algorithm (swapping the cursor's element with any element of the
list) you wouldn't be able to detect this either.

[kevmoo-old, 2013-09-26 15:45:39]

> > 
> > The benchmark was just an example.
> > The statement about being advanced enough applies to lots of APIs. Perhaps
if
> > you feel this way it is a sign that shuffle is not worth it.
> We have seen way too many examples where people used JavaScript's sort with a
> random comparator.
> This was basically the main-reason we decided to add `shuffle`.

Perhaps shuffle is worth it, but as a static helper in dart:collection instead
of on the base class.

Then the optional Random param doesn't feel like noise to explain on an already
large interface.

[floitsch, 2013-09-27 08:59:27]

On 2013/09/26 15:45:39, kevmoo wrote:
> > > 
> > > The benchmark was just an example.
> > > The statement about being advanced enough applies to lots of APIs. Perhaps
> if
> > > you feel this way it is a sign that shuffle is not worth it.
> > We have seen way too many examples where people used JavaScript's sort with
a
> > random comparator.
> > This was basically the main-reason we decided to add `shuffle`.
> 
> Perhaps shuffle is worth it, but as a static helper in dart:collection instead
> of on the base class.
> 
> Then the optional Random param doesn't feel like noise to explain on an
already
> large interface.

I don't think that shuffle should be static.
Fwiw I would like to push for a way to set the global seed, so that benchmarks
or tests could reliably run the same thing every time.

[Lasse Reichstein Nielsen, 2013-09-27 09:30:03]

Added test. Fixed typos. PTAL.

[floitsch, 2013-09-27 10:59:43]

LGTM.

https://codereview.chromium.org/24740003/diff/11001/tests/corelib/shuffle_tes...
File tests/corelib/shuffle_test.dart (right):

https://codereview.chromium.org/24740003/diff/11001/tests/corelib/shuffle_tes...
tests/corelib/shuffle_test.dart:55: if (--remaining == 0) {
move remaining-- into previous line.

[Lasse Reichstein Nielsen, 2013-09-27 12:35:05]

https://codereview.chromium.org/24740003/diff/11001/tests/corelib/shuffle_tes...
File tests/corelib/shuffle_test.dart (right):

https://codereview.chromium.org/24740003/diff/11001/tests/corelib/shuffle_tes...
tests/corelib/shuffle_test.dart:55: if (--remaining == 0) {
On 2013/09/27 10:59:43, floitsch wrote:
> move remaining-- into previous line.

Done.

[Lasse Reichstein Nielsen, 2013-10-03 11:09:25]

Committed patchset #3 manually as r28206 (presubmit successful).