Well, I think a normal non-Java programmer would return a new shuffled list instead of shuffling the existing list in-place. Normally I'd write that off to "when in Rome," but...
... in this case, it actually makes a big difference API-wise. If you have a lazy, functional shuffle (which is trivial to adapt from Fisher-Yates) then the use case of "get me 5 randomly selected things from this collection of 1 million things" just translates into "take(shuffle(list), 5)". If your shuffle shuffles the whole list in place, you can't get away with that, and you need a new special-purpose function to get your random things. So I really would prefer the functional version to the in-place version.
mquander, while I would generally agree that it's more flexible that way, you shouldn't forget that taking x elements from a list of n elements using take(shuffle(list), 5) is O(n). Knuth describes a simple algorithm to take x elements randomly in O(x), so in this particular case, there's some good motivation to have a specialized function.
Yes, the first problem is that it doesn't return the shuffled list. This is exacerbated by the fact that Java omitted the comma operator, which would have at least allowed a nasty workaround.
I'd certainly prefer a new shuffled list to shuffling in place, but it isn't too nasty to copy the list before shuffling.
The second problem is that this should not be a static method.
I do not see any problem: - using a static method is the correct way to present an algorithm that works on an Interface (there is no concrete List class where a method could be added) - If the list is huge (>half of the available memory), creating a shuffled copy will lead to an out-of-memory situation, while the in-place version will work fine
The void result is probably deliberate command-query separation. Lacking a naming convention like shuffle!, Java uses the return type as a way of declaring that the operation has side effects, so users won't be surprised when it modifies its argument. I'm not convinced it's worth the inconvenience, but Java culture seems to think otherwise; most similar operations return void. And they don't see the point of having a nondestructive version too (especially for shuffle, since the usual implementation is destructive).
Between linguistic and cultural constraints, this may be the best option the authors had. Working on the Java libraries must have been a frustrating experience.
9 comments:
Well, I think a normal non-Java programmer would return a new shuffled list instead of shuffling the existing list in-place. Normally I'd write that off to "when in Rome," but...
... in this case, it actually makes a big difference API-wise. If you have a lazy, functional shuffle (which is trivial to adapt from Fisher-Yates) then the use case of "get me 5 randomly selected things from this collection of 1 million things" just translates into "take(shuffle(list), 5)". If your shuffle shuffles the whole list in place, you can't get away with that, and you need a new special-purpose function to get your random things. So I really would prefer the functional version to the in-place version.
mquander, while I would generally agree that it's more flexible that way, you shouldn't forget that taking x elements from a list of n elements using take(shuffle(list), 5) is O(n). Knuth describes a simple algorithm to take x elements randomly in O(x), so in this particular case, there's some good motivation to have a specialized function.
Well mquander mentioned a lazy shuffle ...
Anyhow, shuffle should return the List so you can chain calls using return values
Yes, the first problem is that it doesn't return the shuffled list. This is exacerbated by the fact that Java omitted the comma operator, which would have at least allowed a nasty workaround.
I'd certainly prefer a new shuffled list to shuffling in place, but it isn't too nasty to copy the list before shuffling.
The second problem is that this should not be a static method.
I do not see any problem:
- using a static method is the correct way to present an algorithm that works on an Interface (there is no concrete List class where a method could be added)
- If the list is huge (>half of the available memory), creating a shuffled copy will lead to an out-of-memory situation, while the in-place version will work fine
java.util.Collections must be what's wrong.
The void result is probably deliberate command-query separation. Lacking a naming convention like shuffle!, Java uses the return type as a way of declaring that the operation has side effects, so users won't be surprised when it modifies its argument. I'm not convinced it's worth the inconvenience, but Java culture seems to think otherwise; most similar operations return void. And they don't see the point of having a nondestructive version too (especially for shuffle, since the usual implementation is destructive).
Between linguistic and cultural constraints, this may be the best option the authors had. Working on the Java libraries must have been a frustrating experience.
I may have instead written
public static <T> void shuffle(List<T> list)
for an in place version.
But I don't think that makes any real difference.
Post a Comment