Lampsort: Leslie Lamport's Non-recursive Quicksort

http://bertrandmeyer.com/2014/12/07/lampsort/

by mpweiher • 12 years ago

93 44 12 years ago

rav• 12 years ago

Where 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.

taeric4• 12 years ago

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).

hyt7u2• 12 years ago

There are ways to do a DFS of a tree without any sort of stack, though

What do you mean by this? You need a way to say that the unexplored nodes we've most recently found are the ones we explore first. How do you do that (with constant time operations) without what's effectively a stack?

jwmerrill• 12 years ago

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?

bkirwi• 12 years ago

Yes, that's the principal idea, I think -- separating out the implementation details from the actual conditions that are necessary for correctness. IIRC, I've seen another presentation of this where the author used that freedom to implement a work-stealing quicksort across multiple threads.

Cushman2• 12 years ago

Watching the source lecture[0], it's not about how the code is written so much as how the function is specified. It's easier to describe quicksort as a few set equations without invoking the concept of recursion, but since we don't write code like that people can't get to it easily.

The nuts-and-bolts difference is in fact that it's a set and not a stack, but the underlying question is, why do we all treat the set implementation as the derived version?

[0] http://channel9.msdn.com/Events/Build/2014/3-642 ~35m

badubu• 12 years ago

but since we don't write code like that people can't get to it easily

which likely sums up what Lamport is trying to get across - express your work equationally, determine properties and generally understand what you're dealing with and then later, you can 'compile your equations' down to a particular implementation. from my own practice, i've found that it is much easier to reason about equations and reflect it down into code than to try and reason about the code

TheLoneWolfling4• 12 years ago

since we don't write code like that people can't get to it easily.

I've lately been trying to write code with no recursion - as in able to be implemented with each function having a variable indicating where to return to, no implicit stack in sight. (Statically-determinable stack size, to put it another way.)

It took me a bit to get the hang of, but I'd argue that it ends up being easier in the long run. Far easier to change the priority operator on your queue than trying to reason what behavior different orders of recursion get you, for example.

Ditto with graph search algorithms. It's enlightening to teach graph search algorithms as a single algorithm with a queue, where changing the priority gives you Dijkstra's algorithm (least cost first), DFS (LIFO), BFS (FIFO), A* (current cost + underestimating huristic of cost left), or whatever. Also easy to show that A* degenerates into Dijkstra's algorithm when you use a null heuristic (i.e. a heuristic that returns a constant) if you teach them as variants of the same algorithm.

TheLoneWolfling4• 12 years ago

I think so.

Of course, you can make the same point about many other algorithms - graph search, for example.

The nice thing about showing that arbitrary orderings still work is that you can, for example, do parallel sorting with work-stealing, where each thread tries to grab the smallest interval from its working set at each iteration (to minimize space requirements and to improve cache locality), but other threads try to grab the largest interval possible (to reduce the amount of locking as much as possible).

lambda• 12 years ago

  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?

Right. In fact, there are several parts of the algorithm that are not really fundamental; one is how you pick the pivot, and another is how you perform the partitioning (ensuring that all elements before the pivot are less and all elements after are greater).

Lamport's point is that if you look at the fundamentals of the quicksort algorithm, which are that you must pick a pivot, partition such that smaller values come before and larger values come after, and then at some point later apply the same two steps to the two intervals [start, pivot) and (pivot, end].

Any algorithm that follows that specification will correctly sort the array, and then you can tweak exactly how you do that depending on your constraints. You could do it recursively, you could do it iteratively, you could divide it up into separate threads until you have one thread per processor each of which does the recursive or iterative algorithm on a private work list, you could do a worker pool in which each worker takes intervals from the set of remaining intervals to sort, etc. And likewise, you can tweak how you pick the pivot (picking the first element in the array is usually a bad idea, as it gives worst case behavior for already sorted arrays), and tweak how you perform the partitioning.

Anyhow, he didn't go into this kind of detail, he just pointed out that thinking about the fundamental specification can help get you away from the details of a particular implementation.

danbruc• 12 years ago

require j >= a.upper seems wrong.

tedunangst3• 12 years ago

First 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?

jerluc• 12 years ago

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...).

vram222• 12 years ago

Eiffel is considered by some people to be one of the better programming languages (maybe even near the top of the heap, though of course a lot depends on application area you are using it for, just as with any other language). Features in it may have influenced other languages. Not sure, but I think Design by Contract is one of them - preconditions, postconditions and invariants, which can be implemented somewhat, using assertions, in languages that provide assertions. But Eiffel provides language support for them. Search for some Eiffel success stories. There was one very good one - I don't have the link right now - about someone at Hewlett Packard using it to develop software for printers, maybe a device driver, after earlier attempts using other languages turned out to have many problems - IIRC.

Edit: after a quick search, I found an article that is about the same story, of HP using Eiffel - though I don't think it is the same article I read a while ago:

https://archive.eiffel.com/eiffel/projects/hp/creel.html

From the article:

``Eiffel is the perfect embedded language...'': an interview of Christopher Creel, HP CCD (Color laserjet and Consumables Division) How HP used ISE Eiffel to develop leading-edge printer software, used Design by Contract to preserve the work of its best designers, and in the process found bugs in its legacy software, discovered a flaw in a hardware chip, and learned a few lessons -- such as how to do in weeks what used to require months.

I've used design by contract principles (in C) in a successful middleware software that I was the team leader for, ensured (pun intended :) that my team used it extensively in the code, and the end result met its goals and was somewhat widely used in projects by the company where it was developed.

