Re: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o
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 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 flexcoders%40yahoogroups.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 flexcoders%40yahoogroups.com [mailto:
flexcoders@yahoogroups.com flexcoders%40yahoogroups.com] On
Behalf Of andrii_olefirenko
Sent: Saturday, February 23, 2008 1:01 AM
To: flexcoders@yahoogroups.com 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 flexcoders%40yahoogroups.commailto:
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?
RE: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o
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 mailto:flexcoders%40yahoogroups.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:flexcoders%40yahoogroups.com
[mailto:flexcoders@yahoogroups.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
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
, 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?
RE: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o
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?
RE: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o
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 10 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,
RE: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o
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 [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: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 10 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
RE: [flexcoders] Re: What is the best way to compare two arrays element by element ignoring the o
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
[EMAIL PROTECTED] 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?
