Musical sorting algorithms
August 21, 2009 6:17 AM Subscribe
This strums the strings of my music nerd heart... thanks.
posted by baxter_ilion at 7:54 AM on August 21, 2009
posted by baxter_ilion at 7:54 AM on August 21, 2009
The intersection of maths, coding and music... If you could find a way of introducing Buffy, you'd have the perfect quadfecta of my interests! Thanks for this!
posted by benzo8 at 8:02 AM on August 21, 2009
posted by benzo8 at 8:02 AM on August 21, 2009
sleevener: "3) MIDI hurts my soul through my ears."
Why? MIDI is a description language for music, that's all. It doesn't sound like anything - it's totally independent of sound sources...
posted by benzo8 at 8:06 AM on August 21, 2009
Why? MIDI is a description language for music, that's all. It doesn't sound like anything - it's totally independent of sound sources...
posted by benzo8 at 8:06 AM on August 21, 2009
Why? MIDI is a description language for music, that's all. It doesn't sound like anything - it's totally independent of sound sources...
That's sort of like saying that mp3 is a file format and doesn't sound like anything, right? But of course one can hear the difference between an mp3 and a vinyl record, for example. MIDI renditions of pieces tend to sound stilted (to me, anyway), because there's no variety or flexibility in the sound -- an A# always sounds exactly the same, a given cymbal crash always sounds exactly the same. Maybe there's a more nuanced and flexible way to use it, but I've never heard it.
A lot of composers will work up MIDI renditions of their pieces before they've found a musician to play them. My wife's a pianist and we listen to a lot of new pieces together, some in MIDI and some performed by a human pianist; it's nearly impossible to hear the piece if it's in MIDI. If MIDI was a font, it would be Courier.
posted by sleevener at 8:26 AM on August 21, 2009 [1 favorite]
That's sort of like saying that mp3 is a file format and doesn't sound like anything, right? But of course one can hear the difference between an mp3 and a vinyl record, for example. MIDI renditions of pieces tend to sound stilted (to me, anyway), because there's no variety or flexibility in the sound -- an A# always sounds exactly the same, a given cymbal crash always sounds exactly the same. Maybe there's a more nuanced and flexible way to use it, but I've never heard it.
A lot of composers will work up MIDI renditions of their pieces before they've found a musician to play them. My wife's a pianist and we listen to a lot of new pieces together, some in MIDI and some performed by a human pianist; it's nearly impossible to hear the piece if it's in MIDI. If MIDI was a font, it would be Courier.
posted by sleevener at 8:26 AM on August 21, 2009 [1 favorite]
Neat idea. But it doesn't really explain how sorts work as well as watching a sorting animation.
posted by Nelson at 8:43 AM on August 21, 2009
posted by Nelson at 8:43 AM on August 21, 2009
sleevener: "That's sort of like saying that mp3 is a file format and doesn't sound like anything, right?"
No. It's nothing like saying that. MP3 is a compression algorithm, applied to a recording. MIDI may be a description of that recording, but it hasn't been played yet.
MIDI is the score, MP3 is the vinyl. MIDI has no sound. Hold up a score, put it really close to your ear - hear that? No, of course you don't.
sleevener: "MIDI renditions of pieces tend to sound stilted (to me, anyway), because there's no variety or flexibility in the sound -- an A# always sounds exactly the same, a given cymbal crash always sounds exactly the same. Maybe there's a more nuanced and flexible way to use it, but I've never heard it."
This is, because as you rightly surmise, you don't know what you're talking about. You're still conflating MIDI with sound.
If you gave the aforementioned score to a pianist, it would sound one way. If you gave it to an orchestra, it would sound different. The MIDI hasn't changed. The sound source has changed.
These days, you can buy a sample set for orchestral sounds which weighs in in the multi-hundred gigabytes of data. It contains countless phrasing and playing variations for every note, at every volume, on every instrument. A capable sampler like Native Intrument's Kontakt will play two slightly different samples if two consecutive notes are the same (this is called Round Robin Recording, btw). Different volumes (velocities) will play different sounds. Notes at the end of a phrase will us a different sample; with key-switching you can play vibrato, staccato, whichever -ato you want. You can make it sound beautiful and realistic.
But these are all about the sound source, and none of it is about the MIDI. Which is no different from the MIDI you might run through the Microsoft GM Softsynth, and which then would, indeed, sound crappy.
sleevener: "A lot of composers will work up MIDI renditions of their pieces before they've found a musician to play them. My wife's a pianist and we listen to a lot of new pieces together, some in MIDI and some performed by a human pianist; it's nearly impossible to hear the piece if it's in MIDI. If MIDI was a font, it would be Courier."
But this is the point. MIDI isn't a font. It's a text document. It has no font until you use something to view it. If you choose to view it in using Courier, then it'll look like Courier. But if you view it in something else, it'll sound like something else...
posted by benzo8 at 8:57 AM on August 21, 2009 [7 favorites]
No. It's nothing like saying that. MP3 is a compression algorithm, applied to a recording. MIDI may be a description of that recording, but it hasn't been played yet.
MIDI is the score, MP3 is the vinyl. MIDI has no sound. Hold up a score, put it really close to your ear - hear that? No, of course you don't.
sleevener: "MIDI renditions of pieces tend to sound stilted (to me, anyway), because there's no variety or flexibility in the sound -- an A# always sounds exactly the same, a given cymbal crash always sounds exactly the same. Maybe there's a more nuanced and flexible way to use it, but I've never heard it."
This is, because as you rightly surmise, you don't know what you're talking about. You're still conflating MIDI with sound.
If you gave the aforementioned score to a pianist, it would sound one way. If you gave it to an orchestra, it would sound different. The MIDI hasn't changed. The sound source has changed.
These days, you can buy a sample set for orchestral sounds which weighs in in the multi-hundred gigabytes of data. It contains countless phrasing and playing variations for every note, at every volume, on every instrument. A capable sampler like Native Intrument's Kontakt will play two slightly different samples if two consecutive notes are the same (this is called Round Robin Recording, btw). Different volumes (velocities) will play different sounds. Notes at the end of a phrase will us a different sample; with key-switching you can play vibrato, staccato, whichever -ato you want. You can make it sound beautiful and realistic.
But these are all about the sound source, and none of it is about the MIDI. Which is no different from the MIDI you might run through the Microsoft GM Softsynth, and which then would, indeed, sound crappy.
sleevener: "A lot of composers will work up MIDI renditions of their pieces before they've found a musician to play them. My wife's a pianist and we listen to a lot of new pieces together, some in MIDI and some performed by a human pianist; it's nearly impossible to hear the piece if it's in MIDI. If MIDI was a font, it would be Courier."
But this is the point. MIDI isn't a font. It's a text document. It has no font until you use something to view it. If you choose to view it in using Courier, then it'll look like Courier. But if you view it in something else, it'll sound like something else...
posted by benzo8 at 8:57 AM on August 21, 2009 [7 favorites]
I don't fully understand the point for this, but I see why he didn't do selection sort.
posted by demiurge at 9:15 AM on August 21, 2009
posted by demiurge at 9:15 AM on August 21, 2009
I like MIDI because, for the cost of GarageBand and a $125 MIDI keyboard, I now have an orchestra, instead of the toy instruments I was using beforehand. Does it sound precisely like an actual grand piano or horn section? No, but, then, the kazoo I was playing earlier didn't sound much like a trumpet either.
MIDI has vastly increased the palette of sounds I can work with, and for very little expense. If the results offend sound snobs, well, they can pitch in to buy me the Philharmonic.
posted by Astro Zombie at 9:22 AM on August 21, 2009
MIDI has vastly increased the palette of sounds I can work with, and for very little expense. If the results offend sound snobs, well, they can pitch in to buy me the Philharmonic.
posted by Astro Zombie at 9:22 AM on August 21, 2009
Benzo8 or you could have simply realized by saying "midi hurts soul through my ears" that Sleevener meant that he hated the sound of General Midi as most people do when they mention the "sound of midi" and saved yourself a half an hour of your day and the embarrassment of making analogies as poor as "mp3 is the vinyl"
posted by phidelity at 9:27 AM on August 21, 2009 [1 favorite]
posted by phidelity at 9:27 AM on August 21, 2009 [1 favorite]
(getting away from the tangential MIDI discussion)
Ok.. I think this is beautiful. And here's why..
To a human being, repeating patterns are as boring as pure randomness. On one hand, there isn't any new information. On the other, there's very little information in a (pseudo) random signal. But, what we DO like, is flirtations between both ends of that spectrum. For a good example of this: http://www.youtube.com/watch?v=wgaD54YcXpA
In all of these algorithms there is interplay between randomness and patterns, approaching complete predictability as it becomes more sorted. There are some really nice patterns in the middle, where it's kind of random, and kind of boring.
You could say that this is the core of music: keeping things just predictable enough to still surprise you. But, I'm not a scholar on this type of thing, so I'll shut up now. :)
posted by hanoixan at 9:40 AM on August 21, 2009 [3 favorites]
Ok.. I think this is beautiful. And here's why..
To a human being, repeating patterns are as boring as pure randomness. On one hand, there isn't any new information. On the other, there's very little information in a (pseudo) random signal. But, what we DO like, is flirtations between both ends of that spectrum. For a good example of this: http://www.youtube.com/watch?v=wgaD54YcXpA
In all of these algorithms there is interplay between randomness and patterns, approaching complete predictability as it becomes more sorted. There are some really nice patterns in the middle, where it's kind of random, and kind of boring.
You could say that this is the core of music: keeping things just predictable enough to still surprise you. But, I'm not a scholar on this type of thing, so I'll shut up now. :)
posted by hanoixan at 9:40 AM on August 21, 2009 [3 favorites]
Benzo8 or you could have simply realized by saying "midi hurts soul through my ears" that Sleevener meant that he hated the sound of General Midi as most people do when they mention the "sound of midi" and saved yourself a half an hour of your day and the embarrassment of making analogies as poor as "mp3 is the vinyl"
Yeah, I would've preferred that too.
posted by sleevener at 10:55 AM on August 21, 2009
Yeah, I would've preferred that too.
posted by sleevener at 10:55 AM on August 21, 2009
your favourite sorting algorithm sucks
posted by yoHighness at 11:19 AM on August 21, 2009 [2 favorites]
posted by yoHighness at 11:19 AM on August 21, 2009 [2 favorites]
Dunno, it was pretty clear to me that sleevener simply didn't understand what the difference between MIDI and and audio format is. He also didn't notice that there's no MIDI involved in this post.
I'm annoyed that it's an insertion sort with linear search. Who does that?
posted by hattifattener at 11:47 AM on August 21, 2009
I'm annoyed that it's an insertion sort with linear search. Who does that?
posted by hattifattener at 11:47 AM on August 21, 2009
no MIDI involved in this post.
hattifattener, you're right, I didn't notice that. And, you're also right that I don't (or didn't) understand the difference between MIDI and an audio format. I don't really know anything about search algorithms either. Looks like this was the wrong post for me to comment in!
benzo8, thanks for your explanation. I take back what I said before, I'm glad you straightened me out.
posted by sleevener at 12:02 PM on August 21, 2009
hattifattener, you're right, I didn't notice that. And, you're also right that I don't (or didn't) understand the difference between MIDI and an audio format. I don't really know anything about search algorithms either. Looks like this was the wrong post for me to comment in!
benzo8, thanks for your explanation. I take back what I said before, I'm glad you straightened me out.
posted by sleevener at 12:02 PM on August 21, 2009
Dude! Did you see Insertion Sort in concert? He was rockin' the skins, man!
posted by chairface at 12:11 PM on August 21, 2009 [1 favorite]
posted by chairface at 12:11 PM on August 21, 2009 [1 favorite]
If MIDI was a font, it would be Courier.
I know that benzo8 already hammered this nail to death, but let me simply point out that there is the concept of a soundfont:
posted by pwnguin at 1:28 PM on August 21, 2009
I know that benzo8 already hammered this nail to death, but let me simply point out that there is the concept of a soundfont:
SoundFont banks are tightly integrated with MIDI devices and can be seamlessly used in place of General MIDI (GM) patches in many computer music sequencersIf your MIDIs all sound like Courier, its because the only font you have installed is Courier. That said, the MIDI spec is pretty crazy on letting you specify articulation, far beyond the normal score would.
posted by pwnguin at 1:28 PM on August 21, 2009
I'm annoyed that it's an insertion sort with linear search. Who does that?
Me.
Yes, the region you're sorting is already ordered, and that would indeed allow you to use a binary search to find where your next value should be inserted; but once you've found that position, you still need to shuffle everything beyond it along one spot in order to perform the actual insertion. It costs so little to examine the things you're shuffling as you're actually shuffling them that in general an initial binary-search step doesn't pay off - especially if you're using insertion sort for the purpose God made it: as the final cleanup step after a partial Quicksort.
Quicksort is nifty and neat, but using it for sorting lists shorter than about 7 elements is generally slower than doing the same job with the simplest possible insertion sort, purely because of loop setup and function call overheads. The same applies to the sub-lists that QS ends up processing as it recurses. It's best simply not to recurse once the sub-list length is shorter than about 7 elements (so the QS terminates with a mostly-sorted rather than a fully-sorted list) and then do a single simple IS pass over the entire list to finish things off.
In this case, the IS will never have to move any list item more than 6 places regardless of the list size. For any decent size list it will run in something very close to linear time, and it will cause rather less function call and loop control overhead than a bunch of small sorts called in the bottom level of QS recursion.
For example, consider a final IS pass like this being performed on a 10,000 element list. If you're using a simple linear search-as-you-move inside the IS, you will never need to examine more than 6 elements to find the correct position for each element you're trying to insert. In the worst case, you'd need to do (1+2+3+4+5+6)/7*10000 = 30000 comparisons and moves.
With a binary search included, you'd need closer to (sum for i = 1 to 10000 of log2 i) = well over 100000 comparisons, and you'd still need your 30000 moves.
posted by flabdablet at 6:24 AM on August 22, 2009 [2 favorites]
Me.
Yes, the region you're sorting is already ordered, and that would indeed allow you to use a binary search to find where your next value should be inserted; but once you've found that position, you still need to shuffle everything beyond it along one spot in order to perform the actual insertion. It costs so little to examine the things you're shuffling as you're actually shuffling them that in general an initial binary-search step doesn't pay off - especially if you're using insertion sort for the purpose God made it: as the final cleanup step after a partial Quicksort.
Quicksort is nifty and neat, but using it for sorting lists shorter than about 7 elements is generally slower than doing the same job with the simplest possible insertion sort, purely because of loop setup and function call overheads. The same applies to the sub-lists that QS ends up processing as it recurses. It's best simply not to recurse once the sub-list length is shorter than about 7 elements (so the QS terminates with a mostly-sorted rather than a fully-sorted list) and then do a single simple IS pass over the entire list to finish things off.
In this case, the IS will never have to move any list item more than 6 places regardless of the list size. For any decent size list it will run in something very close to linear time, and it will cause rather less function call and loop control overhead than a bunch of small sorts called in the bottom level of QS recursion.
For example, consider a final IS pass like this being performed on a 10,000 element list. If you're using a simple linear search-as-you-move inside the IS, you will never need to examine more than 6 elements to find the correct position for each element you're trying to insert. In the worst case, you'd need to do (1+2+3+4+5+6)/7*10000 = 30000 comparisons and moves.
With a binary search included, you'd need closer to (sum for i = 1 to 10000 of log2 i) = well over 100000 comparisons, and you'd still need your 30000 moves.
posted by flabdablet at 6:24 AM on August 22, 2009 [2 favorites]
I swear, you people make things too damn complicated. Just use mergesort and be done with it. Simple, in-place, and won't go terribly, terribly wrong when the user clicks on the column header to reverse the sort ordering.
posted by pwnguin at 1:26 PM on August 22, 2009
posted by pwnguin at 1:26 PM on August 22, 2009
Posts on sorting like this one warm my geeky little heart, just like this other one from April did.
posted by JibberJabber at 6:32 PM on August 22, 2009
posted by JibberJabber at 6:32 PM on August 22, 2009
Hmm. Good points, flabdablet, but on the other hand, if you know that you're doing a cleanup sort, then that log2 should really only be over the 7 elements you know are possible insertion locations. Which puts the number of comparisons at about the same number as for a linear search (but if you were doing 16 elements, the binary search would start coming out ahead, of course).
In almost every case I deal with, comparisons are much more expensive than moves, both in terms of code executed and memory touched. Doing a block-move of a bunch of elements once I find the right location for an insertion is probably cheaper than doing pairwise swaps, too.
I took the code from rcompton's website and coded up a binary insertion sort video— if you avoid making unnecessary moves, it's really hard to tell what's doing on in the video, so the video version ends up shifting whole blocks back and forth just to show you the locations it's considering.
I also made some audio and visual rendering changes, so here's the linear insertion sort again for comparison.
(Links are coralized because they're on a dsl connection, and I think the video encoder I used is a little wonky somehow, but eh. If it doesn't play in your browser try downloading and playing from a file.)
posted by hattifattener at 9:26 PM on August 22, 2009
In almost every case I deal with, comparisons are much more expensive than moves, both in terms of code executed and memory touched. Doing a block-move of a bunch of elements once I find the right location for an insertion is probably cheaper than doing pairwise swaps, too.
I took the code from rcompton's website and coded up a binary insertion sort video— if you avoid making unnecessary moves, it's really hard to tell what's doing on in the video, so the video version ends up shifting whole blocks back and forth just to show you the locations it's considering.
I also made some audio and visual rendering changes, so here's the linear insertion sort again for comparison.
(Links are coralized because they're on a dsl connection, and I think the video encoder I used is a little wonky somehow, but eh. If it doesn't play in your browser try downloading and playing from a file.)
posted by hattifattener at 9:26 PM on August 22, 2009
Doing a block-move of a bunch of elements once I find the right location for an insertion is probably cheaper than doing pairwise swaps, too
If you code an IS properly, you don't end up doing pairwise swaps. You load the element you want to insert into a register, then enter a loop where you compare it with the previous element, then simply copy that element up one spot if the comparison says you have to. It's very nearly as fast as a block move.
if you know that you're doing a cleanup sort, then that log2 should really only be over the 7 elements you know are possible insertion locations. Which puts the number of comparisons at about the same number as for a linear search
only with rather more control-flow overhead. Also, if you know you're doing a cleanup sort then you can simply unroll the IS inner loop and make it faster still.
(but if you were doing 16 elements, the binary search would start coming out ahead, of course).
If you were doing 16 elements on a cleanup sort, you should probably have been going in a little harder with QS beforehand :-)
I take your point that in some cases, compares are expensive and moves are cheap. But in those cases, you really want to be using an algorithm like QS or merge sort that minimizes both, rather than trying to bolt algorithmic tweaks onto an IS.
posted by flabdablet at 10:59 PM on August 22, 2009
If you code an IS properly, you don't end up doing pairwise swaps. You load the element you want to insert into a register, then enter a loop where you compare it with the previous element, then simply copy that element up one spot if the comparison says you have to. It's very nearly as fast as a block move.
if you know that you're doing a cleanup sort, then that log2 should really only be over the 7 elements you know are possible insertion locations. Which puts the number of comparisons at about the same number as for a linear search
only with rather more control-flow overhead. Also, if you know you're doing a cleanup sort then you can simply unroll the IS inner loop and make it faster still.
(but if you were doing 16 elements, the binary search would start coming out ahead, of course).
If you were doing 16 elements on a cleanup sort, you should probably have been going in a little harder with QS beforehand :-)
I take your point that in some cases, compares are expensive and moves are cheap. But in those cases, you really want to be using an algorithm like QS or merge sort that minimizes both, rather than trying to bolt algorithmic tweaks onto an IS.
posted by flabdablet at 10:59 PM on August 22, 2009
« Older Science Fiction VS Scifi | Fashion backward Newer »
This thread has been archived and is closed to new comments
1) This is awesome
2) No bogosort?
3) MIDI hurts my soul through my ears.
posted by sleevener at 6:48 AM on August 21, 2009 [1 favorite]