PDA

View Full Version : Shuffle algorithm

RonM
2008-05-04, 19:43
Anyone know what the shuffle algorithm is for the Duet? I mean in general terms.

I've gotten tired of "shuffle" or "random" features in devices that are clearly not, with distinct patterns always emerging. It would be nice if the Duet had something approximating true randomness, with each unplayed tune having an equal chance of being the next one queued up.

R.

JJZolx
2008-05-04, 19:53
Anyone know what the shuffle algorithm is for the Duet? I mean in general terms.

I've gotten tired of "shuffle" or "random" features in devices that are clearly not, with distinct patterns always emerging. It would be nice if the Duet had something approximating true randomness, with each unplayed tune having an equal chance of being the next one queued up.

R.

Define "unplayed".

dean
2008-05-04, 21:06
For the shuffle modes, the playlist is shuffled in place using a Fischer-Yates shuffle: http://en.wikipedia.org/wiki/Knuth_shuffle

kmr
2008-05-04, 22:14
But what algorithm produces the random numbers? Hopefully not the C rand() function!

"BTW, a member of the ANSI C committee once told me that the only thing rand is used for in C code is to decide whether to pick up the axe or throw the dwarf..." - from Tim Peters, numerical methods wizard and Python hacker extraordinare

pippin
2008-05-04, 23:51
Do you plan to encrypt something with the titles in your playlist?
Otherwise even rand() should be good enough for shuffling.

To define "equal chance" for such an application is not that simple, though. There's an abundance of subjective priority parameters you may or may not want to see in that (e.g. it can be perfectly "random" to have the same song played twice if shuffling a 200 track playlist, as #200 and #1 of the second iteration, but it definitely does not FEEL like it, so there are algorithms which take care of that; dou you want to play longer tracks as often as shorter ones; do you want to shuffle albums along with the rest of the tracks or make sure they get somewhat "distributed" etc. etc.).

Have a look at Erland's "Dynamic Playlists" plugin, I think you can define your own algorithms there.

RonM
2008-05-05, 06:06
Ideally, I'd like an algorithm that dropped played titles from the playlist, until all were played and it started over.

It would be nice if there were some alternative choices, options only -- e.g. to no play from the same album two cuts in a row, or to choose a spiral method, where a track would be played from each of the included albums until they'd all had a track played, and then it started over, with both tracks and albums being randomly selected. I'm sure that would be too much to ask for.

R.

pippin
2008-05-05, 06:40
Ideally, I'd like an algorithm that dropped played titles from the playlist, until all were played and it started over.

It would be nice if there were some alternative choices, options only -- e.g. to no play from the same album two cuts in a row, or to choose a spiral method, where a track would be played from each of the included albums until they'd all had a track played, and then it started over, with both tracks and albums being randomly selected. I'm sure that would be too much to ask for.

R.

Again. Have a look at the "Dynamic Playlists" plugin

http://wiki.erland.homeip.net/index.php/Category:SlimServer

erland
2008-05-05, 11:20
It would be nice if there were some alternative choices, options only -- e.g. to no play from the same album two cuts in a row, or to choose a spiral method, where a track would be played from each of the included albums until they'd all had a track played, and then it started over, with both tracks and albums being randomly selected. I'm sure that would be too much to ask for.

Dynamic Playlist plugin together with Custom Skip can pretty much do all this. Although, it require some work to configure it.

The basic idea is:
- Dynamic Playlist plugin plays either saved playlists by itself or also random mixes if SQL Playlist plugin is installed.
- Dynamic Playlist checks each tracks against filters defined in the Custom Skip plugin, if a track matches any filter it is skipped, if it doesn't match it is added to the current playlist.
- In the Custom Skip plugin you can setup a filter to skip tracks that have been recently played, or tracks by artists that have been recently played.

If you want to do more advanced filtering in Custom Skip based on when a track was last played, you will also need the TrackStat plugin which keeps a history of when a specific track has been played.

So it can be done but since the functionality is divided into several plugins and very configurable it is a bit of work to set it up exactly as you want it.

JJZolx
2008-05-05, 11:21
Ideally, I'd like an algorithm that dropped played titles from the playlist, until all were played and it started over.

It would be nice if there were some alternative choices, options only -- e.g. to no play from the same album two cuts in a row, or to choose a spiral method, where a track would be played from each of the included albums until they'd all had a track played, and then it started over, with both tracks and albums being randomly selected. I'm sure that would be too much to ask for.

All that for background music?

Siduhe
2008-05-05, 11:39
I would also recommend looking at MusicIP which is supported within Squeezecenter. It's not random, but produces some great playlists and is easy to configure different types of mixes (once you have it set up) including "do not repeat tracks from album/artist within [12] tracks] - Jagged Mix might work well for you.

kmr
2008-05-06, 23:17
Do you plan to encrypt something with the titles in your playlist?
Otherwise even rand() should be good enough for shuffling.

It's not the sorted order of an individual playlist that is the problem; I totally agree that rand() is good enough for that.

What I really dislike is correlation in the successive random number sequences. For example, I like to use "shuffle songs" on my late 2004 4th gen iPod in my car; however, if I don't use the iPod over the weekend, it resets itself and on Monday morning, I select "shuffle songs" again. The new "random" playlist is strongly correlated with the last "random" playlist - I hear largely the same songs in not too far off from the same order. This is a classic case of correlation in the RNG. So, I was curious if the SqueezeCenter shuffle algorithm uses a good, uncorrelated RNG or not (and yes, I'm well aware that correlation is only one of many tests to determine the goodness of an RNG).

pippin
2008-05-07, 15:50
It's not the sorted order of an individual playlist that is the problem; I totally agree that rand() is good enough for that.

