Any algorithm ideas?

Hello

I am developing an addin for Groupwise in which I have a particular
problem. It is an issue of efficiency(not GW related)

I need to scan a collection of objects each with a long & painful ID
for example: 345SD3G098F.3F9SDNSD.SDF8S7DF98.SDFSDG

So my approach up to this point has been to create a sorted string array, do
an inital pass at the cost of O(N) - not too horrible for 1 pass.

However, at regular intervals, I need to scan this same collection for
changes. First I check the counts of each. If they are the same, I do
nothing. That helps alot, but when changes are made, my algorithm becomes:

For each MESSAGE in objMESSAGEBOX

If DoBinarySearch(myArray(), MESSAGE.ID) = NOT_FOUND then
RaiseEvent FoundNewMessage(MESSAGE )
end if

next

This yields about O(N * NlogN) if I remember my big O notation correctly.

Can anyone think of a more efficient way to implement this? I tried custom
Datatypes using a date-based sort, however, had little success.

Thanks in advance.

Andrew

anonymous
Fri Apr 30 03:11:03 CDT 2004

This post makes absolutely no sense whatsoever.

Jens
Fri Apr 30 03:23:35 CDT 2004

Hi Andrew,

is sorting important? If it is not so then why don't you use a
dictionary? beware that the Scripting.dictionary gets VERY slow with
more than 10000 elements. Using a dictionary would make finding new
messages O(N), you don't get that much faster (the fastest would be
O(new_messages)).

If sorting is important use a self balancing tree
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
( finding new messages : O(n * log n ) )

I am also not quite certain what you do with the new messages, aren't
they "sorted in"? [*]

Also a good resource for algorithms is
http://www.nist.gov/dads/


Jens

[*]
If you need sorting you could use a heapsort derivate called
smoothsort that sorts in O(n) to O(n log n), depending how presorted
your data is. I have never used or implemented smoothsort myself so
beware.
http://en.wikipedia.org/wiki/Smoothsort


> Hello
>
[snip]

>
> I need to scan a collection of objects each with a long & painful ID
> for example: 345SD3G098F.3F9SDNSD.SDF8S7DF98.SDFSDG
[snip]

>
>

Andrew
Fri Apr 30 12:41:19 CDT 2004

Jens Thank you very much

That looks like something... Here is a good article I found on it:

http://www.vbwm.com/art_2001/avltree08/

Thanks Again

Andrew

BTW.. Bonj I got a good laugh at your post! I rarely if ever make any sense
;)

"Jens Neuhalfen" <JNeuhalfen@akkaya.de> wrote in message
news:uiRJJzoLEHA.1892@TK2MSFTNGP10.phx.gbl...
> Hi Andrew,
>
> is sorting important? If it is not so then why don't you use a
> dictionary? beware that the Scripting.dictionary gets VERY slow with
> more than 10000 elements. Using a dictionary would make finding new
> messages O(N), you don't get that much faster (the fastest would be
> O(new_messages)).
>
> If sorting is important use a self balancing tree
> http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
> ( finding new messages : O(n * log n ) )
>
> I am also not quite certain what you do with the new messages, aren't
> they "sorted in"? [*]
>
> Also a good resource for algorithms is
> http://www.nist.gov/dads/
>
>
> Jens
>
> [*]
> If you need sorting you could use a heapsort derivate called
> smoothsort that sorts in O(n) to O(n log n), depending how presorted
> your data is. I have never used or implemented smoothsort myself so
> beware.
> http://en.wikipedia.org/wiki/Smoothsort
>
>
> > Hello
> >
> [snip]
>
> >
> > I need to scan a collection of objects each with a long & painful ID
> > for example: 345SD3G098F.3F9SDNSD.SDF8S7DF98.SDFSDG
> [snip]
>
> >
> >