Scrambling eggs for Spotify with Knuth's Fibonacci hashing
pncnmnp.github.io
pncnmnp.github.io
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.
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/8afb7903f61ec69a157287435a63...
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 - 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.
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.
I want those non-repeating pattern tiles, how awful would those be to tile?
And yet, when Spotify's shit tier algorithm takes over, it kicks me into a similar 5 to 6 meme set of songs every single time. It's an absolute joke.
I can't tell if it's:
- Certain artists are paying Spotify to favor them in randomization?
- There's some kind of shared random seed across devices that results in picking a tiny subset of songs to randomize from in the first place?
- Other?
I do notice that the effect seems to persist for maybe a week, then I'll never hear those songs again, but now it'll be different songs that keep popping up repeatedly.
There's a related effect when you launch a radio station based on an artist or track. If you launch it multiple times in the same day or week, you get the exact same list of tracks. But maybe a week later the tracks have changed, like the radio has been recalculated based on a different random seed.
If you have 100 songs and listen to 1 song per day (which is 1% of the library), on any given day your odds of hearing the same song as yesterday are 1 in a 100.
If you have 1000 songs and listen to 10 per day (still 1%), the odds of hearing a song that was also played yesterday are a little less than 1 in 10, right?
So what matters is not only what fraction of your library's play time you sample daily, but also how finely subdivided the time is into individual tracks for sampling.
No. It's 10*(1/1000)=1%.
It'll happen a few times a year only.
It's 1%. Any specific song is 0.1%.
Assume that you got 10 unique songs yesterday, which is the case ~96% of the time. Then there are 990 songs you didn't hear yesterday, and for every song you listen to today, there is a 990/1000 chance that it's one of those songs. Hence the chance of only hearing new songs today is (990/1000)^10 = 90.4%.
I remember hearing of a bug where if you played on a remote device, it would transfer the first part of your playlist (10? 100 tracks?), and then shuffle would only choose from among them.
But it's been 5+ years so things may have changed and/or I could be remembering completely wrong.
When I still used Spotify, I would get a dozen of my favorite artists mixed into basically any "playlist" I pick. Was one of the reasons I quit Spotify - they are too opinionated on what I should listen to.
Clustering apparently ought to feel deliberate. Now think back to when you had actual DJs selecting tracks on the radio. One of the techniques was "Two from a particular band." Not two from a band with some tracks between them.
Similarly, one can do a "Four tracks from 1994" to provide a cluster in time, another technique I've heard.
If anything, the more metadata you have, the more you can provide short runs of something. Microgenres, for example.
Back then we had our music locally and we chose our own players, of which there were many and easy to make another one. Actually, hacking on music playback was easy and not uncommon. We had full control of our musical lives.
e.g. For classical music I’d prefer stringing together pieces from the same orchestra/composer. But for some contemporary music would like mix the artist/album up more.
"The user can use thumbs up and thumbs down buttons to declare whether they like a track or not, which determines whether similar songs should be played in the station.[40] A second thumbs down to the same artist will ban that artist from the selected station.[41] A thumbs down immediately skips a song, but the number of times a user can skip tracks is limited unless they are using one of the paid subscription plans, or opts to watch a video ad.[42][43] More than 450 musical attributes are considered when selecting the next song.[44] These 450 attributes are combined into larger groups called focus traits, of which there are 2,000.[45] Examples of these are rhythm syncopation, key tonality, and vocal harmonies.[45]"
But here's what I noticed when I went to the explore section of Instagram.
At display, there would be distinct choices of images and reels, varied and related to my interests. But if I select a particular reel/image type (e.g. animation or comics or 3d render), it would take that as a signal and would expand the feed based on that selection. I love that feature.
I guess Spotify Radio do that to some extent, not sure.
Great for a while, but then they complained that all the slow songs were bunched together. And perhaps the random shuffle play mode was sampling the songs, deriving the tempo of each, and adjusting the shuffle accordingly.
Very funny.
---
Heh-heh, I independently came up with Fibonacci hashing for color many years ago.
My web app was drawing a diagram of N rectangular items, color-coded to tell them apart, with a table listing the details of each below.
(Normally I would use EIA standard colors, with a nod to my EE brethren.)
But I didn't want the colors to bias anything. So you'd normally try random colors. But random colors can come out weird and some can be close together.
So I used a Golden Angle around the hue circle, with a constant brightness and saturation. And sure enough, the generated colors were nicely differentiated.
BUT... not as nice as I'd like. Something was wrong.
It turns out that our perception of color is more complex. And when we're differentiating between colors, it really, really helps if the colors are familiar, and describable.
So simple colors like blue and purple are much easier to differentiate than a new weird blueish color and a new weird purplish color.
So my Golden Angle colors were technically superior, but not as good a user experience.
So if you have a playlist with 10 songs A-J that you've listened to 10 times each. And then you add 10 new songs K-T that you've listened to 1 time each... Then every time I shuffle the playlist, I want songs K-T to be the first 10 songs in random order until I've played them 10 times each.
I mean, things can be mixed up a little more than that... but generally speaking, I want to listen to my least-listened songs much more than the ones I've been listening to forever. But I don't want to have to separate them out into special playlists "newest", "newer", "kinda new", "old", "oldest" which is annoying.
When I press the big green play button in a playlist's page, it tends to start playing from a specific song, in a weirdly familiar order. So I manually pick a song at random and let it play from there.
But even so, some songs almost never get played, but others get played fairly frequently.
Martin Fiedler briefly addresses this topic in a comment on his blog post about shuffling algorithms (https://keyj.emphy.de/balanced-shuffle/)
> Apple has a so-called “smart shuffle” algorithm, but this merely puts higher-rated tracks in front of lower-rated ones. So basically, it’s just random shuffle, followed by a sort-by-rating operation. I don’t know of any product (software or hardware) that uses some kind of smart, balanced or whatever-you-like-to-call-it shuffle based on the principles I described in the text.
I'm not sure what they are using today.
In this paper, they test different probability models to detect bias in iPod's shuffling algorithm and eventually conclude that:
> Our statistical tests show the long-term occurrences of these events are within expectations under the assumption of a random shuffle."
Regarding sorting by artists or groups, they found that:
> We failed to find any evidence to support the claim of users like Steven Levy of favoritism of certain groups in the shuffle.