Hello,
Attached is a [list-quicksort] abstraction, which sorts lists of numbers using (you guessed it!) a quicksort algorithm... it should function as a drop-in replacement for the recent [list-*sort] abstractions, and it should be quite a bit faster than [list-sort], and faster than [list-shellsort] for lists of maybe 50 or more. It will not perform as well as [list-shellsort] for lists that have a ton of duplicates, and it uses more memory than the shellsort.
I believe there are faster sorting algorithms which begin with quicksort and then move to another kind of sort for short partitions or if the partitioning gets too deep, but I wanted to do a pure quicksort for simplicity.
Anything significantly faster would probably need an external, but like I said before I love this kind of thing just for the constrained problem solving, and for the pedagogical value for anyone who uses list-abs. I don't think we "need" a heapsort or anything else, but I'd be happy to put one together in a couple of weeks.
There were a few persistent bugs in this one that I think I've ironed out, but I'd like to have one or two people try to break it. =o)
Thanks,
Matt
Have you analysed (or measured) the asymptotic complexities of the implementations?
Note they may be different from the "standard" complexities [1] because of the non-optimal primitives [2] that Pd provides.
Claude
[1] http://en.wikipedia.org/wiki/Sorting_algorithms#List_of_sorting_algorithms
[2] eg: [list split 1] loop to implement [list-drip] would copy O(n^2) atoms
Matt Barber wrote:
Hello,
Attached is a [list-quicksort] abstraction, which sorts lists of numbers using (you guessed it!) a quicksort algorithm... it should function as a drop-in replacement for the recent [list-*sort] abstractions, and it should be quite a bit faster than [list-sort], and faster than [list-shellsort] for lists of maybe 50 or more. It will not perform as well as [list-shellsort] for lists that have a ton of duplicates, and it uses more memory than the shellsort.
I believe there are faster sorting algorithms which begin with quicksort and then move to another kind of sort for short partitions or if the partitioning gets too deep, but I wanted to do a pure quicksort for simplicity.
Anything significantly faster would probably need an external, but like I said before I love this kind of thing just for the constrained problem solving, and for the pedagogical value for anyone who uses list-abs. I don't think we "need" a heapsort or anything else, but I'd be happy to put one together in a couple of weeks.
There were a few persistent bugs in this one that I think I've ironed out, but I'd like to have one or two people try to break it. =o)
Thanks,
Matt
Right, this has been on my mind a lot. It would take me a while to figure this out, as I'm no Big-O expert. I have sometimes put in a few extra steps to make the code easier to read or to make it lie better spatially in the patch, but usually this is only something like an extra float store and I don't think that adds to the overall complexity. You're right, though -- filtering the non-floats is the costliest part of the operation (lists of 20000 members or so take about 3 times as long). But seriously who's gonna be using 20000-element lists in Pd practice?
If there were a vanilla equivalent of [iter], this would be a lot better. Attached is a [list-shellsort] and [list-quicksort] which do the filtering process as part of writing the table -- this cuts down time -- but unfortunately it removes the instructive use of [list-filter].
Matt
On Sat, Dec 6, 2008 at 12:07 PM, Claude Heiland-Allen claudiusmaximus@goto10.org wrote:
Have you analysed (or measured) the asymptotic complexities of the implementations?
Note they may be different from the "standard" complexities [1] because of the non-optimal primitives [2] that Pd provides.
Claude
[1] http://en.wikipedia.org/wiki/Sorting_algorithms#List_of_sorting_algorithms
[2] eg: [list split 1] loop to implement [list-drip] would copy O(n^2) atoms
Matt Barber wrote:
Hello,
Attached is a [list-quicksort] abstraction, which sorts lists of numbers using (you guessed it!) a quicksort algorithm... it should function as a drop-in replacement for the recent [list-*sort] abstractions, and it should be quite a bit faster than [list-sort], and faster than [list-shellsort] for lists of maybe 50 or more. It will not perform as well as [list-shellsort] for lists that have a ton of duplicates, and it uses more memory than the shellsort.
I believe there are faster sorting algorithms which begin with quicksort and then move to another kind of sort for short partitions or if the partitioning gets too deep, but I wanted to do a pure quicksort for simplicity.
Anything significantly faster would probably need an external, but like I said before I love this kind of thing just for the constrained problem solving, and for the pedagogical value for anyone who uses list-abs. I don't think we "need" a heapsort or anything else, but I'd be happy to put one together in a couple of weeks.
There were a few persistent bugs in this one that I think I've ironed out, but I'd like to have one or two people try to break it. =o)
Thanks,
Matt
Hallo, Matt Barber hat gesagt: // Matt Barber wrote:
If there were a vanilla equivalent of [iter], this would be a lot better. Attached is a [list-shellsort] and [list-quicksort] which do the filtering process as part of writing the table -- this cuts down time -- but unfortunately it removes the instructive use of [list-filter].
I think, what could be a good solution would be to factor out the table-sorting into separate objects. People who deal with long lists will probably store them in tables instead of lists anyway, and for list sorting, the objects could be a simple as:
[inlet] | [pd write-list-to-table] | [table-quicksort $0-table] | [pd dump-table-to-list] | [outlet]
Maybe there should be a [table]-abs collection as well? ;)
Ciao
Frank
-
Claude Heiland-Allen -
Frank Barknecht -
Matt Barber