How to compare two arrays for identical objects?

[Harald Kirsch]

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

 

[Tobias Lehmann]

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)

 

[Faiser]

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

 

[Hemal Pandya]

(e-mail address 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?

 

[Dale King]

Hello, Harald Kirsch!

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.