Re: fastest sorted list type?

"Peter Duniho" <NpOeStPeAdM@xxxxxxxxxxxxxxxx> wrote in message
news:op.t4ugi7fe8jd0ej@xxxxxxxxxxxxxxxxxxxxxxx
On Sat, 12 Jan 2008 16:43:37 -0800, colin <colin.rowe1@xxxxxxxxxxxxxxxxxx>
wrote:

[...]
was I right in my first attempt or is there a better way ?

Do you need the data sorted before you're done collecting it? If not,
then your first go at it was better. Maintaining data in sorted order is
generally at least as expensive as sorting it once.

thank for the reply, basically the data set is a list of all the possible
lines between
any two 3d points in a list. so that data grows in size quite quickly as the
number of points increase.
I maybe able to trim down the number but id still like to know wich is the
fastest sorted list.

its sorted on the length, wich is saved in the struct as its used many
times.

once the data is put into the container it isnt added to subsequently.
its discarded after being read about 5 times.
but basically it needs to be able to do the shortest lines first etc ...

An exception to this would be a binary tree implementation, which if I
recall correctly is what the non-generic SortedList class uses. A binary
tree has a poor worst-case performance (but then so too can some
implementations of quicksort), but for random data it's O(n log n) just
like quicksort.

why is there two types of comparer functionality,
one of wich accepts a static member function,
the other a member function wich cant be static yet it still
takes two parameters, whats the this pointer used for in such cases ?

I'm not really sure which versions you're talking about, but it _sounds_
like you're asking about the difference between the one that takes a
Comparison<T> and the one that takes an IComparer<T>.

yep thats the ones sorry if i wasnt explicit.

The former is simply a delegate...it need not be in any class if you
simply provide an anonymous method, and if it is in a class it can be a
static method or an instance method (though if it's an instance method
then of course you need to provide an instance from which to get the
delegate reference).

yes its confusing the BinarySearch needs a instance compared to the
List<t>.Sort
I just have to use a dummy struct is all.

The latter is an object that implements a specific interface, IComparer.
IComparer defines a single method, Compare(). This method would be
equivalent to the Comparison<T> delegate method.

In both cases, the comparison method compares the two parameters passed
in. They basically do the same thing, the only difference being how the
method is declared and then passed to the Sort() method.

sort uses either, but binary search uses the later, would this make it
slower ?

Not likely to produce a significant performance difference.

aha ok thanks, but im unsure why the binarysearch and add method is slower
than sort,
as it calls my comparer far fewer times, yet it seemed to never end with the
bigger lists ...
maybe its becuase the sort method is self contained and
so doesnt have the bounds checking etc for every access ?
or is it doing lots of moving ?
I dont know the internals at all.

the list contains over 2 million entries, wich is why i used an array of
structs as a list of classes would require lots of allocations

Allocations in .NET are _extremely fast. In fact, I would guess that you
could get a decent performance improvement using a class instead of a
struct, especially if the struct is relatively large, because the data
actually being moved during the sort would be smaller. It's difficult to
anticipate exactly where the break-even point would be, since classes
reduce your data locality which would hurt performance. But at some point
they would definitely win out.

Im not moving the structs at all, im only moving the index,
so its much like a class reference only with an extra level of indirection.
the structs also contain a fair amount of data wich is pre calculated
numbers to speed up computations.

All that said, 2 million elements is a lot of data, and sorting that much
data is going to be relatively slow no matter what you do. At least,
until they perfect quantum computer technology and a sort can be
accomplished in constant time. :)

it takes about 2 minutes to process many lists, only a few of wich are of
that size.
im considering if a binary tree would do better, but its not a trivial thing
to eveluate,
and its been a while since I went into this sort of thing in depth.

thanks
Colin =^.^=


.

Relevant Pages

  • Re: fastest sorted list type?
    ... like a merge sort. ... My method involves splitting the list up into many sub lists ... I gues its sensitive to data being in clumps wich in the extreme might mean ...
    (microsoft.public.dotnet.languages.csharp)
  • [Fwd: Re: >1024 connections in slapd / select->poll]
    ... I read your kqueue paper with great interest. ... The struct equeue describes the event list: ... for array indices there is a limit of 65535 events in an equeue. ... event lists and modifying them is essentially zero-cost. ...
    (Linux-Kernel)
  • Re: [PATCH] Driver Core patches for 2.6.7
    ... pointer to the struct class_simple that this device should be registered to. ... void device_unregister ... * controlling device power management will also be added. ... * A different set of lists than the global subsystem list are used to ...
    (Linux-Kernel)
  • [PATCH -mm 06/16] split LRU lists into anon & file sets
    ... Split the LRU lists in two, one set for pages that are backed by ... unsigned long *scanned, int order, int mode, ... int mode, struct zone *z, ...
    (Linux-Kernel)
  • [PATCH -mm 06/12] split LRU lists into anon & file sets
    ... Split the LRU lists in two, one set for pages that are backed by ... unsigned long *scanned, int order, int mode, ... int mode, struct zone *z, ...
    (Linux-Kernel)
Loading