Sorting Lists of byte arrays

Discussion in 'Java' started by mikew01, Dec 11, 2007.

  1. mikew01

    mikew01 Guest

    Hello, I need to compare 2 lists of byte arrays.
    I wanted to use something like Collections.sort then compare each
    array in the order they came out of the List but this will not work
    because a byte array object does not implement Comparable, so I'm
    doing this at present...

    <code>
    protected void compareDBVsIProds( List convertedProds, List
    iProducts )
    {
    int matches = iProducts.size();

    for( int i = 0; i < iProducts.size(); i++ )
    {
    byte[] iArr = ( byte[] ) iProducts.get( ( i ) );

    for( int j = 0; j < convertedProds.size(); j++ )
    {
    byte[] prodArr = ( byte[] )convertedProds.get( j );

    if( Arrays.equals( iArr, prodArr ) )
    {
    matches--;
    break;
    }
    }
    }

    if( matches != 0 )
    {
    String error = matches + " products have not been matched";
    throw new RuntimeException( error );
    }
    }
    </code>

    Could anyone suggest a neater way of achieving this task?

    TIA

    Mike.
     
    mikew01, Dec 11, 2007
    #1
    1. Advertisements

  2. Try:

    Collections.sort(myListOfByteArrays, new Comparator<byte[]> {
    // compares byte arrays using lexical ordering
    public int compare(byte[] arr1, byte[] arr2) {
    int len = Math.min(arr1.length, arr2.length);
    for(int i = 0; i < len; i++) {
    int cmp = arr1 - arr2;
    if (cmp != 0) { return cmp; }
    }
    return arr1.length - arr2.length;
    }
    });

    Warning: written directly in newsreader, not tested :)

    When you have sorted the lists, you can run through them, using
    a pair of iterators and see if they match, perhaps using the
    same comparator again.

    /L
     
    Lasse Reichstein Nielsen, Dec 11, 2007
    #2
    1. Advertisements

  3. mikew01

    Eric Sosman Guest

    It seems you don't care about the order of items in
    the two Lists, but only about their presence: a,b is
    to be considered "equal" to b,a. (In fact, it seems
    you want a,b,a to be "equal" to a,b. Stranger still,
    the code says that a,b is "equal" to a,b,c but that
    a,b,c is "unequal" to a,b -- are you sure you've coded
    what you actually intend?)

    That aside, you can certainly sort the Lists of
    byte arrays. There are two Collections.sort() methods:
    one that uses the natural order of collections of
    Comparable objects (which doesn't help you), but another
    which uses a Comparator object that you can supply.
    By sorting both Lists, you can turn the O(N*N) process
    shown above into an O(N*log(N)) process; whether this
    is or isn't worth while depends on the value of N and
    of the messy details hidden behind the Big-O's.

    It seems attractive to use a Set (where order doesn't
    matter) instead of a List (where it does), but that will
    require wrapping each byte array in a class with a little
    intelligence. Still, that may not be a drawback: Just
    how "raw" are these arrays supposed to be, anyhow? If
    they have some kind of significance, perhaps the wrapping
    class will turn out to have other uses anyhow.
     
    Eric Sosman, Dec 11, 2007
    #3
  4. mikew01

    Daniel Pitts Guest

    Use the Comparator method overloaded version of sort:

    Collections.sort(byteArrays, new Comparator<byte[]>() {
    public int compare(byte[] o1, byte[] o2) {
    // do your byte comparison here.
    }
    });
     
    Daniel Pitts, Dec 11, 2007
    #4
  5. mikew01

    Roedy Green Guest

    You can use a Comparator with Arrays.sort

    For sorting byte arrays, a Radixsort will be very quick. See
    http://mindprod.com/jgloss/radixsort.html
     
    Roedy Green, Dec 12, 2007
    #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.