 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Gilles Tran wrote:
> Haskell ;) http://brainwagon.org/2006/11/27/why-haskell-indeed/
> Perhap Andy should send him his resume...
Hey, Mark Chu-Carrol. I went to grad school with him, back when he was
Mark Carrol. Actually, I knew his wife Chu also. :-) Funky where you
run across people.
--
Darren New / San Diego, CA, USA (PST)
"That's pretty. Where's that?"
"It's the Age of Channelwood."
"We should go there on vacation some time."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Hey, Mark Chu-Carrol. I went to grad school with him, back when he was
> Mark Carrol. Actually, I knew his wife Chu also. :-) Funky where you
> run across people.
Not when you live by yourself in your bedroom...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Gilles Tran <gitran_nospam_@wanadoo.fr> wrote:
> http://brainwagon.org/2006/11/27/why-haskell-indeed/
I think he has a point. Quicksort is not such a good example because
quicksort is rather easy and short to implement in almost any language
(which is one of the strengths of quicksort: it's so fast because its
inner loop is so small).
What I would like to see is introsort in haskell to see how easy and
fast it is.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> I think he has a point. Quicksort is not such a good example because
> quicksort is rather easy and short to implement in almost any language
> (which is one of the strengths of quicksort: it's so fast because its
> inner loop is so small).
I think he has a point too.
However, as the blog author points out, it's kinda difficult. To see how
good a language "really is", you need a non-trivial example. But if
you're trying to write a tutorial, you need small examples which are
easy to understand - in other words, trivial. Kind of a no-win situation
there...
> What I would like to see is introsort in haskell to see how easy and
> fast it is.
Heh. I once tried to implement something similar to this. It did an
insert sort on lists of less than 50 elements, and a quicksort
otherwise. However, I made a *fatal* mistake: I used the "length"
function to determine the size of the list. At every iteration.
Shall we just say it was "not fast"?
Anyway, assuming you've already got a heapsort function that takes a
list and completely sorts it, and you want to swap from quicksort to
heapsort after exactly 16 iterations, you could do something like this:
introsort = choose 16
choose 0 xs = heapsort xs
choose n (x:xs) =
(choose (n-1) (filter (<x) xs)) ++ [x] ++
(choose (n-1) (filter (>x) xs))
Of course, a good quicksort utterly depends on picking the right pivot.
And for a linked list, it seems hard to do that without wasting too much
time trying to pick a pivot. So I'm not really sure quicksort is a good
algorithm to be using on a linked list in the first place, but hey...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Of course, a good quicksort utterly depends on picking the right pivot.
> And for a linked list, it seems hard to do that without wasting too much
> time trying to pick a pivot. So I'm not really sure quicksort is a good
> algorithm to be using on a linked list in the first place, but hey...
In Java, if you sort a linked list (or any collection with linear lookup
time), it copies the whole contents into an array, sorts it, and copies
the sorted results back to the structure you were using.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Of course, a good quicksort utterly depends on picking the right
>> pivot. And for a linked list, it seems hard to do that without wasting
>> too much time trying to pick a pivot. So I'm not really sure quicksort
>> is a good algorithm to be using on a linked list in the first place,
>> but hey...
>
> In Java, if you sort a linked list (or any collection with linear lookup
> time), it copies the whole contents into an array, sorts it, and copies
> the sorted results back to the structure you were using.
Ouch! That's a bit expensive isn't it?
Mind you... maybe not... A quick sort with a decent pivot is going to be
that much faster.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Of course, a good quicksort utterly depends on picking the right
>>> pivot. And for a linked list, it seems hard to do that without
>>> wasting too much time trying to pick a pivot. So I'm not really sure
>>> quicksort is a good algorithm to be using on a linked list in the
>>> first place, but hey...
>>
>> In Java, if you sort a linked list (or any collection with linear
>> lookup time), it copies the whole contents into an array, sorts it,
>> and copies the sorted results back to the structure you were using.
>
> Ouch! That's a bit expensive isn't it?
>
> Mind you... maybe not... A quick sort with a decent pivot is going to be
> that much faster.
I once thought sorting a linked list would be even faster than an array,
since moving elements around is so fast (no copying needed, just
changing the link). Then pretty quickly noticed how stupid that was; you
need to read elements to know *where* to move the elements, and reading
random elements is not fast...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] dev null> wrote:
> Anyway, assuming you've already got a heapsort function that takes a
> list and completely sorts it, and you want to swap from quicksort to
> heapsort after exactly 16 iterations, you could do something like this:
While introsort probably doesn't "officially" state how the pivot is
chosen, the median-of-3 choosing algorithm is the de-facto standard.
> Of course, a good quicksort utterly depends on picking the right pivot.
> And for a linked list, it seems hard to do that without wasting too much
> time trying to pick a pivot. So I'm not really sure quicksort is a good
> algorithm to be using on a linked list in the first place, but hey...
As I have commented to you before, it is possible to use the median-of-3
pivot choice even with linked lists.
Of course it's much easier to do with a true array, which I think it's
one weak point of Haskell, at least currently?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> I once thought sorting a linked list would be even faster than an array,
> since moving elements around is so fast (no copying needed, just
> changing the link). Then pretty quickly noticed how stupid that was; you
> need to read elements to know *where* to move the elements, and reading
> random elements is not fast...
Well, if the array elements are quite large, a linked list could
arguably be faster. However, in that case you'd likely use an array of
pointers, and any advantage is gone.
[I believe Warp has done some work on this question though...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> In Java, if you sort a linked list (or any collection with linear lookup
> time), it copies the whole contents into an array, sorts it, and copies
> the sorted results back to the structure you were using.
Why? C++ supports sorting of its linked list data structure, and it
does so in-place, without the need for additional memory and without
having to copy elements around. And it's very fast.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
