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

Quicksort is the new Hello World

blog.rmontanaro.com

Post reply on HN
Print view View original

51–60 of 64 posts

Re: Quicksort is the new Hello World

#51

Post by sizzla »

neilc wrote: post #49
sizzla wrote: post #42

Earlier quoted context omitted.

Advancing compilers is hard. When people argue efficiency as a compiler implementation detail that is going to get worked out, they forget about many who have fallen before them. You can argue some older languages were written in a way in which it was (reasonably) easy to write a compiler that generates code with little performance overhead when compared to assembly (at worst a factor of 2 to 4, back in the 80s). Som…

When people argue efficiency as a compiler implementation detail that is going to get worked out, they forget about many who have fallen before them. Yes; see also http://prog21.dadgum.com/40.html

Thanks. Beatifully written and I love the print-shop analogy.

It's nice he is into the C&C Portland Wiki, there's golden nuggets of wisdom everywhere. I am reposting the link from his blog. http://c2.com/cgi/wiki?SufficientlySmartCompiler

Personally of the higher-level languages, I found SBCL to be crazy good at optimizing, of course given a few nudges with a compiler directive or two. By inspecting the dissasembly, I could validate it was doing the "right-thing" (TM), but then again, I do the same to check the C/C++ compiled code.

Re: Quicksort is the new Hello World

#52

Post by sizzla »

amalcon wrote: post #31
l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

It would be pretty difficult to write an in-place sort in Haskell, given that it only has mutable state through monads (and I doubt anyone wants to go into a monad just to sort something). GHC is pretty good at optimizing list concatenations, so that's probably not a big deal either. You're absolutely right about the two-pass filter, though.

It's not that good, which is why they gave up on using quicksort in Data.List .

Re: Quicksort is the new Hello World

#53

Post by merijnv »

sizzla wrote: post #43
aristidb wrote: post #30

Earlier quoted context omitted.

This is the real "sort" used by GHC 7: http://hackage.haskell.org/packages/archive/base/4.3.0.0/doc... It's pretty elegant, too, if less than the inefficient pseudo-qsort shown by the OP.

