[flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o

[andrii_olefirenko]

The trick is to keep hash value of all elements of the array.
Prerequisites are following:
1. Hash function H(index, object) should return unique value for the
object and the index of this object in the array (so two equal objects
in different positions have different hash value, H(i, obj1) !=
H(j,obj1) - this will force the order of elements).
2. On add/remove/modify operation, compute value h=f(h1, H(i, obj)),
where h1 - old hash value for the array, f - composition function (XOR
for example but could be something else). For empty array h1 equals
some initial value (like 0).

Then to check if two arrays are equal you just need to compare h
values of both arrays, which is O(1) operation.
Of course, modifying an array would become more expensive operation,
but it's still O(1) operation, so you basically eliminate all O(n)
(loops over array of data)
Of course, there could be more optimisation done if we knew more about
particular requirements.

Andrii Olefirenko

--- In flexcoders@yahoogroups.com, "Gordon Smith" <[EMAIL PROTECTED]> wrote:
>
> Can you give more detail? I don't believe there is any O(1) algorithm
> for this. O(1) means that comparing two 100,000-element arrays would
> take the same time as comparing two 100-element arrays.
>  
> Gordon Smith
> Adobe Flex SDK Team
> 
> ________________________________
> 
> From: flexcoders@yahoogroups.com [mailto:[EMAIL PROTECTED] On
> Behalf Of andrii_olefirenko
> Sent: Saturday, February 23, 2008 1:01 AM
> To: flexcoders@yahoogroups.com
> Subject: [flexcoders] Re: What is the best way to compare two arrays
> element by element ignoring the o
> 
> 
> 
> if you are really concerned about performance I would recommend to
> hash values added to the array into common hash and then comparing two
> arrays would take only O(1) not O(n)
> 
> Andrii Olefirenko
> 
> --- In flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com>
> , "Sergey Kovalyov"
> <skovalyov.flexcoders@> wrote:
> >
> > What is the best way to compare two arrays element by element
> ignoring the
> > order? My solution:
> > 
> > var differs : Boolean =
> > (a.length != b.length) ||
> > a.some(
> > function(item : Object, index : int, array : Array) : Boolean {
> > return (b.indexOf(item) == -1);
> > });
> > 
> > May be the better solution exists?
> >
>