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) !=
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
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:
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
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
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
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
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,
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.
---
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, Sergey Kovalyov
[EMAIL PROTECTED] wrote:
What is the best way to
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
I don't believe that will do it, since the arrays aren't actually equal:
I believe Arrays (for the purposes of object comparison) are only equal
if they contain the same elements in the same order.
--
Maciek Sakrejda
Truviso, Inc.
http://www.truviso.com
-Original Message-
From: Scot
12 matches
Mail list logo
