I'm pretty sure about MD5 transposition quality as it's used to hash passwords, it's not ordinary check sum. So yes, it's order depended. And therefore serialization of the object fields should be ordered (in alphabetical order, for instance) And it is indeed ordered, as far as i remember.
--- In flexcoders@yahoogroups.com, "Gordon Smith" <[EMAIL PROTECTED]> wrote: > > But MD5 is order-dependent, isn't it? Otherwise, MD5 would say that > documents containing "hello, world" and "world, hello" are the same. > > - Gordon > > ________________________________ > > From: flexcoders@yahoogroups.com [mailto:[EMAIL PROTECTED] On > Behalf Of andrii_olefirenko > Sent: Sunday, February 24, 2008 7:44 PM > To: flexcoders@yahoogroups.com > Subject: [flexcoders] Re: What is the best way to compare two arrays > element by element ignoring the o > > > > "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 <mailto:flexcoders%40yahoogroups.com> > , "Gordon Smith" <gosmith@> 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:flexcoders%40yahoogroups.com> > [mailto:flexcoders@yahoogroups.com <mailto:flexcoders%40yahoogroups.com> > ] On > > Behalf Of andrii_olefirenko > > Sent: Sunday, February 24, 2008 7:21 PM > > 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 > > > > > > > > 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> > <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%40yahoogroups.com> > > [mailto:flexcoders@yahoogroups.com > <mailto:flexcoders%40yahoogroups.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> > <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> > > <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%40yahoogroups.com> > > > [mailto:flexcoders@yahoogroups.com > <mailto:flexcoders%40yahoogroups.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> > > <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> > > > <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? > > > > > > > > > > > > > > >
