A more specific use case may result in a more elegant solution On Sun, Feb 24, 2008 at 10:18 AM, andrii_olefirenko <[EMAIL PROTECTED]> wrote:
> 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 [email protected] <flexcoders%40yahoogroups.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: [email protected] <flexcoders%40yahoogroups.com> [mailto: > [email protected] <flexcoders%40yahoogroups.com>] On > > Behalf Of andrii_olefirenko > > Sent: Saturday, February 23, 2008 1:01 AM > > To: [email protected] <flexcoders%40yahoogroups.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 [email protected] <flexcoders%40yahoogroups.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? > > > > > > > >
