On Sat, Mar 5, 2011 at 1:06 PM, Mathieu Bouchard matju@artengine.ca wrote:
On Fri, 4 Mar 2011, Matt Barber wrote:
This all sounds about right -- I made [list-shellsort] more as a pedagogical exercise for my students
So, what is that supposed to teach them ?
Right, well -- my students are almost all composers with very little experience with computers, except for maybe music engraving software. In our computer music program the emphasis has long been on "achieving musical results," and the technical training required to make this happen tends to be very hard for them. Many of them will look in books to find things that interest them, only to get scared by equations, block diagrams, bits of code, etc. They all get really excited about abstractions in Pd when it comes up, but they don't have any idea why or when to make them or use them. It's useful, then, to take concrete problems like sorting numbers, finding roots of quadratic equations, or making comb filters, for which there exist plenty of code or diagram examples, and "translate" them into Pd. At this level just getting from an analysis of the problem to "it works" takes a huge amount of time; analysis of time complexity would be way outside the scope of the course, unfortunately.
than as a model of speed or efficiency (I did a "quicksort" as well that didn't end up in list-abs).
How did you achieve the quicksort ?
Why didn't it end up in list-abs ?
Attached. It uses a table for all the partitioning, and uses until loops instead of the more classic recursion.
but then it uses fewer of the list abstractions and is less of an opportunity to show how the abstractions work "in action."
Don't you think that it would be better to show the list-abs for what they are good at, rather than for what they aren't ?
Yes, absolutely. Swapping numbers in a list is hard with vanilla tools (and I think [list-swap] could be improved considerably) -- my point was that the library seems to prefer using list operations all the way through, even if a table/array would be more efficient ultimately.
And it's a good reminder for how slow list manipulations can be.
Ah, yes. But note that [list split] is O(1), which is the cool thing about pd's lists.
one of the best exercises in constrained patching I've ever done, and fun for proving that some things are actually possible in vanilla that you think wouldn't be,
Yeah, people didn't think a pure-vanilla [list-drip] could be O(n) either. I made one and now it's the new [list-drip]. I didn't mean to actually encourage people to use list-abs though. I already had written [foreach] in C++ which is a lot easier to understand :
\class ForEach { \constructor () {} \decl 0 list (...) {for (int i=0; i<argc; i++) out0;} }; \end class {install("foreach",1,1);}
this basically just says : make a class that has an inlet 0 list method that takes every element and sends it through outlet 0. Then name this class [foreach] and make it have 1 inlet and 1 outlet.
Your [s2l] looked more desperate though. ;)
Yes, it was desperate. Desperate things happen quite often -- for instance when an audio chain has a number of if-then conditionals, if you don't want to use expr~ or externals you have to calculate all the sidechains and then choose among them arithmetically; there's no good way to avoid calculation of certain rare conditions (things that approach division by small numbers, e.g.) on a sample-by-sample basis.
Yet, I suspect that people go ahead and use [list-sort] all the time.
uh, who would do that ?
People who discover list-abs on their own and who then learn that there's a sort function in the library.
Matt