True. However, andrii's solution does amortize the cost of the comparison across all array modifications, so you don't incur it all at once when doing the comparison. Depending on the actual requirements of the situation (and assuming you control array modifications, and are not just trying to compare two arrays you've been handed out of the blue), this may be a useful trick.
-- Maciek Sakrejda Truviso, Inc. http://www.truviso.com On Sun, 2008-02-24 at 10:42 -0800, Gordon Smith wrote: > > Of course, modifying an array would become more expensive operation, > but it's still O(1) operation > > The overhead when modifying each element is O(1), so the total > overhead you've incurred is O(n). > > Gordon Smith > Adobe Flex SDK Team > > > ______________________________________________________________________ > > From: flexcoders@yahoogroups.com [mailto:[EMAIL PROTECTED] > On Behalf Of andrii_olefirenko > Sent: Sunday, February 24, 2008 7:18 AM > To: flexcoders@yahoogroups.com > Subject: [flexcoders] Re: What is the best way to compare two arrays > element by element ignoring the o > > > > 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? > > > > > > > > > >
