A Better Random Play Routine

[Psycho_Dave]

I'd like to see a better Random playback routine implemented. I've experienced the following scenarios:

(1) The same track gets repeated just one or two tracks after it was first played.
(2) Some tracks almost never get heard, even after the player allegedly finishes playing all the songs on it's random playback.
(3) I once went for a week never hearing one of the songs that I know was on the player, while other songs repeated several times. Then, the song played once.

I recommend the following:

Have the random playback routine compile a list of tracks, but in the process of generating the list, it checks each new random selection against the rest of the list to make sure the track is not a repeat -- or -- once a track is randomly selected, the routine remembers it, and doesn't let it repeat until all of the tracks in the database have been played at least once.

I don't know if this kind of routine would be a memory hog or not, but When I took programming some 20 years ago or more, we used to make such routines, back in the days when memory was always a huge concern.

I don't know if a recent update has done this, but it would be nice to avoid playing the same track too close to itself

[Llorean]

(1) is impossible unless there's a bug. Has this happened in a current build? There WAS a bug that did this, but it was fixed a couple weeks ago.

"Random" in Rockbox works by taking your list of songs, and shuffling them. If you have 400 songs, then you will hear 400 songs before there's any repeat (unless a song shows up more than once in the list, then you will hear it exactly how many times it was in the original list). It's like shuffling a deck of cards (thus it is called "Shuffle" and not "Random"). No matter how you shuffle a deck, if you draw it one at a time and discard the ones you draw you'll never draw the same one twice, because now it's in the discard pile.

(2) Again, impossible. If you sit through the whole list, you'll hear all of them exactly how many times that song shows up in the original list you shuffled.

(3) Again, impossible.

Have you actually, while NOT restarting the playlist (resuming playback) kept track of every song that plays and tested these findings? The playback is actually not "Random", it's just shuffling a list. You can look at the list and verify every single song in it, and their new, shuffled, positions.

[JdGordon]

Have you actually, while NOT restarting the playlist (resuming playback) kept track of every song that plays and tested these findings? The playback is actually not "Random", it's just shuffling a list. You can look at the list and verify every single song in it, and their new, shuffled, positions.

even with resuming the playlist that shouldnt be possible.. shuffled playlists keep their random seed so it will always resume with the same order

[Llorean]

Sorry. To clarify, by "restart" I mean "launch the playlist again", and meant they should resume it instead of restarting.

[Psycho_Dave]

Okay, I upgraded to the latest build, and that seems to be much better. It played several songs this morning that I never heard since I put them on, and no repeats yet.

[shoe]

I haven't had the same problem as Psycho_Dave, but I have noticed that shuffle doesn't do a truly random shuffle -- if I shuffle all my music I end up hearing more songs by the same artists than if it were random.  Is this intentional?  Is there a constant that is easily varied in the source code to make it more random?

[Llorean]

It is random. It takes a playlist, and shuffles it. It does not know anything about the songs and does not weight it.

Have you done some actual testing, or are you just going off "I notice the same artist several times"? And have you done a couple thousand tests? If it's truly random, there's no reason why it couldn't give you several songs by the same artists each time you reshuffle for several shuffles. Thus the definition of "random."

[safetydan]

The Rockbox rand function is based on a mersenne twister which is one of the best PRNG's you can get. About the only thing that might be affecting playlist randomness is the size of the playlist. Looking at the playlist shuffle code it basically does a modulus (i.e. % operator) which tends to throw away some of that randomness. Maybe that's what people are seeing/hearing?

[LinusN]

I took some time to experiment with the distribution of the shuffles.

The shuffle algorithm we use is called the Fisher-Yates algorithm, and is generally accepted as a good shuffling algorithm.

However, the current Rockbox version uses the modulo operator to generate a random value in the desired range, so there is a potential problem with modulo bias, see http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#Modulo_bias for an explanation.

I implemented a version that compensates for the bias by discarding random numbers that are out of range, as suggested by the article, but there was practically no difference.

I even did a small test with only 3 songs. I shuffled them 50 million times and counted the occurrences of the different permutations. It turned out that the bias compensation even made it slightly worse than the original version, which had a very even distribution.

I can't see any problem with the shuffle as it is.

We have had similar complaints about the shuffling since the first time we implemented it, so there may still be a bug lurking somewhere, but so far we haven't found any problems.

Many times, it turned out that the user had several duplicate songs on the player, leading him/her to believe that the shuffle was bad.

[shoe]

Thanks for all the info.  I just wrote a program to report a list of playlist positions for each artist in the playlist.  Now I need to figure out the analysis, to see if my claim is correct.  More later...

[Multiplex]

The shuffle algorithm we use is called the Fisher-Yates algorithm, and is generally accepted as a good shuffling algorithm.

Is my memory fading or did the code change from the Mersenne Twister?.

I seem to remember that proper shuffle was one of the original design goals for Rockbox... but I can't find the History text in the Wiki.

[MarcGuay]

Seems like this page could use an update by someone well-brained on the subject: http://www.rockbox.org/twiki/bin/view/Main/ShuffleExplained

[LinusN]

Seems like this page could use an update by someone well-brained on the subject: http://www.rockbox.org/twiki/bin/view/Main/ShuffleExplained

As far as I can see, that page is still 100% correct.

The shuffle algorithm is called the Fisher-Yates algorithm, and the random number generator is called the Mersenne Twister.

[goffa]

haven't noticed this on shuffle or random, but i seem to get the same dirs playing a lot with the random folder advance plugin.

[shoe]

Have you done some actual testing, or are you just going off "I notice the same artist several times"?

It was the latter here.  It seemed like after I had heard several songs by a certain artist I would be more likely to hear another song by that artist than another artist that I had not heard yet.  I played this game a few times: "Ive been hearing a lot of Led Zeppelin recently, lets see if I hear another Led Zeppelin before something by Tom Petty" (for example, since I have at least as many tracks by Tom Petty) and it seemed like it came true more often than not.

Ive seen other programs that have an "adjustable" shuffle mode, where you can specify how shuffled the playlists are, I wondered if there was something like this going on behind the scenes in Rockbox.

I tried to be a little more rigorous here, but I can't figure out a way to get a good measure of randomness.  I saved all my music shuffled in playlists a few times, and I wrote a Matlab program that parses the playlist files and plots some histograms based on artist location, but this is still subjective, since all I can do is look at the histograms and decide by eye if they look fairly random.  Nothing jumps out at me.

I assume, based on the information from LinusN that everything is working as it is supposed to, and I was just fooling myself.

By the way, thanks to everybody involved for this quality software!