Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

Correct `_.sample` to avoid favoring putting the second half of the a…

…rray into the front and the first half in the back.
commit 1276bf8c7260f3fa47ff277daad051c5da314c7e 1 parent 9ef5c5d
@jdalton jdalton authored
Showing with 9 additions and 10 deletions.
  1. +9 −10 lodash.src.js
View
19 lodash.src.js
@@ -7086,19 +7086,18 @@
var length = collection.length;
return length > 0 ? collection[baseRandom(0, length - 1)] : undefined;
}
- var result = toArray(collection),
+ var index = -1,
+ result = toArray(collection),
length = result.length,
- index = length;
+ lastIndex = length - 1;
n = nativeMin(n < 0 ? 0 : (+n || 0), length);
- var end = length - n;
- while (index-- > end) {
- var rand = baseRandom(0, index),
- othIndex = length - index - 1,
- othValue = result[othIndex];
-
- result[othIndex] = result[rand];
- result[rand] = othValue;
+ while (++index < n) {
+ var rand = baseRandom(index, lastIndex),
+ value = result[rand];
+
+ result[rand] = result[index];
+ result[index] = value;
}
result.length = n;
return result;

4 comments on commit 1276bf8

@jdalton
Owner

Hey @jridgewell, I haven't had to tackle Fisher–Yates shuffle in a while. Mind giving me a review of the significance of baseRandom(index, lastIndex).

@jridgewell

That'll do it. I was using thinking baseRandom returned min upto but excluding max.

Sorry if my comment came off harsh. I've got to work on that.

@jdalton
Owner

Sorry if my comment came off harsh. I've got to work on that.

Naw, my fuse is short at the end of the day. It's my bad.

Still though a walkthrough of the baseRandom(index, lastIndex) significance would be appreciated.

@jridgewell

Oh, I thought you were asking about lastIndex specifically.

It's all about the index that you're going to be storing the random value in. If you put it in the end of the array (as underscore does), you can't select that last index anymore — it's already "shuffled". Same if you store it in the beginning of the array. So, you have to adjust the range where your next random index could be so you don't select an already shuffled index.

[1, 2, 3, 4]
 ^ index
          ^ end
       ^ random

[3, 2, 1, 4]
    ^ index
          ^ end
          ^ random

[3, 4, 1, 2]
       ^ index
          ^ end
       ^ random

[3, 4, 1, 2]
          ^ index
          ^ end
          ^ random
Please sign in to comment.
Something went wrong with that request. Please try again.