summaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
authorNiklas Haas <git@nand.wakku.to>2016-03-20 18:17:34 +0100
committerwm4 <wm4@nowhere>2016-03-20 19:51:22 +0100
commitb9c48ca8f33e63549f51edb08bd50cc6cc8badbb (patch)
treee02ce982a05e22815a23cd2d75a5e37fa51e7067 /common
parent3353923f2906368fb4d0b1fc0927f9f8fce30cf8 (diff)
downloadmpv-b9c48ca8f33e63549f51edb08bd50cc6cc8badbb.tar.bz2
mpv-b9c48ca8f33e63549f51edb08bd50cc6cc8badbb.tar.xz
playlist: improve shuffle algorithm
The old algorithm produced results which were not uniformly distributed, i.e. some particular shuffles were preferred over others. The new algorithm is an implementation of the Fisher-Yates shuffle which is guaranteed to shuffle uniformly given a sufficiently uniform rand() and ignoring potential floating-point errors. Signed-off-by: wm4 <wm4@nowhere>
Diffstat (limited to 'common')
-rw-r--r--common/playlist.c8
1 files changed, 3 insertions, 5 deletions
diff --git a/common/playlist.c b/common/playlist.c
index 4c003c5f21..b2b297d671 100644
--- a/common/playlist.c
+++ b/common/playlist.c
@@ -169,11 +169,9 @@ void playlist_shuffle(struct playlist *pl)
arr[n] = pl->first;
playlist_unlink(pl, pl->first);
}
- for (int n = 0; n < count; n++) {
- int other = (int)((double)(count) * rand() / (RAND_MAX + 1.0));
- struct playlist_entry *tmp = arr[n];
- arr[n] = arr[other];
- arr[other] = tmp;
+ for (int n = 0; n < count - 1; n++) {
+ int j = (int)((double)(count - n) * rand() / (RAND_MAX + 1.0));
+ MPSWAP(struct playlist_entry *, arr[n], arr[n + j]);
}
for (int n = 0; n < count; n++)
playlist_add(pl, arr[n]);