From 76139ef711627a3176736af47272ff55be62e720 Mon Sep 17 00:00:00 2001 From: gmungoc Date: Tue, 4 Nov 2014 09:10:14 +0000 Subject: [PATCH] JAL-1152 annotation sort algorithm optimisation --- src/jalview/analysis/AnnotationSorter.java | 34 +++++++++++- test/jalview/analysis/AnnotationSorterTest.java | 65 ++++++++++++++++++----- 2 files changed, 83 insertions(+), 16 deletions(-) diff --git a/src/jalview/analysis/AnnotationSorter.java b/src/jalview/analysis/AnnotationSorter.java index 28fa1f8..a5d2164 100644 --- 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 sequenceIndices = new HashMap(); + /** * 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 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 --- 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: + *
    + *
  • set up in sequence order, with randomly assigned labels from a limited + * range
    • + *
  • sort by label and sequence order, report timing
    • + *
  • resort by sequence and label, report timing
    • + *
  • resort by label and sequence, report timing
    • + *
+ * + * @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"); } -- 1.7.10.2