Click here to Skip to main content
15,896,606 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.

 
GeneralRe: Thought of the Day Pin
lopatir24-Oct-17 5:52
lopatir24-Oct-17 5:52 
GeneralRe: Thought of the Day Pin
Nagy Vilmos24-Oct-17 6:54
professionalNagy Vilmos24-Oct-17 6:54 
GeneralRe: Thought of the Day Pin
Tim Deveaux24-Oct-17 7:12
Tim Deveaux24-Oct-17 7:12 
GeneralRe: Thought of the Day Pin
PIEBALDconsult24-Oct-17 7:54
mvePIEBALDconsult24-Oct-17 7:54 
GeneralRe: Thought of the Day Pin
OriginalGriff24-Oct-17 8:17
mveOriginalGriff24-Oct-17 8:17 
GeneralRe: Thought of the Day Pin
snorkie24-Oct-17 8:32
professionalsnorkie24-Oct-17 8:32 
GeneralRe: Thought of the Day Pin
Daniel Pfeffer24-Oct-17 8:55
professionalDaniel Pfeffer24-Oct-17 8:55 
GeneralOn list.OrderBy(x => random.Next()) Pin
harold aptroot24-Oct-17 3:27
harold aptroot24-Oct-17 3:27 
Apparently this is a popular shuffling algorithm. Unfortunately it has a couple of problems with it.

First, OrderBy is not a linear time operation, while shuffling should be. That is already sufficient reason to stop using it to shuffle, especially on big lists, but there is more.

Less obviously, it does not choose a permutation with uniform probability across all possible permutations. This will be clear if we intentionally make it worse first and work from there. Consider
C#
list.OrderBy(x => random.Next() & 1)
Now every element only gets a random bit. Assume we shuffle a list with 2 elements A and B, there are only 2 outcomes, AB and BA. BA happens when the first element gets a 1 and the second element gets a 0. AB happens in all other cases, because in the case of a draw they are left in their original order.

This is obviously bad. One outcome is chosen with probability 0.25, and the other with probability 0.75. With more random bits both probabilities get closer and closer to 0.5, but they never quite make it all the way there.

Larger lists are worse. The probability of two elements being assigned the same random number gets large enough to worry about really quickly, which you have heard about as the birthday paradox. Any time a group of elements is assigned the same random number, those elements will not be reordered. Of course it is OK to not reorder elements, but the probability of that happening is larger than it should be. This is especially noticeable for lists larger than the space from which random numbers are drawn.

Consider what would have happened if the snippet above was used to sort a list of 3 elements, A B and C. At least 2 of them must get the same random value, because there are only two different values to randomly draw. That means that at least 2 elements remain in their original order, so it is impossible to generate CBA. For the full number of random bits this problem only happens for lists with over 2 billion elements, but for shorter lists it is still the case that permutations with many inversions are generated with a probability that is too low.

Here's an other way to look at it. Clearly it would work if all elements were assigned a unique random number. That is equivalent to applying a permutation with a key-value sort, which is a common (though inefficient) technique. It doesn't even need to be a permutation on the numbers 0 to N-1, it's OK if there are "gaps", that's just a relabeling. So as long as only unique random numbers are generated, it's fine. What is the probability that that does not happen? If I got the formula right then that means that for a list of length 10000 there is already a probability of 2% that you're in a "bad case" (with some duplicate), quickly growing to 90% for size 100000. In practice that would still be really hard to notice since those "bad cases" don't create an immediate problem, they're just subtly skewing the probability distribution, but it is still wrong.
GeneralRe: On list.OrderBy(x => random.Next()) Pin
CodeWraith24-Oct-17 3:52
CodeWraith24-Oct-17 3:52 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
harold aptroot24-Oct-17 4:12
harold aptroot24-Oct-17 4:12 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
CodeWraith24-Oct-17 4:37
CodeWraith24-Oct-17 4:37 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
lopatir24-Oct-17 4:44
lopatir24-Oct-17 4:44 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
CodeWraith24-Oct-17 5:13
CodeWraith24-Oct-17 5:13 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
Richard Andrew x6424-Oct-17 9:20
professionalRichard Andrew x6424-Oct-17 9:20 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
Richard Deeming24-Oct-17 4:05
mveRichard Deeming24-Oct-17 4:05 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
harold aptroot24-Oct-17 4:10
harold aptroot24-Oct-17 4:10 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
megaadam24-Oct-17 4:20
professionalmegaadam24-Oct-17 4:20 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
BillWoodruff24-Oct-17 4:20
professionalBillWoodruff24-Oct-17 4:20 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
harold aptroot24-Oct-17 5:10
harold aptroot24-Oct-17 5:10 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
BillWoodruff24-Oct-17 22:03
professionalBillWoodruff24-Oct-17 22:03 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
harold aptroot25-Oct-17 1:10
harold aptroot25-Oct-17 1:10 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
BillWoodruff25-Oct-17 2:44
professionalBillWoodruff25-Oct-17 2:44 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
harold aptroot25-Oct-17 5:21
harold aptroot25-Oct-17 5:21 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
BillWoodruff25-Oct-17 6:56
professionalBillWoodruff25-Oct-17 6:56 
GeneralRe: On list.OrderBy(x => random.Next()) Pin
harold aptroot25-Oct-17 7:08
harold aptroot25-Oct-17 7:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.