I agree that it is O(1) in the sense that you describe, because the O(n) work has been amortized to be imperceptible. Do you actually know of a good hash function for this case? - Gordon
________________________________ From: flexcoders@yahoogroups.com [mailto:[EMAIL PROTECTED] On Behalf Of andrii_olefirenko Sent: Sunday, February 24, 2008 7:21 PM To: flexcoders@yahoogroups.com Subject: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o That's right if you treat a user as continuous array of input data. If the user is a human, that won't be the case. O(1) + O(1).. + O(1) won't do O(N) in total. Imagine the users who enters/modify the data in two arrays (via Flex app). They need to see if two arrays are identical. Our flex app will be O(1) if its response time is constant and doesn't depend on amount of data they already entered. In case of hash algorithm, this response time is slightly more that in usual algorithm (the computers are pretty good at calculating numeric values) but users won't notice this increase (it's just fractions of a second) Even if in total input time is bigger, i don't care (I would do care if my fingers were faster than calculation of hash value) And then it doesn't matter how many data you have in your arrays: 100 or 100000 items. You got feedback in O(1) manner - just comparing two numeric values - instantly. Hope this will make the clear the approach - it's not magic - one always pays - in this case i compare arrays not once in one loop but split the loop into many O(1) operations. (it's basically how multithreading works) Andrii Olefirenko --- In flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com> , "Gordon Smith" <[EMAIL PROTECTED]> 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:flexcoders%40yahoogroups.com> [mailto:flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com> ] On > Behalf Of andrii_olefirenko > Sent: Sunday, February 24, 2008 7:18 AM > To: flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.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 <mailto:flexcoders%40yahoogroups.com> <mailto:flexcoders%40yahoogroups.com> > , "Gordon Smith" <gosmith@> 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:flexcoders%40yahoogroups.com> <mailto:flexcoders%40yahoogroups.com> > [mailto:flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com> <mailto:flexcoders%40yahoogroups.com> > ] On > > Behalf Of andrii_olefirenko > > Sent: Saturday, February 23, 2008 1:01 AM > > To: flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com> <mailto: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 flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com> > <mailto: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? > > > > > >
