]> git.ipfire.org Git - thirdparty/make.git/commit
Fix biased shuffle by avoiding already "struck" elements
authorSergei Trofimovich <siarheit@google.com>
Tue, 18 Jun 2024 21:37:54 +0000 (22:37 +0100)
committerPaul Smith <psmith@gnu.org>
Mon, 2 Sep 2024 19:11:36 +0000 (15:11 -0400)
commit9251546bac031db325da80c4a8429db67c5578f7
tree1bb66c160c32f639de5e772b3c49c9008e6b99e5
parent7dc23aff3001d22384caef9a1197f970c5f0b845
Fix biased shuffle by avoiding already "struck" elements

Artem Klimov noticed that current shuffle implementation suffers from
probability bias due to a typical bug in the shuffling implementation.

When we consider already shuffled element we slightly bias their
propability.

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
suggests shuffling each "struck" element only once.

Before the change probabilities of 4-element array to land from `i`
index to `j` index are:

          0     1     2     3
      _____ _____ _____ _____
  0 | 25.00 29.30 24.60 21.10
  1 | 25.00 22.25 28.13 24.63
  2 | 25.00 23.44 22.26 29.30
  3 | 25.00 25.01 25.01 24.98

Note that `0->1` probability is almost 29% while `0->3` os only 21%.

After the change probabilities are not as biased:

          0     1     2     3
      _____ _____ _____ _____
  0 | 24.99 24.99 25.01 25.01
  1 | 24.99 25.04 24.99 24.99
  2 | 25.01 25.00 25.00 24.99
  3 | 25.01 24.98 25.00 25.01

* src/shuffle.c (random_shuffle_array): Fix biased shuffle by avoiding
already "struck" elements.
src/shuffle.c