Correct me if I am wrong but they are actually using mergesort (mergeAll) as it is significantly faster in Haskell than in-place quicksort (qsort). That means there is a lot of overhead for doing something simple like an in-place qsort that should be much faster than a mergesort. I am at a loss on why the provided code is any more elegant than: http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29 or this (also…

> That means there is a lot of overhead for doing something simple like an in-place qsort

Well, the problem not so much that there is a lot of overhead for doing an in-place qsort. The problem is that "in-place" anything is impossible in Haskell, it violates referential transparency.

Merge sort however needs no in-place update and can trivially (in Haskell world) be parallelized (merge sort is associative, you can use it as the reduce step of MapReduce). So you are correct in concluding that mergesort is used in Haskell.

You state "something simple like an in-place qsort", your statement about qsort being simple makes some assumptions about your programming languages world, which are not the same for all languages especially not Haskell. No whether all this is a pro and a con depends on what sort of coding you're doing of course.

I think that people call Haskell's code more elegant because they (like me) find C++ template and type annotations to be annoyingly verbose and messy for no good reason. For example for the two quicksort functions:

"template void quicksort(RandomAccessIterator first, RandomAccessIterator last)"

vs

"quicksort :: (Ord a) => [a] -> [a]" (where "Ord a" means that a is an instance of the typeclass of ordered items).

Re: Quicksort is the new Hello World

#54

Post by seanmcq »

This test gives an extreme advantage to lazy functional languages that they don't enjoy in any realistic context.

Trying to come up with a single test that is good turns out to be surprisingly hard. In modern languages I'm looking for the ability to do clean functional code, stateful object code, async programming, a solid module system, and a type system that doesn't get in my way. I really can't imagine a single 5 line program that would encapsulate all of these areas.

Re: Quicksort is the new Hello World

#56

Post by dagw »

Deestan wrote: post #15
sb wrote: post #10

tl; dr, but a quick note: the presented algorithm takes the first element as the pivot element p: qsort (p:xs) = ... This is not recommended as it results in worst-case behavior on sorted input lists. (Another commentor correctly pointed out that it requires extra memory for the intermediate lists, too.)

It is just a toy implementation. If we're going to worry about practicals, then it's not recommended to use your own general purpose sorting implementations at all . For general purpose sorting, the standard library "always" has the best implementation.

Except it is also the canonical look-how-awesome-Haskell-is example that keeps getting trotted out all the time. Why aren't there more canonical examples of Haskell being both simple and awesome as well as fast and correct?

Re: Quicksort is the new Hello World

#57

Post by aristidb »

sizzla wrote: post #43
aristidb wrote: post #30

Earlier quoted context omitted.

This is the real "sort" used by GHC 7: http://hackage.haskell.org/packages/archive/base/4.3.0.0/doc... It's pretty elegant, too, if less than the inefficient pseudo-qsort shown by the OP.

Correct me if I am wrong but they are actually using mergesort (mergeAll) as it is significantly faster in Haskell than in-place quicksort (qsort). That means there is a lot of overhead for doing something simple like an in-place qsort that should be much faster than a mergesort. I am at a loss on why the provided code is any more elegant than: http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29 or this (also…

No, because it is solving a different problem. Quicksort cannot sort linked-lists, not even in C++. I think most implementations of std::list::sort (in C++) use some variant of mergesort.

And it is not true that in-place modification is not possible in Haskell. It is just not considered elegant, but it can be encapsulated in a perfectly Haskell-y way. (Hint: ST monad.)

Also I did not claim that my linked code is more elegant than some other code. Where did I make that claim? So I don't have to defend the claim I did not make, right?

Re: Quicksort is the new Hello World

#58

Post by sizzla »

merijnv wrote: post #53
sizzla wrote: post #43

Earlier quoted context omitted.

Correct me if I am wrong but they are actually using mergesort (mergeAll) as it is significantly faster in Haskell than in-place quicksort (qsort). That means there is a lot of overhead for doing something simple like an in-place qsort that should be much faster than a mergesort. I am at a loss on why the provided code is any more elegant than: http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29 or this (also…

> That means there is a lot of overhead for doing something simple like an in-place qsort Well, the problem not so much that there is a lot of overhead for doing an in-place qsort. The problem is that "in-place" anything is impossible in Haskell, it violates referential transparency. Merge sort however needs no in-place update and can trivially (in Haskell world) be parallelized (merge sort is associative, you can us…

If you want to be terse, you can just use typedefs but most of ISO C++03 libraries just assume your editor can autocomplete quickly. The culture is different and absolute clarity is preferred over terseness.

There's a lot of infrastructure behind MapReduce and I bet you any implementation is going to have a lot more code in it than what is in Data.List.

Once things are in RAM (say, less than 1 GB), quicksort is the fastest algorithm (Edit: or some other optimized in-place variation on the theme such as introsort). You can parallelize across cores all you want but all that is going to do is crap up your caches and cause bus contention, making your code more complex and slower. The bottleneck is your databus not the CPU, after all what is the cost of a compare in clock cycles? This is also why mergesort is slower and parallelizing is not going to fix it.

If you want to see things that are parallelizable check out vectorizing libraries such as Thrust that run on massively parallel GPGPUs that have the bus design and RAM to handle that kind of parallelization. They are written in C++ and both the implementation and the code to use them looks almost the same like the code I posted. The compiler technology of other languages is years behind and currently can't even target these kinds of architectures.

I've seen GPU massive parallelization in Haskell and all it did was to generate C code and then invoke the CUDA compiler. This was in a research paper. In the meantime you can fire up nvcc with Thrust and sort bazillion of keys with less than 10 lines of code in C++ using a well-tested library.

Edit: BTW, anyone (and I really don't know who would be doing this) who is even thinking of running a MapReduce Haskell cluster must have lots of free time and $$$ to burn on wasted CPU cycles.

Re: Quicksort is the new Hello World

#59

Post by [deleted] »

hristov wrote: post #44
l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

Ok, I am still learning Haskell, but I thought I would try to fix the above so that there is only one filter pass: qsort :: Ord a => [a] -> [a] qsort [] = [] qsort [x] = [x] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where (lesser, greater) = foldl split ([],[]) xs where split (left, right) x = if x Does this work?

[deleted]

Re: Quicksort is the new Hello World

#60

Post by fleitz »

sizzla wrote: post #41
DanielBMarkham wrote: post #38

Yet another article that completely misses the point. The point of "Hello World" is to show a noob how to fire up the editor, compile, and see something happen. And btw, here's the answer in F#: let rec qsort = function | [] -> [] | x::xs -> let smaller,larger = List.partition (fun y -> y

This looks like yet another Haskell "variant." From what I can tell this sort does not occur in place and thus would not make a particularly good quicksort. Memory use, number of accesses per element, etc. This style of programming is more suitable for heapsort or maybe mergesort.

Given the level of abstraction in most modern programing languages/ operating systems it's really hard to say that any modern language could implement quicksort in the most strict definitions.

For example, is a quicksort 'in-place' if your memory gets swapped to disk?

Post reply on HN