Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > How to compare two arrays for identical objects?

Reply
Thread Tools

How to compare two arrays for identical objects?

 
 
Harald Kirsch
Guest
Posts: n/a
 
      07-02-2004
In my previous life, using C, the two arrays
contained pointers to objects and I kept
the arrays sorted according to the pointers'
equivalent int value. Comparing the two arrays
to check whether they contain identical objects
could be done in O(n) where n is the length
of the arrays.

In Java, identity can be established by x==y,
but sadly there is no total order defined
on object references. Consequently I cannot
keep the arrays sorted --- except in special
cases where objects implement Comparable. As
a result, the comparison becomes O(n^2).

A half solution uses System.identityHashCode()
to keep the arrays roughly sorted. Only within
a run of equal hash codes, each element of
one array must be compared with each element
of another array.

The resulting code is unnecessarily complicated
in particular in view of the fact that
on most Java implementations the
System.identityHashCode() is in fact unique.

It seems a total order on object references
would be a great thing for such problems.

Other ideas?

Harald Kirsch
 
Reply With Quote
 
 
 
 
Tobias Lehmann
Guest
Posts: n/a
 
      07-02-2004
You could try to put both arrays into a TreeMap with a Comperator that
implements the "==" function.
This would reduce the O(n^2) to O(n*ln(n)), which is equal to a new sorting.
You then still face the problem of two identical references in one array,
but this should be solvable by a workaround wrapping the references with a
number for each array. (If a destinction between these is intented)


"Harald Kirsch" <(E-Mail Removed)> schrieb im Newsbeitrag
news:(E-Mail Removed) m...
> In my previous life, using C, the two arrays
> contained pointers to objects and I kept
> the arrays sorted according to the pointers'
> equivalent int value. Comparing the two arrays
> to check whether they contain identical objects
> could be done in O(n) where n is the length
> of the arrays.
>
> In Java, identity can be established by x==y,
> but sadly there is no total order defined
> on object references. Consequently I cannot
> keep the arrays sorted --- except in special
> cases where objects implement Comparable. As
> a result, the comparison becomes O(n^2).
>
> A half solution uses System.identityHashCode()
> to keep the arrays roughly sorted. Only within
> a run of equal hash codes, each element of
> one array must be compared with each element
> of another array.
>
> The resulting code is unnecessarily complicated
> in particular in view of the fact that
> on most Java implementations the
> System.identityHashCode() is in fact unique.
>
> It seems a total order on object references
> would be a great thing for such problems.
>
> Other ideas?
>
> Harald Kirsch



 
Reply With Quote
 
 
 
 
Faiser
Guest
Posts: n/a
 
      07-02-2004
> In Java, identity can be established by x==y,
> but sadly there is no total order defined
> on object references.

Perhaps, 'inconveniently' is more appropriate than sadly.

This notwithstanding, perhaps you could create a Comparator to work
something like:

public int compare( Object o1, Object o2 ) {
int hash1 = o1.hashCode(),
hash2 = o2.hashCode();


return ( hash1 > hash2 ? 1 :
( hash1 == hash2 ? 0 :
-1 ) );
}

Objects that do not implement Comparable could then be indexed
according to their natural or overridden hash.

-Faiser
 
Reply With Quote
 
Hemal Pandya
Guest
Posts: n/a
 
      07-06-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (Harald Kirsch) writes:

[....]
> It seems a total order on object references
> would be a great thing for such problems.
>
> Other ideas?


The second argument to a native method is a reference to the
object. in C terminology it is a pointer to an incomplete type (struct
_jobject). Can you convert this pointer to an java int value and use
for this purpose?

>
> Harald Kirsch

 
Reply With Quote
 
Dale King
Guest
Posts: n/a
 
      04-15-2006
Hello, Harald Kirsch!
You wrote:

> In my previous life, using C, the two arrays
> contained pointers to objects and I kept
> the arrays sorted according to the pointers'
> equivalent int value. Comparing the two arrays
> to check whether they contain identical objects
> could be done in O(n) where n is the length
> of the arrays.
>
> In Java, identity can be established by x==y,
> but sadly there is no total order defined
> on object references. Consequently I cannot
> keep the arrays sorted --- except in special
> cases where objects implement Comparable. As
> a result, the comparison becomes O(n^2).
>
> A half solution uses System.identityHashCode()
> to keep the arrays roughly sorted. Only within
> a run of equal hash codes, each element of
> one array must be compared with each element
> of another array.
>
> The resulting code is unnecessarily complicated
> in particular in view of the fact that
> on most Java implementations the
> System.identityHashCode() is in fact unique.
>
> It seems a total order on object references
> would be a great thing for such problems.
>
> Other ideas?


I agree and hve made such a suggestion before. A major whole in
the colletions API is that there is no sorted list. There is
SortedSet, but that does not allow duplicates. There is no way to
adapt SortedSet to allow objects with duplicate data because you
do not have a total ordering on the objects.
--
Dale King
My Blog: http://daleking.homedns.org/Blog
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
FAQ 4.43 How do I compute the difference of two arrays? How do I compute the intersection of two arrays? PerlFAQ Server Perl Misc 0 02-02-2011 05:00 AM
Compare, two identical numbers are not the same?! Justin C Perl Misc 8 07-04-2009 10:50 PM
Two identical Strings stored in two different object Neroku Java 12 02-12-2007 03:32 PM
How to compare two SOAP Envelope or two Document or two XML files GenxLogic Java 3 12-06-2006 08:41 PM
two arrays problem (although different from the other two arrays) Kev Jackson Ruby 2 03-29-2006 03:58 PM



Advertisments