diff options
author | Niklas Haas <git@nand.wakku.to> | 2016-03-20 18:17:34 +0100 |
---|---|---|
committer | wm4 <wm4@nowhere> | 2016-03-20 19:51:22 +0100 |
commit | b9c48ca8f33e63549f51edb08bd50cc6cc8badbb (patch) | |
tree | e02ce982a05e22815a23cd2d75a5e37fa51e7067 /common/playlist.c | |
parent | 3353923f2906368fb4d0b1fc0927f9f8fce30cf8 (diff) | |
download | mpv-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/playlist.c')
-rw-r--r-- | common/playlist.c | 8 |
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]); |