Lampsort: Leslie Lamport's Non-recursive Quicksort
bertrandmeyer.com
Lampsort: Leslie Lamport's Non-recursive Quicksort
1–10 of 46 posts
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#2Where Quicksort uses the recursion stack to maintain the `intervals` implicitly, Lampsort instead uses some set data structure to maintain this set of subproblems explicitly.
It reminds me of the way you turn recursive depth-first search (recurse on children that have not been visited) into non-recursive depth-first search (push the children that have not been visited onto the DFS stack). Calling it "non-recursive" is a bit misleading, since you're trading recursion stack space for an actual data stack to maintain the recursion you are supposed to avoid -- but it is a useful program transformation to know.
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#3> His trick is to ask the audience to give a non-recursive version of Quicksort, and of course everyone starts trying to remove the recursion, for example by making the stack explicit or looking for invertible functions in calls. But his point is that recursion is not at all fundamental in Quicksort.
I'm not completely sure what distinction Meyer is trying to draw between the implementation he discusses, and "making the stack explicit". He ends up with a "set" of intervals that he pushes onto and pops from, which might as well have been a stack of arguments.
Is the point that the order you pull things out of the set doesn't matter, so demanding that it behave as a stack is overly prescriptive?
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#4require j >= a.upper seems wrong.
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#5First question was why anybody would present this using Eiffel. That's apparently answered at the bottom, but I still don't understand. Eiffel is good at being abstract or something? But isn't the code presented a concrete implementation of a single way to do things?
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#6Where Quicksort uses the recursion stack to maintain the `intervals` implicitly, Lampsort instead uses some set data structure to maintain this set of subproblems explicitly. It reminds me of the way you turn recursive depth-first search (recurse on children that have not been visited) into non-recursive depth-first search (push the children that have not been visited onto the DFS stack). Calling it "non-recursive" i…
There are ways to do a DFS of a tree without any sort of stack, though. This sounds more like a nitpick on stack vs set. You still have a data structure that grows in lg(n).
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#7Here's a Python version I quickly threw together, for people like me who don't know Eiffel:
https://gist.github.com/joelgrus/9dc47ebb22243fe990e5
I think it's right. :)
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#8If I understand the argument, the use of a set rather than a stack encodes the observation that the order of execution of adjacent partition operations isn't important. That ordering is information you don't have to store, meaning you can choose any set-like data structure, and being able to choose your access is theoretically useful: For example, by following a rule like "partition the smallest interval first", you could keep the set size ("depth") to a minimum. (That might be handy due to random pivot choice?) You don't have the freedom to choose that in a stack-backed implementation, whether recursive or "non".
So it is reasonable to argue this is a more abstract, "fundamental" implementation of the sort. Intuitively, I'm not sure it's that different from "remov[ing] the recursion, for example by making the stack explicit", then removing the stack, but it's sure interesting.
Edit: See https://news.ycombinator.com/item?id=8713160 for more context; this is correct, but the point is not really about how the code works.
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#9Is this a useful thing to implement as a parallel algorithm, or would I be better of just using mergesort as my choice?
Re: Lampsort: Leslie Lamport's Non-recursive Quicksort
#10First question was why anybody would present this using Eiffel. That's apparently answered at the bottom, but I still don't understand. Eiffel is good at being abstract or something? But isn't the code presented a concrete implementation of a single way to do things?
I think it probably has a lot to do with the fact that the author, Bertrand Meyer, invented Eiffel (http://en.wikipedia.org/wiki/Bertrand_Meyer#Computer_languag...).