What I really dislike is correlation in the successive random number sequences. For example, I like to use "shuffle songs" on my late 2004 4th gen iPod in my car; however, if I don't use the iPod over the weekend, it resets itself and on Monday morning, I select "shuffle songs" again. The new "random" playlist is strongly correlated with the last "random" playlist - I hear largely the same songs in not too far off from the same order. This is a classic case of correlation in the RNG. So, I was curious if the SqueezeCenter shuffle algorithm uses a good, uncorrelated RNG or not (and yes, I'm well aware that correlation is only one of many tests to determine the goodness of an RNG).

No. I have the same thing in my car radio. This is usually not a correlation thing, because you don't hear correlations, as soon as the first track is different you are on a completely new trail and don't tell me that you can hear a correlation like in
1 20 4 80 5 vs 2 40 8 160 10

What you describe usually is a bad randseed issue, that is: the same start value is used on consecutive rand sequences instead of using something like time() as a start value.

kmr
2008-05-08, 19:11
No. I have the same thing in my car radio. This is usually not a correlation thing, because you don't hear correlations, as soon as the first track is different you are on a completely new trail and don't tell me that you can hear a correlation like in
1 20 4 80 5 vs 2 40 8 160 10

What you describe usually is a bad randseed issue, that is: the same start value is used on consecutive rand sequences instead of using something like time() as a start value.

I think you're mistaken here; if the RNG seed were the same, you'd get the SAME random number sequence. What I get with my iPod and dislike is similar but not identical random number sequences - a classic sign of correlation with the RNG (i.e., different seeds produce similar sequences). And yes, I can tell that, out of several thousand songs, I tend to hear the same ones in the first 100 or so.

peter
2008-05-08, 22:17
kmr wrote:
> pippin;299889 Wrote:
>
>> No. I have the same thing in my car radio. This is usually not a
>> correlation thing, because you don't hear correlations, as soon as the
>> first track is different you are on a completely new trail and don't
>> tell me that you can hear a correlation like in
>> 1 20 4 80 5 vs 2 40 8 160 10
>>
>> What you describe usually is a bad randseed issue, that is: the same
>> start value is used on consecutive rand sequences instead of using
>> something like time() as a start value.
>>
>
> I think you're mistaken here; if the RNG seed were the same, you'd get
> the SAME random number sequence. What I get with my iPod and dislike
> is similar but not identical random number sequences - a classic sign
> of correlation with the RNG (i.e., different seeds produce similar
> sequences). And yes, I can tell that, out of several thousand songs, I
> tend to hear the same ones in the first 100 or so.
>

Well, the software is open source so pry out the Fisher-Yates shuffling
algorithm and the RNG and create a benchmark setup to measure the
correlation you mention. Tell us about the result and I'm sure people
will start to work on a better algorithm especially with a method to
measure the effect. Me, I'm sceptical. The human mind is so eager to
find patterns, it often mistakes random chance for destiny. I can't tell
you how many times my player plays a song that applies to the situation
I'm in. I swear it's psychic!

Regards,
Peter

pippin
2008-05-08, 23:31
I think you're mistaken here; if the RNG seed were the same, you'd get the SAME random number sequence. What I get with my iPod and dislike is similar but not identical random number sequences - a classic sign of correlation with the RNG (i.e., different seeds produce similar sequences). And yes, I can tell that, out of several thousand songs, I tend to hear the same ones in the first 100 or so.

Can you describe what a "similar but not identical" random sequence is? You are correct, my car radio plays IDENTICAL sequenced. But I don't fully understand what you mean, then. To have similar sequences is not necessarily a correlation, a correlations means predictability.

kmr
2008-05-10, 00:16
Can you describe what a "similar but not identical" random sequence is? You are correct, my car radio plays IDENTICAL sequenced. But I don't fully understand what you mean, then. To have similar sequences is not necessarily a correlation, a correlations means predictability.

Correlation does NOT mean predictability: the most common statistical meaning of correlation is the Pearson correlation coefficient, which is what I have been referring to here (see http://mathworld.wolfram.com/CorrelationCoefficient.html if you want the gory details). The amount of correlation between two random variables measures the linear dependence of those two random variables, but does not imply prediction (the post hoc ergo prompter hoc fallacy).

If I spoke Perl (I don't - I'm a Python hacker), I would dig into the source and see what RNG gets used for the shuffle. But I don't feel like spending the time to learn enough Perl and learn the ins-and-outs of its RNG(s) to do that right now. I don't use shuffle mode for SqueezeCenter much anyway!

htrd
2008-05-10, 01:11
The random shuffle code is here. Without having worked through all the
details, it looks like it is using mysql to "order by RAND()"

http://svn.slimdevices.com/7.0/trunk/server/Slim/Plugin/RandomPlay/Plugin.pm?revision=19572&view=markup

That is, mysql generates a random number for each matching track then
returns them in the order of those random numbers. Unless I am mistaken
that is not Fisher-Yates?

Anyone know what rng algorithm is used by mysql, and how is it seeded? My
google skills seem to be lacking.

peter
2008-05-12, 06:23
Toby Dickenson wrote:
> The random shuffle code is here. Without having worked through all the
> details, it looks like it is using mysql to "order by RAND()"
>
> http://svn.slimdevices.com/7.0/trunk/server/Slim/Plugin/RandomPlay/Plugin.pm?revision=19572&view=markup
>

AFAIK the 'shuffle' function of SC is *not* the same as the RandomPlay
plugin.

> That is, mysql generates a random number for each matching track then
> returns them in the order of those random numbers. Unless I am mistaken
> that is not Fisher-Yates?
>
> Anyone know what rng algorithm is used by mysql, and how is it seeded? My
> google skills seem to be lacking.
Dunno.

Regards,
Peter