comp.lang.idl-pvwave archive: archive » Efficient comparison of arrays

Home » Public Forums » archive » Efficient comparison of arrays

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Re: Efficient comparison of arrays [message #9738 is a reply to message #9707]

Thu, 14 August 1997 00:00

J.D. Smith
Messages: 214
Registered: August 1996

Senior Member

> <snip>
>
> All very true. With any method there are going to be some tradeoffs.
> But I am skeptical of a method that relies on the sorting of the
> arrays in question. In my timing above for CONTAIN(), of the 10.10
> seconds, 9.40 are spent sorting the array! On some hardware and with
> some data this may not be a problem; on my hardware and with my
> data it most definitely is.
>

It all boils down to this... the bulk of the time taken by contain() is
in sorting. This is obvious. Let a and b be the two vectors in
question. Let a have n elements and b have m elements. The approximate
number of operations to do the sorting is then (n+m)log(n+m) for an
efficient sorting algorithm, on average. On the other hand,
find_elements() necessarily takes on order (n x m) operations (for each
of the m elements in b, compare it with all n elements in a). If n>>m
then the sorting term is approximately nlog(n). Which method takes more
operations? The ratio of the two operation counts is r=log(n)/m. When
this is unity, the two methods will be roughly on equal footing. If r
is much greater than 1, find_elements() will be faster. For r much less
than one, contain() with it's sorting will be faster. In the case of
n=m, r=2log(2n)/n << 1 for any sizeable n ( > 10, say).

So, truly, it does depend critically on your data. I found, on my
machine, an equality at approximately m=25 for n=65536. Log(n)=16 in
this case, so it's not too far off. For larger, n, the test gets more
accurate (until memory becomes an issue).

JD

Report message to a moderator

[Message index]

		Efficient comparison of arrays By: Andy Loughe on Fri, 08 August 1997 00:00
		Re: Efficient comparison of arrays By: J.D. Smith on Thu, 14 August 1997 00:00
		Re: Efficient comparison of arrays By: David Foster on Thu, 14 August 1997 00:00
		Re: Efficient comparison of arrays By: William Clodius on Thu, 14 August 1997 00:00
		Re: Efficient comparison of arrays By: William Clodius on Wed, 13 August 1997 00:00
		Re: Efficient comparison of arrays By: J.D. Smith on Wed, 13 August 1997 00:00
		Re: Efficient comparison of arrays By: David Foster on Wed, 13 August 1997 00:00
		Re: Efficient comparison of arrays By: J.D. Smith on Tue, 12 August 1997 00:00
		Re: Efficient comparison of arrays By: J.D. Smith on Mon, 11 August 1997 00:00
		Re: Efficient comparison of arrays By: davidf on Mon, 11 August 1997 00:00
		Re: Efficient comparison of arrays By: davidf on Mon, 11 August 1997 00:00
		Re: Efficient comparison of arrays By: John Votaw on Wed, 20 August 1997 00:00

Previous Topic:	Animations to mpeg/fli
Next Topic:	performing a TVRD() on 24 bit images...

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Wed Oct 08 17:31:55 PDT 2025

Total time taken to generate the page: 0.00456 seconds