9 ms·
A great application for this is in randomizing playlists. My friends, who are also CS grads and should know better, have often complained that their MP3 players
by ideonexus 9y ago
A great application for this is in randomizing playlists. My friends, who are also CS grads and should know better, have often complained that their MP3 players, CD carousels, etc play the same music too often claiming that the random is broken, when a song repeating in a short period of time or other songs never playing is what you would expect from a truly random selection. Using this algorithm, you'd be sure to hear all of your songs. I'm guessing most music services already do something like this.
- nxc18 9y agoI think the original Zune had a bad randomizer. In my experience it would tend to play two songs from the same artist back to back. Whether this was because they had a botched 'smart' randomizer or because they in fact used true random to shuffle, I may never know.
- abritinthebay 9y agoThe iPod and iTunes used to do this too - it’s because of a behavior you’d actually expect in a true randomizer called clustering. Supposedly Jobs specifically “fixed” this behavior and it’s why there used to be (still is?) a slider that allowed you to customize that behavior.
- drewrv 9y agoThis is also an example of users saying they want one thing (randomness) when really they want something else (variety).
- Sholmesy 9y agoBoth this and the GP are great lessons in software design.
- nkrisc 9y agoGreat example of finding what users really want as opposed to what they say they want.
- stubish 9y agoOr a great example of how things fail when producers and consumers don't use the same language. If you don't understand the language your consumers are speaking, you are not going to produce what they want. So next time some one tells you their computer is broken, don't reply saying it appears to be in one piece.
- Tarq0n 9y agoThis sounds like a giant strawman to me. Where do programmers get the idea that a mode called 'shuffle' would call for sampling with replacement? The obvious software analogy to shuffling would be re-ordering a list randomly, not randomly drawing from a list. I think this whole shuffling meme started with Spotify's engineers misunderstanding what they were asked to do, then claiming their customers don't know what they want when they obviously delivered the wrong feature.
- cestith 9y agoShuffle and weighted random both give a better chance of variety than truly random. Shuffle is cheaper to calculate in terms of storage space. The article is about weighting randomness based on past distribution. In a music playlist that may be enough. Some user might also want a term in the equation that weights songs they've rated highly to be favored over lower-rated or unrated songs.
- gpawl 9y ago"truly random" refers to how well a real distribution matches its intended distribution. So, a long cycle is not truly random, because many desired outcomes are physically possible to obtain. This is orthognal to the choice of distributon. Shuffle and Weighted Sampling are different choices of distribution.
- xg15 9y agoThis - and possibly also a reminder that the same words may mean different things for people with different backgrounds. If someone with no specialized knowledge about math and probability requests their songs in a "random" order, I don't think one should assume they are insisting on an order sampled from a uniform distribution.
- mulmen 9y ago"If I had asked people what they wanted, they would have said faster horses." - Henry Ford
- Jasper_ 9y agoBecause the casual definition of "random" means "without a discernible pattern", which multiple artists in a row doesn't handle. Music shuffle algorithms sometimes go lengths to avoid patterns and duplicate artists.
- michaelmcmillan 9y agoI actually tested the random distribution of Spotify's shuffle functionality: http://michaelmcmillan.net http://michaelmcmillan.net
- Jackim 9y agoI appreciate the simplicity of your site but it is definitely difficult to quickly see where one post ends and another one starts.
- RugnirViking 9y agoOn your website you put a source mark on the statement 'This is the same reason the Brits mistakenly assumed that the Germans had an exceptionally good aim with their V-1 flying bombs during World War II ' I'd like to read about this, do you still have the intended link?
- feider 9y agoThinking fast & slow by D.Kahneman mentioned this same story
- michaelmcmillan 9y agohttps://www.wired.com/2012/12/what-does-randomness-look-like/ https://www.wired.com/2012/12/what-does-randomness-look-like...
- wodenokoto 9y agoI have a theory that Spotify doesn't do random shuffling, but weighted shuffling, so that new items are more likely to be at the top of a shuffle (or maybe even popular items). I also believe that this will satisfy users better than true random shuffling. About your linked post: You don't test the randomness of the shuffling, you only test if a shuffled list contain one and only of each original item.
- c3534l 9y agoSpotify officially says it's not random.
- wodenokoto 9y agoIsn't this why most players do shuffling instead of random? This insures that no playlist item can be played twice in a row.
- laumars 9y agoMany music players have done this for a long time. In fact I believe that's part of the reason why they refer to that function as "shuffle" rather than "random"
- eterm 9y agoShuffle is too far the other way though, you don't get any duplicates until you've been through the whole playlist. 'Random' was better, especially when there were players that would play "random album" which was great. You're right that shuffle has been the standard for a long time, the last actual "random" for singles I remember was napster back when it was popular.
- SAI_Peregrinus 9y agoI usually use Foobar2000 in "shuffle albums" mode. It's a good compromise IMO.
- pkulak 9y agoBut even a pure shuffle isn't enough, since you're likely to get the same artist many times in a row, which bothers people.
- laumars 9y agoThat depends entirely on the implementation. There's no one rule for how developers should implement shuffle. When I was writing my in car entertainment system (it's not as good as it sounds!) the first metric that was shuffled was the artist, followed by weightings for albums.
- worldsayshi 9y agoI would expect a "dumb shuffle" to randomise the order of playing songs in the list but play each song once.
- c3534l 9y agoYou can take it too far, though. When I listen to Venetian Snares on Spotify, they only play some songs off of 3 albums, despite the fact that have about a dozen albums. If you're going to do that, tell people it's not actually random.
- jameshart 9y agoNot sure this works perfectly for playlists, because it's still possible for it to roll the same thing twice in a row - it's just less likely. Long ago I asked this related question on stackoverflow: https://stackoverflow.com/questions/5467174/how-to-implement-a-repeating-shuffle-thats-random-but-not-too-random https://stackoverflow.com/questions/5467174/how-to-implement... - it surprises me still that nobody has identified a classic algorithm for solving exactly this problem.
- corpMaverick 9y agoUsing the power of 2 idea that was recently posted here. Choose two random songs and play the one that was least recently played.
- bendykstra 9y agoOh, I really like this idea. I might go with a number greater than two though for the aesthetic reason that 25% of the time, you will select a song that has been played more recently than half of the playlist. With four, you'd be selecting something from the back half of the playlist more than 90% of the time.
- munificent 9y agoThis is called "sampling without replacement" and lines up with the physical intuition users have for taking a playlist where each song appears once, randomly reordering it, and then playing the entire playlist. https://en.wikipedia.org/wiki/Simple_random_sample https://en.wikipedia.org/wiki/Simple_random_sample
- BurningFrog 9y agoWith these dice it's still possible you get the same song twice in a row, just less so. A simpler system is picking a random song, but excluding the last 20 songs played.
- koolba 9y agoA simpler way that's guaranteed to not repeat a song till the entire set has been played is: Assuming you have N songs, pick a prime P such that N is not divisible by P. Then pick a random index I (0 <= I < N) to start from. The index of the next song is I' = MOD(I + P, N). This method has the advantage of being O(1) regardless of the size of the playlist. Another method is to pick a random key K and sort the entries of the playlist based on HMAC(SONG, K) (where SONG is the name or other identifier of the song). This has a number of interesting properties. For starters the playlist will be randomized (that's good). It will also keep it's overall order if a new song is added. The new song will get inserted based upon its HMAC. You can switch things up a bit by having K be a based on the current date. That way new songs will maintain their order and jumping to a track on a given day will continue the chain as before, but day to day you won't always hear the same tracks back to back.
- gpvos 9y agoThe prime method would mean that you would never hear some combinations of songs (for example, those who are an even number apart).
- Paul-ish 9y agoWouldn't all random methods with some reasonable number of bits of randomness (eg 256) be unable to create all permutations of a sufficiently long playlist. The number of permutations of the playlist would be greater than the number possible random seeds. Eg a playlist with 60 songs has more than 2^270 permutations.
- Cogito 9y agoThat's not true, at least for the even number apart example. The prime method will sample songs p apart from each other, and it's easy to find examples of N and p where p is even, for example N=5 p=2. More generally, this method works for any n that is co-prime with N, so N=5 n=4 works as well. There are lots of shufflings where subsequent songs are not separated by a constant amount, so your main point is true. There are many combinations of songs that you would never hear no matter which prime you picked. To quantify just how many takes a little bit of work. There are N! total shufflings possible. We know that there are N-1 or less numbers that are co-prime with N (you get N-1 when N is prime, less otherwise). For each number that is co-prime, we have N possible shufflings, each starting from a different point. This gives at most N(N-1) shufflings from the prime method (really the co-prime method). As a percentage of total shufflings, we know the upper bound from the co-prime method is N(N-1) / N! == 1/(N-2)!. This very quickly goes to 0. For the first few N, N % of shuffles 2 100.00000% 3 100.00000% 4 50.00000% 5 16.66667% 6 4.16667% 7 0.83333% 8 0.13889% 9 0.01984% 10 0.00248% 11 0.00028% 12 0.00003% 13 0.00000% So for any reasonable number of songs, we know that _most_ shufflings will not be found by the prime shuffling method.
- legohead 9y agoback when I used Winamp as my daily player, I was getting annoyed that its "shuffle" kept playing the same songs. and it would play the same songs in a row. so I would hear the songs C,A,F play. then the next day again the sequence would be C,A,F. over time, I would start hearing the melody of the next song before it even started playing. when I finally noticed this and realized that could only mean it's not actually random, I researched it, and found out that once you hit shuffle/random on Winamp, it shuffled the songs once and kept the sequence forever. and then as it turned out, Winamp actually had a setting to select a truly random song each time. all I needed to cure my madness was a checkbox!
- erikb 9y agoGood implementations actually don't make a random choice, but do a random sort and then play the whole list, then random sort again, then play again the whole list, etc. The only possible problem here is when the last song in one playthrough is the same as the first song in the next playthrough. But even that can be overcome by re-random-sorting the follow-up.
- nathan_f77 9y agoI had a few issues with Spotify doing this. I even saw a post where an engineer claimed it was all psychological, but I was definitely getting repeats when I had queued up a large amount of music (e.g. over 40 hours.) I think they only shuffle a certain percentage of the playlist and forget which songs have already been played after a while. I manually shuffle some playlists now. One nice thing about the desktop client is the clipboard integration. You can press cmd+a to highlight all the songs, cmd+c to copy, and then paste all the song URLs into a text editor. Then I used "permute lines" in Sublime Text to shuffle them, then cmd+c and cmd+v to paste the songs back into Spotify.
- mickronome 9y agoI probably have some details wrong, but according to Spotify's customer feedback site, there at least used to be a couple of issues with their shuffle. One, if I remember somewhat correctly, was that if the player was stopped/shutdown, it forgot the shuffle seed. This would essentially lead to a reshuffle, which would cause duplicate songs for songs played before the unintended reseeding.
- nathan_f77 9y agoOh ok, yeah that seems to line up with what I experienced. I think it was after closing my laptop, or switching between different devices. I might have to try it again.
- oe 9y agoOn mobile Spotify seems to heavily favor songs it has cached which results in the same songs being played every time a random playlist is started.
- gregmac 9y agoSeveral years ago I used to use a music service that had a bunch of sliders, something like: Favorites: Normal <----------> Very Frequently Artist: Liked only <-----------> Wide variety Prefer: Old <----Balanced----> New Popularity: Hits only <--------> Fringe It was great to be able to customize stations. I don't remember what service it was, but I think it did get purchased and folded into something else. This was a great way of tweaking the "randomization", and really gets into understanding what people want to hear. In my case, I had different stations/playlists customized in different ways.
- deleted 9y ago[deleted]
- xg15 9y ago> My friends, who are also CS grads and should know better... I know this is about being "technically correct" but I'd argue that even if you're pedantic and know the behavior of true randomness, the complaints are justified. First, "pick a song from a uniform distribution" is an implementation detail, not the use case. The use case is "pick songs in a pleasant, novel order". If the implementer chose to do this using uniform randomness, that's their descision. If that implementation does not fulfill the use case, it's a bug and also their responsibility. Second, the function is frequently called "shuffle" - so it even gives some hints about the implementation expected. No shuffling algorithm should ever result in duplicates. (except at the beginning and end of playlists)
- hammock 9y agoThe iTunes shuffle program is(was?) known buggy, where it's not actually random but will repeat the same order again and again.
- accountyaccount 9y agothey don't want a random playlist, they want all the music on the playlist played in a random order w/ no repeats
- deleted 9y ago[deleted]