How to compare two arrays for identical objects?

Discussion in 'Java' started by Harald Kirsch, Jul 2, 2004.

  1. 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
     
    Harald Kirsch, Jul 2, 2004
    #1
    1. Advertisements

  2. 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)
     
    Tobias Lehmann, Jul 2, 2004
    #2
    1. Advertisements

  3. Harald Kirsch

    Faiser Guest

    In Java, identity can be established by x==y,
    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
     
    Faiser, Jul 2, 2004
    #3
  4. Harald Kirsch

    Hemal Pandya Guest

    (Harald Kirsch) writes:

    [....]
    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?
     
    Hemal Pandya, Jul 6, 2004
    #4
  5. Harald Kirsch

    Dale King Guest

    Hello, Harald Kirsch!
    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, Apr 15, 2006
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.