)]}'
{
  "commit": "9251546bac031db325da80c4a8429db67c5578f7",
  "tree": "1bb66c160c32f639de5e772b3c49c9008e6b99e5",
  "parents": [
    "7dc23aff3001d22384caef9a1197f970c5f0b845"
  ],
  "author": {
    "name": "Sergei Trofimovich",
    "email": "siarheit@google.com",
    "time": "Tue Jun 18 22:37:54 2024 +0100"
  },
  "committer": {
    "name": "Paul Smith",
    "email": "psmith@gnu.org",
    "time": "Mon Sep 02 15:11:36 2024 -0400"
  },
  "message": "Fix biased shuffle by avoiding already \"struck\" elements\n\nArtem Klimov noticed that current shuffle implementation suffers from\nprobability bias due to a typical bug in the shuffling implementation.\n\nWhen we consider already shuffled element we slightly bias their\npropability.\n\nhttps://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm\nsuggests shuffling each \"struck\" element only once.\n\nBefore the change probabilities of 4-element array to land from `i`\nindex to `j` index are:\n\n          0     1     2     3\n      _____ _____ _____ _____\n  0 | 25.00 29.30 24.60 21.10\n  1 | 25.00 22.25 28.13 24.63\n  2 | 25.00 23.44 22.26 29.30\n  3 | 25.00 25.01 25.01 24.98\n\nNote that `0-\u003e1` probability is almost 29% while `0-\u003e3` os only 21%.\n\nAfter the change probabilities are not as biased:\n\n          0     1     2     3\n      _____ _____ _____ _____\n  0 | 24.99 24.99 25.01 25.01\n  1 | 24.99 25.04 24.99 24.99\n  2 | 25.01 25.00 25.00 24.99\n  3 | 25.01 24.98 25.00 25.01\n\n* src/shuffle.c (random_shuffle_array): Fix biased shuffle by avoiding\nalready \"struck\" elements.\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "8fbefc7b30d7f14d288036770d4626fd5b161ac9",
      "old_mode": 33188,
      "old_path": "src/shuffle.c",
      "new_id": "cda28f200699a521b3fa2eaf97f5d4ad077bd81d",
      "new_mode": 33188,
      "new_path": "src/shuffle.c"
    }
  ]
}