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 #9749 is a reply to message #9707]

Wed, 13 August 1997 00:00

William Clodius
Messages: 30
Registered: December 1996

Member

Andy Loughe wrote:
>
> Hi!
>
> I feel I should know the answer to this one, but I don't, so here goes.
>
> Given vectors of the type...
>
> a = [1,2,3,4,5]
> b = [3,4,5,6,7]
>
> What is the most efficient way to determine which values that occur in
> a also occur in b (i.e., the values [3,4,5] occur in both a and b).
>
> Presumably this needs to be done without loops (to be efficient), but an
> obvious solution escapes me.
>
> Thanks for your help.
> <snip>

It is not clear whether you want the values or the positions of the
values (the second is harder). For the first case it is possible to this
with an algorithm that approximately scales as of order N ln N.

Assume you have two vectors of length N and M respectively.

If unsorted, sort them, => operations of order N ln N and M ln M.

If duplicates within a vector can exists, delete duplicates. Operations
of order N and M.

Concatenate arrays. An operation of order N + M

Sort concatenated array. An operation of order (N+M) ln (N+M)

Inspect adjacent elements of the sorted array to find duplicates. An
operation of order N+M.

Done.

--

William B. Clodius Phone: (505)-665-9370
Los Alamos Nat. Lab., NIS-2 FAX: (505)-667-3815
PO Box 1663, MS-C323 Group office: (505)-667-5776
Los Alamos, NM 87545 Email: wclodius@lanl.gov

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:55:18 PDT 2025

Total time taken to generate the page: 0.00425 seconds