"I'm not a math guy, I'm more of a miracle guy"(c) :) Picking up a good hash function is art :) I would start with MD5 over serialized version of the object, but there could be more effective hash functions if you know more about object structure.
--- In flexcoders@yahoogroups.com, "Gordon Smith" <[EMAIL PROTECTED]> wrote: > > 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" <gosmith@> 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? > > > > > > > > > >
