3 ms·

The fibonacci hashing mentioned here looks to be just Kronecker low-discrepancy sequences https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Additive_recurr

The fibonacci hashing mentioned here looks to be just Kronecker low-discrepancy sequences https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Additive_recurrence https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Addit... which is used for dithering too (see eg https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ https://extremelearning.com.au/unreasonable-effectiveness-of...). It's quite likely already what Spotify were obliquely referring to. But I think the author missed a trick: tracks by an artist occur close together if your collection is already arranged by artist/album. Picking tracks far apart from the globally sorted list is what this sequence will do, and do you don't need to do anything at all to split by artist/album/category etc: 1. for the Kth track in a sorted collection of N with seed S in [0,1), pick track number floor(N((K(phi-1)+S)%1)). 2. There is no step 2. Since Spotify suggest their algorithm is only a couple of lines, I'd guess this is what they did. edited to add: the above would get pretty boring because songs would always follow one another in sequence, no matter what the seed was. But since the chance of picking an irrational number at random in a real interval is a near certainty (because rationals are countable and reals are uncountable) you can just pick any new random number as the stepsize in the sequence when you start to shuffle play and it should be good enough; picking in [.25, .75) avoids steps that take you back too close to the same artist.

pncnmnp 3y ago
This is fantastic! I still need to carefully study it all, but I implemented the idea you described in the original comment. It seems the error lies somewhere between the algorithm I mentioned and the Fisher-Yates shuffle, based on one million playlists: Mean: 0.13, Median: 0.11, Mode: 0, p25: 0.06, p75: 0.18, p90: 0.26, p95: 0.31. It's possible I'm missing something here. Regarding your edit about 'picking any new random number as the stepsize,' wouldn't it be affected by a 'bad break,' as mentioned by Knuth? I still need to work out the 'bad break' proof. Edit: If it helps, here is the code I used to test it out - https://gist.github.com/pncnmnp/8afb7903f61ec69a157287435a6347aa https://gist.github.com/pncnmnp/8afb7903f61ec69a157287435a63...
- bazzargh 3y ago
  I don't have Knuth to hand...but yeah it is possible you can accidentally pick a number that is too close to a rational, so you get short repeats of tracks instead of long ones. What you're after is a number with a high approximation coefficient https://en.wikipedia.org/wiki/Liouville_number#Irrationality_measure https://en.wikipedia.org/wiki/Liouville_number#Irrationality... but in practice you just need to know that it is irrational "enough", eg you might want to avoid repeats in the first 1000 plays. You can get that by rejection sampling on the random number and using the Farey sequence to find nearby low-denominator fractions https://en.wikipedia.org/wiki/Farey_sequence#Applications https://en.wikipedia.org/wiki/Farey_sequence#Applications - if I pick a number between 0 and 1 I can use 0/1, 1/1 as the starting point for the usual iteration. (and then scale to .25,.75 at the end). You pick your approximation bound mu and reject if log(abs(p/q - x)) > - mu log q, repeat the farey iteration until q is large enough. (just making this up as I go on an ipad, I may have a sign wrong in there or whatever) It is actually much simpler than this ^ to just explicitly check the first 1000 numbers for a loop. It's simpler than tortoise and hare: you know there is no run-in, so the first number is in the loop, and you want that number to not reappear in the first min(N,1000) items.
HelloNurse 3y ago
The problem is separating tracks in the same group. If the globally sorted reference list of N songs has M consecutive entries that we want to spread evenly, they should be "shuffled" at increments of floor(N/M) or 1+floor(N/M): easy to guarantee with tortured recursive constructions like the one that opens the article, less obvious with a hash function that is affected by floating point approximations. An integer formula that is more obvious to work: starting from any number between the maximum group size and (if larger) N/phi, pick an increment D as the next larger or smaller integer that has no common factors with N (to ensure full period) and map index K to index (S+K*D)%N.
jameshart 3y ago
To avoid the fixed cycle problem, for each shuffle, choose a seed, then sort by hash(artist + seed) + hash(album + seed) instead of just artist + album before you start jumping through the list using fibonacci hashing. Album tracks and artists still end up colocated, but their position in the list is randomized.

pncnmnp 3y ago

This is fantastic! I still need to carefully study it all, but I implemented the idea you described in the original comment. It seems the error lies somewhere between the algorithm I mentioned and the Fisher-Yates shuffle, based on one million playlists: Mean: 0.13, Median: 0.11, Mode: 0, p25: 0.06, p75: 0.18, p90: 0.26, p95: 0.31. It's possible I'm missing something here. Regarding your edit about 'picking any new random number as the stepsize,' wouldn't it be affected by a 'bad break,' as mentioned by Knuth? I still need to work out the 'bad break' proof. Edit: If it helps, here is the code I used to test it out - https://gist.github.com/pncnmnp/8afb7903f61ec69a157287435a6347aa https://gist.github.com/pncnmnp/8afb7903f61ec69a157287435a63...

bazzargh 3y ago
I don't have Knuth to hand...but yeah it is possible you can accidentally pick a number that is too close to a rational, so you get short repeats of tracks instead of long ones. What you're after is a number with a high approximation coefficient https://en.wikipedia.org/wiki/Liouville_number#Irrationality_measure https://en.wikipedia.org/wiki/Liouville_number#Irrationality... but in practice you just need to know that it is irrational "enough", eg you might want to avoid repeats in the first 1000 plays. You can get that by rejection sampling on the random number and using the Farey sequence to find nearby low-denominator fractions https://en.wikipedia.org/wiki/Farey_sequence#Applications https://en.wikipedia.org/wiki/Farey_sequence#Applications - if I pick a number between 0 and 1 I can use 0/1, 1/1 as the starting point for the usual iteration. (and then scale to .25,.75 at the end). You pick your approximation bound mu and reject if log(abs(p/q - x)) > - mu log q, repeat the farey iteration until q is large enough. (just making this up as I go on an ipad, I may have a sign wrong in there or whatever) It is actually much simpler than this ^ to just explicitly check the first 1000 numbers for a loop. It's simpler than tortoise and hare: you know there is no run-in, so the first number is in the loop, and you want that number to not reappear in the first min(N,1000) items.

HelloNurse 3y ago

The problem is separating tracks in the same group. If the globally sorted reference list of N songs has M consecutive entries that we want to spread evenly, they should be "shuffled" at increments of floor(N/M) or 1+floor(N/M): easy to guarantee with tortured recursive constructions like the one that opens the article, less obvious with a hash function that is affected by floating point approximations. An integer formula that is more obvious to work: starting from any number between the maximum group size and (if larger) N/phi, pick an increment D as the next larger or smaller integer that has no common factors with N (to ensure full period) and map index K to index (S+K*D)%N.

jameshart 3y ago

To avoid the fixed cycle problem, for each shuffle, choose a seed, then sort by hash(artist + seed) + hash(album + seed) instead of just artist + album before you start jumping through the list using fibonacci hashing. Album tracks and artists still end up colocated, but their position in the list is randomized.