To be fair, that is because it is a carefully tuned combination of 3 sort routines (quicksort, heapsort, insertion sort), and also optimisations to avoid unnecessary checks for pointers reaching the end of arrays where they can be avoided.
I would be impressed if a sort which used the same 3 combined techniques could be faster.
(Of course, there might be better sorts, such as TimSort, but that's a change of algorithm, not language).
I think timsort is trying to optimize on comparison counts, because comparisons might call back into Python code, which is expensive. Other sorting algorithms optimize different operations.
Is it actually possible to implement quicksort in a pure functional language like Haskell (with immutable data structures)? Sorting in place would seem to involve mutating the list every time two values are swapped.
Haskell is designed to quarantine side effects, not remove them altogether. There's a special monad for building data structures that are mutable at creation time but appear immutable outside that block of code. In normal circumstances, you'd probably still have to copy the contents of the input into a new array before sorting it, though. So, it would still be less memory efficient on large inputs.
Mutability is attained by using the ST monad. The ST monad uses mutable memory, but since it does not allow other interactions with the outside world, its value can be extracted (unlike the IO monad). When you are done with the modification of the vector, it can be frozen to obtain a pure vector.
The IO monad can also be used, but not if you want to return a pure value.
I'd argue that it's a good thing to use an algorithm that is efficient in and of itself. (And perhaps a language which invites the use of such an algorithm.)
The efficiency of algorithms depends on the language / model of computation you are using.
For an extreme example, the best way to write an efficient matrix multiplication in Fortran is to write a naive matrix multiplication. The compiler will recognize the pattern, and transform it.
Obligatory comment about quicksort being excessively popular because of its catchy name, and all-too-often delivering inferior performance on large datasets due to partial orderings & bad pivot choices.
Obligatory comment about how sorting algorithm speed is far more important when dealing with incredibly large datasets, spanning across multiple machines. Uninsightful (and perhaps glib) point about how Machines Are So Fast These Days that even Bubble Sort appears fast for medium-sized datasets.
Cleverly-worded comment about how Merge Sort is not the sort of sort to let you down in a jam, and how it is particularly suited to distributed computation (where the overhead of allocation is rendered meaningless by the I/O requirements).
Haskell's type system can also express interesting things most languages' type systems can't.
For example:
https://github.com/yairchu/red-black-tree/blob/master/AvlTre... -- in lines 13..21, an AVLTree type is defined -- with its invariants encoded in the type system. If there's a mistake in these 9 lines, you may get a wrong program. But the nice thing is that if you get just these 9 lines right -- then the hundreds of lines below it that implement an AVL tree cannot get the AVL invariants wrong.
Lines 26..36 inclusive encode the RBTree type such that the invariants are enforced by the type-checker.
In case this is unclear: the type-checker enforcing the correctness of the invariants is at compile-time. A running program is a correct program, at least from the invariants' perspective.
On the one hand, I agree. On the other hand, a type declaration cannot possibly tell you /why/ unless the type system encodes a significant portion of our physical world.
This encoding is left as an exercise for the reader.
Agreed, generally. I'd say comments are to express things the code itself cannot. More expressive languages can get by with good naming, some declarations, and clear idioms in many cases.
The most useful kind of comments are "why" comments, about why specific design trade-offs were chosen.
I mainly agree with you, but for something like that, "it's an AVL tree, look it up" is all it should need. Names and type declarations handle the rest.
If you want to dismiss me as "one of those" people that is anti-commenting, you're reading too much into what I said. You said, "it doesn't have comments!", I said "actually, it does, and they're even checked." The end.
In a more complex program, I'd add comments. How many, and the nature of the comments, depends on whether I was writing in something relatively low-level (like C) or something high-level (like Haskell, Erlang, or K).
That's a very interesting question. I made a stab at removing the invariant enforcement from the AVL tree code, but it was more involved than I expected.
In this specific case, it doesn't matter much since compilation takes less than a second on my underpowered netbook. I'm curious whether it's an issue for a program of significant size.
GADT are really cool, but I would like to note three caveats:
1.
> in lines 13..21, an AVLTree type is defined -- with its invariants encoded in the type system
Its balance invariants are encoded, but its ordering invariants are not.
2. The code for manipulating AVL and red-black trees in GADT form is significantly more complicated that it would be if they were not in GADT form.
3. Sometimes, whether using GADTs or not, one ends up with code like this, from the AVL example:
> Nil -> undefined -- shouldnt happen
Needless to say, this negatively affects the comfort we might receive from the type system.
Having said all that, I think there are cases where GADTs are really worth the extra effort. Sometimes, they even simplify code when the alternative to GADTs is checking things at run-time!
1. True, this is harder in Haskell. More easily possible in a language like Agda.
2. The assurances you get in return are probably worth it.
3. I think that piece is unnecessary, and the type system will see that constructor is impossible. If it doesn't, it's a limitation of Haskell GADT's, and can be fixed. I don't think you ever resort to "Nil -> undefined" in Agda.
His version is explicit, sort of a C++ translation of the C algorithm (though still a bit longer than necessary even for C). I think he meant to imply "in simple C++ without STL." The awkwardness of partition() is not quite enough to overcome the LOC savings, but it's making a good effort.
The Haskell version also refrains from importing the equivalent Data.List, which would allow us to define `more` and `less` as simply `partition (< x) xs`.
37 comments
[ 3.4 ms ] story [ 89.8 ms ] threadI would be impressed if a sort which used the same 3 combined techniques could be faster.
(Of course, there might be better sorts, such as TimSort, but that's a change of algorithm, not language).
It's still short and sweet ;).
http://hackage.haskell.org/package/vector-0.7.0.1
Mutability is attained by using the ST monad. The ST monad uses mutable memory, but since it does not allow other interactions with the outside world, its value can be extracted (unlike the IO monad). When you are done with the modification of the vector, it can be frozen to obtain a pure vector.
The IO monad can also be used, but not if you want to return a pure value.
A good tutorial can be found at:
http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector...
I used mutable vectors in the ST monad in maximum entropy training software, and they are really performant.
I was like, "Wait. Wait. Waaaiiiitt. How does it do that?"
For an extreme example, the best way to write an efficient matrix multiplication in Fortran is to write a naive matrix multiplication. The compiler will recognize the pattern, and transform it.
Obligatory comment about how sorting algorithm speed is far more important when dealing with incredibly large datasets, spanning across multiple machines. Uninsightful (and perhaps glib) point about how Machines Are So Fast These Days that even Bubble Sort appears fast for medium-sized datasets.
Cleverly-worded comment about how Merge Sort is not the sort of sort to let you down in a jam, and how it is particularly suited to distributed computation (where the overhead of allocation is rendered meaningless by the I/O requirements).
Welcome to: http://www.findsoso.com/
We specialized in the exportation of sport shoes and other
products(clothing, bag,sunglasses,watches,belts,etc )which
have great enjoyed popularty in the world market Many of
our goods are on sales ,we can guarantee the crediblity by
Pay-pal and delivery time .we would like to make a long termship.
http://www.findsoso.com/
c.l.o.t.h.i.n.g,j.e.a.n,,h.a.n.d.b.a.g,(f.r.e.e)s.h.i.p.p.i.n.g
Cheap Sweater
>>>------I love you! ----> http://www.findsoso.com/
Believe you will love it. Accept paypal or credit card and free shipping.
I don't disagree on any particular point, but this is hardly news (on HN, at least), and is rather lacking in substance.
http://www.haskell.org/ghc/docs/7.0.2/html/libraries/base-4....
For example:
https://github.com/yairchu/red-black-tree/blob/master/AvlTre... -- in lines 13..21, an AVLTree type is defined -- with its invariants encoded in the type system. If there's a mistake in these 9 lines, you may get a wrong program. But the nice thing is that if you get just these 9 lines right -- then the hundreds of lines below it that implement an AVL tree cannot get the AVL invariants wrong.
The same is also true for Red Black Trees: https://github.com/yairchu/red-black-tree/blob/master/RedBla...
Lines 26..36 inclusive encode the RBTree type such that the invariants are enforced by the type-checker.
In case this is unclear: the type-checker enforcing the correctness of the invariants is at compile-time. A running program is a correct program, at least from the invariants' perspective.
To paraphrase: Some people write tricky code and say, "Ah! I will use a comment to make this clear." Now they have two problems.
I didn't write it, by the way.
This encoding is left as an exercise for the reader.
The most useful kind of comments are "why" comments, about why specific design trade-offs were chosen.
To understand code, you need to figure out "why" and "what". Code gives you one, comments give you the other.
If you want to dismiss me as "one of those" people that is anti-commenting, you're reading too much into what I said. You said, "it doesn't have comments!", I said "actually, it does, and they're even checked." The end.
In a more complex program, I'd add comments. How many, and the nature of the comments, depends on whether I was writing in something relatively low-level (like C) or something high-level (like Haskell, Erlang, or K).
In this specific case, it doesn't matter much since compilation takes less than a second on my underpowered netbook. I'm curious whether it's an issue for a program of significant size.
1.
> in lines 13..21, an AVLTree type is defined -- with its invariants encoded in the type system
Its balance invariants are encoded, but its ordering invariants are not.
2. The code for manipulating AVL and red-black trees in GADT form is significantly more complicated that it would be if they were not in GADT form.
3. Sometimes, whether using GADTs or not, one ends up with code like this, from the AVL example:
> Nil -> undefined -- shouldnt happen
Needless to say, this negatively affects the comfort we might receive from the type system.
Having said all that, I think there are cases where GADTs are really worth the extra effort. Sometimes, they even simplify code when the alternative to GADTs is checking things at run-time!
2. The assurances you get in return are probably worth it.
3. I think that piece is unnecessary, and the type system will see that constructor is impossible. If it doesn't, it's a limitation of Haskell GADT's, and can be fixed. I don't think you ever resort to "Nil -> undefined" in Agda.
The Haskell version also refrains from importing the equivalent Data.List, which would allow us to define `more` and `less` as simply `partition (< x) xs`.