Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lampsort: Leslie Lamport's Non-recursive Quicksort

bertrandmeyer.com

Post reply on HN
Print view View original

21–30 of 46 posts

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#21

Post by hyt7u »

taeric wrote: post #6
rav wrote: post #2

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

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

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#22

Post by vram22 »

jerluc wrote: post #10
tedunangst wrote: post #5

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?

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

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

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#23

Post by taeric »

hyt7u wrote: post #21
taeric wrote: post #6

Earlier quoted context omitted.

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

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

Threaded trees was what I had in mind.[1] I believe the example there still talks of checking a visited list, though. Either a misunderstanding on my part, or on that page. I'll have to check on my books. Later, sadly. :)

[1] http://en.wikipedia.org/wiki/Threaded_binary_tree

Edit: Apologies for a quick edit. I remembered I had a short implementation on my computer. Basically, when you follow a link, you know if it was a regular link or a thread. If it was a regular link, you could still go left from the new node. Otherwise, you visit and go right. Again, keep note of whether it was a thread or not. Repeat until done. (Make sense?)

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#24

Post by bluecalm »

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.

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#25

Post by TheLoneWolfling »

Cushman wrote: post #12
jwmerrill wrote: post #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…

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 im…

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

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#26

Post by TheLoneWolfling »

tedunangst wrote: post #18
Cushman wrote: post #8

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…

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

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.

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#27

Post by TheLoneWolfling »

jwmerrill wrote: post #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…

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

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#28

Post by lisper »

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

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#29

Post by tedunangst »

TheLoneWolfling wrote: post #26
tedunangst wrote: post #18

Earlier quoted context omitted.

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

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.

Fair point. I assume you get a reasonable pivot.

Recursing on one of the two halves of the "current" partition is the cache friendliest option. Smallest interval will guarantee this by induction, I think, but I've never heard that the size of the stack is really a problem in quicksort. If you continuously partition out only a single element, your runtime is going to suck, even if you "sort" those elements first.

Re: Lampsort: Leslie Lamport's Non-recursive Quicksort

#30

Post by hyt7u »

taeric wrote: post #23
hyt7u wrote: post #21

Earlier quoted context omitted.

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

Threaded trees was what I had in mind.[1] I believe the example there still talks of checking a visited list, though. Either a misunderstanding on my part, or on that page. I'll have to check on my books. Later, sadly. :) [1] http://en.wikipedia.org/wiki/Threaded_binary_tree Edit: Apologies for a quick edit. I remembered I had a short implementation on my computer. Basically, when you follow a link, you know if it wa…

Ah, great, thanks. I wasn't thinking about modifications to the tree.
Post reply on HN