Sorting an ArrayList by a Split Value [closed]

Question

I am attempting to create an list which should be sorted by a particular field in a colon separated string. I have an array of strings with the following values:

name1:535
name2:697

After sorting this list, I would have it sorted by the number in the second field:

name2:697
name1:535

How should I go about doing this, are there any issues I should be aware of when sorting this List of Strings?

Answer 1

The naive answer is to have a type that has a String value in it that does the work in compareTo() from the comparable interface.

The code would look something like this...

The problem with this is that it is doing much more work than is needed. A simple test:

public class Thingy implements Comparable<Thingy> {
    double value;
    public Thingy(double arg) {
        value = arg;
    }

    @Override
    public int compareTo(Thingy thingy) {
        Global.count++;
        return Double.valueOf(value).compareTo(thingy.value);
    }
}

public class Global {
    public static int count;
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Thingy> things = new ArrayList<Thingy>();
        for(int i = 0; i < 1000; i++) {
            things.add(new Thingy(Math.random()));
        }
        Collections.sort(things);
        System.out.println(Global.count);
    }
}

shows that compareTo() was called 9015 times. If one is doing any repeated calculation in compareTo() it is being called much more than it needs to and the work it does is unnecessary.

Coming from a perl background, one of the idiomatic calls is the Schwartzian transform - the "sort based on a computation" is something that is quickly recognized. In this code, one does:

@sorted = map  { $_->[0] }
          sort { $a->[1] <=> $b->[1] }
          map  { [$_, split($_)[0]] }
               @unsorted;

While the comparison is being called many times, it is being done on a stored value rather than a (re)computed value. See also Memoization.

In Java, one would likely have the constructor for the class break the string up into the component parts, and sort based on the parts rather than the whole.

---

If you are dealing with unique values to be sorted on (balance isn't likely unique but I'm explaining it anyways), one could use a SortedMap - just insert the key and value. If the key already has a natural ordering to it (Integers, Strings and the like), no more work need be done. You've got a sorted structure that has quite a bit of additional things that you may find useful when you need them (which actually come from NavigableMap, but the TreeMap and the SkipListMap are a NavigableMap in addition to being a SortedMap).

One could create a TreeMap with constructor that you pass a Comparator<String> into (javadoc for the constructor and javadoc for Comparator) and do the work on the String to do the ordering, though this could suffer from the problems of doing repeated calculations in the compareTo() method that I mentioned above. (An example where it doesn't is a Z-A sorted TreeMap as described in this question - one gets the general idea though - the general solution can be seen here).

---

If what you have isn't unique, you can still use it in a SortedMap structure, just that the value instead of being a String is a Set of Strings.

This then means two step adds (if the key doesn't exist, create it and then create the set, and then add the value to the set) and lookups (if the key exists, check to see if the value exists in the set).

It would be sensible to wrap that work in a class of its own so that you don't have copied boilerplate code for doing the multi-step add and lookup in multiple spots.

---

If you just have an array that you are going to sort once and then use, and be done with it and the extensibility of having an object (the name:balance represents an object that is more interesting than just a string), you could use the Comparator mentioned above as a parameter for the Collections.sort(List, Comparator) (javadoc). Remember that for sizable lists the number of invocations to extract the field to compare on from a is much more than calculating it once and storing it in an associated object.