JAL-1152 annotation sort algorithm optimisation

diff --git a/src/jalview/analysis/AnnotationSorter.java b/src/jalview/analysis/AnnotationSorter.java
index 28fa1f8..a5d2164 100644 (file)
--- a/src/jalview/analysis/AnnotationSorter.java
+++ b/src/jalview/analysis/AnnotationSorter.java
@@ -6,6 +6,8 @@ import jalview.datamodel.SequenceI;
 
 import java.util.Arrays;
 import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Map;
 
 /**
  * A helper class to sort all annotations associated with an alignment in
@@ -56,10 +58,15 @@ public class AnnotationSorter
     }
   }
 
+  // the alignment with respect to which annotations are sorted
   private final AlignmentI alignment;
 
+  // user preference for placement of non-sequence annotations
   private boolean showAutocalcAbove;
 
+  // working map of sequence index in alignment
+  private final Map<SequenceI, Integer> sequenceIndices = new HashMap<SequenceI, Integer>();
+
   /**
    * Constructor given an alignment and the location (top or bottom) of
    * Consensus and similar.
@@ -202,6 +209,9 @@ public class AnnotationSorter
   public void sort(AlignmentAnnotation[] alignmentAnnotations,
           SequenceAnnotationOrder order)
   {
+    // cache 'alignment sequence position' for the annotations
+    saveSequenceIndices(alignmentAnnotations);
+
     Comparator<? super AlignmentAnnotation> comparator = getComparator(order);
 
     if (alignmentAnnotations != null)
@@ -214,6 +224,26 @@ public class AnnotationSorter
   }
 
   /**
+   * Calculate and save in a temporary map the position of each annotation's
+   * sequence (if it has one) in the alignment. Faster to do this once than for
+   * every annotation comparison.
+   * 
+   * @param alignmentAnnotations
+   */
+  private void saveSequenceIndices(
+          AlignmentAnnotation[] alignmentAnnotations)
+  {
+    sequenceIndices.clear();
+    for (AlignmentAnnotation ann : alignmentAnnotations) {
+      SequenceI seq = ann.sequenceRef;
+      if (seq != null) {
+        int index = AlignmentUtils.getSequenceIndex(alignment, seq);
+        sequenceIndices.put(seq, index);
+      }
+    }
+  }
+
+  /**
    * Get the comparator for the specified sort order.
    * 
    * @param order
@@ -299,8 +329,8 @@ public class AnnotationSorter
       return showAutocalcAbove ? 1 : -1;
     }
     // get sequence index - but note -1 means 'at end' so needs special handling
-    int index1 = AlignmentUtils.getSequenceIndex(alignment, seq1);
-    int index2 = AlignmentUtils.getSequenceIndex(alignment, seq2);
+    int index1 = sequenceIndices.get(seq1);
+    int index2 = sequenceIndices.get(seq2);
     if (index1 == index2)
     {
       return 0;

diff --git a/test/jalview/analysis/AnnotationSorterTest.java b/test/jalview/analysis/AnnotationSorterTest.java
index ba2162d..239eb4c 100644 (file)
--- a/test/jalview/analysis/AnnotationSorterTest.java
+++ b/test/jalview/analysis/AnnotationSorterTest.java
@@ -1,7 +1,6 @@
 package jalview.analysis;
 
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
 import jalview.analysis.AnnotationSorter.SequenceAnnotationOrder;
 import jalview.datamodel.Alignment;
 import jalview.datamodel.AlignmentAnnotation;
@@ -229,9 +228,19 @@ public class AnnotationSorterTest
   @Test
   public void testSort_timingPresorted()
   {
-    final long targetTime = 100; // ms
-    final int numSeqs = 10000;
-    final int numAnns = 20000;
+    testTiming_presorted(50, 100);
+    testTiming_presorted(500, 1000);
+    testTiming_presorted(5000, 10000);
+  }
+
+  /**
+   * Test timing to sort annotations already in the sort order.
+   * 
+   * @param numSeqs
+   * @param numAnns
+   */
+  private void testTiming_presorted(final int numSeqs, final int numAnns)
+  {
     al = buildAlignment(numSeqs);
     anns = buildAnnotations(numAnns);
 
@@ -254,18 +263,28 @@ public class AnnotationSorterTest
     System.out.println("Timing test for presorted " + numSeqs
             + " sequences and "
             + numAnns + " annotations took " + elapsed + "ms");
-    assertTrue("Sort took more than " + targetTime + "ms",
-            elapsed <= targetTime);
   }
 
   /**
-   * Timing test for sorting randomly sorted annotations
+   * Timing tests for sorting randomly sorted annotations for various sizes.
    */
   @Test
   public void testSort_timingUnsorted()
   {
-    final int numSeqs = 2000;
-    final int numAnns = 4000;
+    testTiming_unsorted(50, 100);
+    testTiming_unsorted(500, 1000);
+    testTiming_unsorted(5000, 10000);
+  }
+
+  /**
+   * Generate annotations randomly sorted with respect to sequences, and time
+   * sorting.
+   * 
+   * @param numSeqs
+   * @param numAnns
+   */
+  private void testTiming_unsorted(final int numSeqs, final int numAnns)
+  {
     al = buildAlignment(numSeqs);
     anns = buildAnnotations(numAnns);
 
@@ -296,8 +315,26 @@ public class AnnotationSorterTest
   @Test
   public void testSort_timingSemisorted()
   {
-    final int numSeqs = 2000;
-    final int numAnns = 4000;
+    testTiming_semiSorted(50, 100);
+    testTiming_semiSorted(500, 1000);
+    testTiming_semiSorted(5000, 10000);
+  }
+
+  /**
+   * Mimic 'semi-sorted' annotations:
+   * <ul>
+   * <li>set up in sequence order, with randomly assigned labels from a limited
+   * range</li>
+   * <li>sort by label and sequence order, report timing</li>
+   * <li>resort by sequence and label, report timing</li>
+   * <li>resort by label and sequence, report timing</li>
+   * </ul>
+   * 
+   * @param numSeqs
+   * @param numAnns
+   */
+  private void testTiming_semiSorted(final int numSeqs, final int numAnns)
+  {
     al = buildAlignment(numSeqs);
     anns = buildAnnotations(numAnns);
 
@@ -320,7 +357,7 @@ public class AnnotationSorterTest
     testee.sort(anns, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
     long endTime = System.currentTimeMillis();
     long elapsed = endTime - startTime;
-    System.out.println("Sort by type for semisorted " + numSeqs
+    System.out.println("Sort by label for semisorted " + numSeqs
             + " sequences and "
             + numAnns + " annotations took " + elapsed + "ms");
 
@@ -333,12 +370,12 @@ public class AnnotationSorterTest
             + " sequences and " + numAnns + " annotations took " + elapsed
             + "ms");
 
-    // now resort by type
+    // now resort by label
     startTime = System.currentTimeMillis();
     testee.sort(anns, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
     endTime = System.currentTimeMillis();
     elapsed = endTime - startTime;
-    System.out.println("Resort by type for semisorted " + numSeqs
+    System.out.println("Resort by label for semisorted " + numSeqs
             + " sequences and " + numAnns + " annotations took " + elapsed
             + "ms");
   }