Edit 2: Bertrand Meyer is also the author of a very well-known and respected book, Object Oriented Software Construction. It's a big book. I read a lot of it, some years ago. It has some very good points in it. Bertrand Meyer is one person who seems to have thought and done a great deal about the process of software development (with a view to getting better results), on many levels, from theory through practice to industrial application.

http://en.wikipedia.org/wiki/Bertrand_Meyer

http://en.wikipedia.org/wiki/Object-Oriented_Software_Constr...

joelgrus• 12 years ago

Here'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. :)

Cushman2• 12 years ago

If 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.

tedunangst3• 12 years ago

"Smallest interval first" is exactly what naive recursion gives you.

TheLoneWolfling4• 12 years ago

Not quite.

Naive recursion doesn't generally change the order between the two subproblems at a single stage. It's generally just sort(first half), sort(second half).

Think of the case of a really bad pivot as the first choice - say, the second-highest element. Naive recursion generally will recurse on the lower chunk first, whereas smallest chunk first will recurse on the higher chunk.

ultimape• 12 years ago

Is this a useful thing to implement as a parallel algorithm, or would I be better of just using mergesort as my choice?

oggy• 12 years ago

Formal specification languages look remarkably like programming languages; to be usable for significant applications they must meet the same challenges: defining a coherent type system...

Lamport disagreed with this statement before [1], wonder what he'd say nowadays (he's been known to change his mind). Gossip warning: Lamport gave a talk at Meyer's university a few years back, bashing OOP. Meyer's a huge OOP proponent.

[1] http://research.microsoft.com/en-us/um/people/lamport/pubs/l...

ape4• 12 years ago

How does it compare speed-wise?

yason2• 12 years ago

I hiss at the term "non-recursive quicksort" which is used a lot. Quicksort per definition is recursive logically. The same computation recurs in the subarrays, you know.

Whether you maintain the state by using the programming language's own stack, a separate stack, a queue, or some other data structure either implicitly or explicitly is a matter of implementation. The amount of space you need to allocate for the program state as a function of the size of the input is the same regardless.

In a high level enough language it doesn't matter because you are to encode, in that language, your intent to apply the same process again and again to the subpartitions until everything is sorted, and a sufficiently smart compiler could choose any implementation that best suits the underlying hardware.

mpweiher• 12 years ago

"The same computation recurs"

Hmm...you mean like in a loop?

yason2• 12 years ago

Nope.

You can run, for example, bubble sort or insertion sort in a loop, always iterating over the same set of data (with some fixed amount of state) until the array is sorted.

Conversely and per definition, quicksort divides the data flow into subarrays and then sub-subarrays recursively which means that a plain single loop with constant space for state won't do. You need extra space for storing state and the amount of that extra space needed depends on the size of the input; logarithmically, in quicksort's case.

The implementation of recursion can vary but the control and data flow still does recur in a nested fashion.

truantbuick• 12 years ago

I'm not sure I agree with the idea that this somehow characterizes the idea of quicksort better.

Technically, you can always convert a recursive algorithm to iterative and back again (and not just with existence arguments -- it can be generally constructed), so why pick on quicksort specifically?

The only thing achieved here is putting the partitioning of the list and sorting in two separable parts. Whether that characterizes quicksort any better is a matter of opinion, I reckon.

bluecalm• 12 years ago

I am not sure what's the point is. It's still recursion it just bypasses using frame pointer and simulates its own. Here with set but stack is customary way to do that.

The idea isn't new either. Link to C implementation of quicksort without function calls: http://www.ucw.cz/libucw/#what (simple implementations is in array-simple.h). This implementation is very similar to the one in the article and is way (in my experience often more than 2x) faster than qsort or std::qsort so worth taking a look at.

lisper3• 12 years ago

TL;DR: if you have an algorithm that makes two recursive calls and it doesn't matter what order you do them in (e.g. Quicksort) then you can rewrite that algorithm to use a set of sub-problems in stead of a stack of sub-problems. The latter is what you (implicitly) get when you write an algorithm recursively.

A much more interesting observation would have been to note that you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter. That would allow a compiler to automatically produce code that used a set-of-intervals data structure, or -- much more relevant in today's world -- code that used multiple cores. (But that would have defeated the real purpose of the article, which was to be a tacit plug for Eiffel, which doesn't have such a construct.)

theoh2• 12 years ago

That's a good observation. It should go without saying that recursion can always be expressed iteratively. Lamport is inclined to make observations like this, e.g. his sequential consistency concept which states that concurrency is always equivalent to a serial process. But don't you mean "multiple recursive calls", not specifically two?

lisper3• 12 years ago

But don't you mean "multiple recursive calls", not specifically two?

Yes, of course.

Exercise for the non-lazy lurker: can you generalize the Quicksort algorithm based on this? Is there any benefit to doing so?

fiatmoney• 12 years ago

"you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter"

Effectively, this is what Golang's "go" construct does. Combined with channels you can construct an arbitrary dependency graph as well.

pacala• 12 years ago

A very common need is to do an bunch of independent RPCs. Small wish: Allow returning values from a goroutine, along the lines of "results <- go rpc(args)".

sorbits• 12 years ago

A much more interesting observation would have been to note that you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter

This would be the case for a pure function: http://en.wikipedia.org/wiki/Pure_function

One of the selling points of pure functional languages is the potential optimizations the compiler can theoretically do, including using multiple cores to evaluate a program, without any explicit hints from the programmer.

Lampsort: Leslie Lamport's Non-recursive Quicksort

Related Stories