Java Collection Performane Tunning Tips for Online Challenge.

Java-performance-tunning.md

Based on Java 7.

Sorting

There are two built-in sort() methods, java.util.Arrays.sort() and java.util.Collections.sot(). Typically, we use the first one to sort primitive type and the later one to sort Objects.

For primitive type, the sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

For Objects, the implementation was adapted from Tim Peters's list sort for Python (TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

Use built-in sort() methods is also a good strategy while doing some algorithm puzzles, please notice that user defined comparator may affect the result if you use some loops inside.

Searching

Like sorting, Java also provides two binarySearch() methods for primitive type and object. For primitive type, use java.util.Arrays.binarySearch(), and for object, use java.util.Collection.binarySearch() with user defined comparator. Here are two snippets:

// Primitive Type
System.out.print(java.util.Arrays.binarySearch(new int[]{1, 2, 3, 4}, 3);
System.out.println(java.util.Arrays.binarySearch(new double[]{1.1, 2.2, 3.3, 4.4}, 3.3));
>> 2 2

For object, you need to implement you own comparator.

public class SomeClass {
    private static Comparator<String> comparator = new Comparator<String>() {
        @Override
        public int compare(String s1, String s2) {
            return s1.compareTo(s2);
        }
    };
    ...
    List<String> lst = new ArrayList<String>();
    lst.add("1");
    lst.add("2");
    lst.add("3");
    System.out.println(java.util.Collections.binarySearch(lst, "3", comparator));
    ...
  }
>> 2