bearophile wrote:
Walter Bright:
Ain't that cool? But look closer. The advantage of quicksort is
that it is an *in-place* sort. The Haskell one creates new arrays
for every state in the sort. The other fundamental problem with the
Haskell version is that it selects the first array element as the
"pivot". This is the worst choice, since arrays to be sorted tend
to already be mostly sorted, and quicksort gives quadratic
performance to sort an already sorted array with the first element
as the pivot.

You are missing two big things, Walter:

1) The first one is big: that was not an example of a general-purpose
sort routine to be used to sort items. If you go look at how normal
system sort is done in Haskell you will see a much longer and much
more efficient implementation. The point of that example was to show
how you can compactly express a computational idea in Haskell, in a
safe, very compact and readable enough way. In a normal program a
significant percentage of the code doesn't need to be top
performance, in both runtime performance and memory used, because
it's used rarely and/or on small data sets. So for this code it's not
good to write an extremely efficient implementation, it's better to
use a safe, very compact and readable implementation. Haskell gives
you both safety and compact code. Note that for real sorting purposes
you don't use that onliner, you use some kind of system sort. So what
I am says applies to new code, absent in the standard library.

It's a piece of crap. A crappy example is a crappy example is a crappy
example. It consistently does more harm than good.

2) The second point you are missing is even bigger. Today languages
as Clojure (and F# and a bit less Scala) are using more and more
immutabe data structures. They reduce bugs, allow a quite simpler
multi-processing (so they are multicore-friendly) and they allow a
more functional-style coding (that in the hands of a modern
compiler/VM allows gives enough semantic constraints to allow a good
compilation. See pure functions). This of course puts more pressure
on the garbage collector, but the GC of Haskell is designed for this
purpose, and the compile is able to optimize away some of this work.
The resulting code is not as efficient as C code on a single CPU but
on many CPUs it may lead to efficient code.

Quicksort is parallellizable although it uses mutation so you chose the wrong example to make an otherwise generally valid point.

Please ask if you have missed my two points, because they must be
understood if you want to design a modern language.

I'd say that's a tad assuming :o).


Andrei

Reply via email to