 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmail isthebestcom> wrote:
> I once thought sorting a linked list would be even faster than an array,
It is, if copying one element is slow enough.
> 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...
It is perfectly possible to implement merge sort and even quick sort
on a linked list without the need for random access. Merge sort is the
best for linked lists because it's truely O(n log n), has no pathological
cases, and for doubly-linked lists requires no additional memory. (The
array links can be used as the "additional memory" the merge sort algorithm
requires, so no additional memory needs to be allocated just for the
sorting.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp escribió:
> 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.
I said how it works, it wasn't my idea :D
http://ln-s.net/1jjA
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> As I have commented to you before, it is possible to use the median-of-3
> pivot choice even with linked lists.
Yeah, it just adds an extra traversal. (Interestingly, I don't think
that technically alters the complexity class of the algorithm...)
> 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?
Merge sort or heap sort is probably a more natural fit for Haskell.
(For a merge sort, you can split a list into the even and odd elements,
sort, and then merge. Heapsort I've demonstrated here before...)
If you did want to do a quick sort, you'd have to decide whether you
want to use immutable or mutable arrays. If I feel sufficiently bored
I'll have a go at implementing them. (I'm curios to see what it would
look like myself...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] devnull> wrote:
> 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.
If you are using a linked list because of the advantages of linked lists,
then using an array to sort the list is useless overhead because linked
lists can be sorted in-place in O(n log n) time.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> http://ln-s.net/1jjA
"This avoids the n2 log(n) performance that would result from attempting
to sort a linked list in place."
I would have never though I would see such BS from such a big company
(who is not Microsoft).
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] devnull> wrote:
> Warp wrote:
> > As I have commented to you before, it is possible to use the median-of-3
> > pivot choice even with linked lists.
> Yeah, it just adds an extra traversal.
The extra traversal can be used to perform the first partitioning
(using eg. simply the first element as pivot), thus potentially reducing
the overall amount of work.
> (Interestingly, I don't think
> that technically alters the complexity class of the algorithm...)
No, because the "extra traversal" has to be done only once. That adds
only one 'n' to the total time, which does not affect the complexity class.
> > 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?
> Merge sort or heap sort is probably a more natural fit for Haskell.
Merge sort is quite efficient for linked lists because it can be done
in-place and without requiring extra memory. On the other hand, it's a bit
complicated to implement for linked lists.
> (For a merge sort, you can split a list into the even and odd elements,
> sort, and then merge.
But does this avoid creating new lists? In other words, can Haskell
optimize it so that the merge sort is done in-place, without requiring
any additional memory?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> http://ln-s.net/1jjA
>
> "This avoids the n2 log(n) performance that would result from attempting
> to sort a linked list in place."
>
> I would have never though I would see such BS from such a big company
> (who is not Microsoft).
......what...the...hell.....?
Seriously. Wow.
A stand astounded. I can't *begin* to imagine what they were thinking.
The only explanation I can come up with is that the document is
incorrect and the actual implementation does something sane. Just... wow.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> A stand astounded. I can't *begin* to imagine what they were thinking.
> The only explanation I can come up with is that the document is
> incorrect and the actual implementation does something sane. Just... wow.
>
Did you know Java is open-source nowadays?
(this is from Collections.java)
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
That's the magic inside. Note it's converted into an array without first
checking what kind of list it is (even an ArrayList would suffer this
unneeded copying!).
Arrays.sort then uses clone() on the array, making yet another copy.
Apparently that's needed for the actual implementation.
(Arrays.java)
public static void sort(Object[] a) {
Object[] aux = (Object[])a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
mergeSort signature is:
private static void mergeSort(Object[] src, Object[] dest,
int low, int high, int off)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Yeah, it just adds an extra traversal.
>
> The extra traversal can be used to perform the first partitioning
> (using eg. simply the first element as pivot), thus potentially reducing
> the overall amount of work.
Yeah, true. And that's the kind of trick Haskell's compiler is likely to
pull off too...
>> (For a merge sort, you can split a list into the even and odd elements,
>> sort, and then merge.
>
> But does this avoid creating new lists? In other words, can Haskell
> optimize it so that the merge sort is done in-place, without requiring
> any additional memory?
Well, between garbage collection, lazy evaluation and aggressive
compiler optimisations, that's not a terribly easy question to answer.
Will it do it with absolutely *no* extra memory at all? Will it
literally take a linked list in memory and just rewrite a few pointers
to make it into a sorted list? I can more or less guarantee that's a "no".
Will it eat N log N extra memory? Again, I can more or less promise you
that's a "no".
If the optimiser does what it's supposed to, and you're not holding on
to a pointer to the original, unsorted list, it should allocate new list
cells directly in sorted order, with GC cleaning up the old cells as the
become unused. [I haven't studied the algorithm in detail, but I'm
fairly confident the N log N potential intermediate lists can be elided
by the optimiser.]
Of course, if sorting is just one part of a long pipeline of list
operations, it's possible that the sorting could be partially merged
with other steps in the pipeline too... as you once said, reasoning
about Haskell program performance isn't that easy for the most part.
[The *other* possibility of course is to design your own brand new list
type that supports explicit in-place updates. But if you're that worried
about space efficiency, it'll probably be better to use an array...]
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Yeah, true. And that's the kind of trick Haskell's compiler is likely to
> pull off too...
I thought it was pretty cool that the latest Erlang compilers will see
code like
map(F, [H|T]) -> [F(H)|map(F,T)];
map(F, []) -> [].
and turn it into the same code you'd get with an auxiliary accumulator
and a call to "reverse" at the end.
--
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
|
|
| |
| |
|
|
|
|
| |
|
|
