You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2013/03/27 21:14:04 UTC
svn commit: r1461834 - in /lucene/dev/trunk/lucene/core/src:
java/org/apache/lucene/util/ArrayUtil.java
java/org/apache/lucene/util/CollectionUtil.java
java/org/apache/lucene/util/SorterTemplate.java
test/org/apache/lucene/util/TestSorterTemplate.java
Author: jpountz
Date: Wed Mar 27 20:14:04 2013
New Revision: 1461834
URL: http://svn.apache.org/r1461834
Log:
LUCENE-4875: Make SorterTemplate.mergeSort run in linear time on sorted (sub-)arrays.
Modified:
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SorterTemplate.java
lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSorterTemplate.java
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java?rev=1461834&r1=1461833&r2=1461834&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java Wed Mar 27 20:14:04 2013
@@ -673,10 +673,7 @@ public final class ArrayUtil {
while (i < len1) {
a[dest++] = tmp[i++];
}
- while (j < hi) {
- a[dest++] = a[j++];
- }
- assert dest == hi;
+ assert j == dest;
}
@Override
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java?rev=1461834&r1=1461833&r2=1461834&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/CollectionUtil.java Wed Mar 27 20:14:04 2013
@@ -101,10 +101,7 @@ public final class CollectionUtil {
while (i < len1) {
list.set(dest++, tmp[i++]);
}
- while (j < hi) {
- list.set(dest++, list.get(j++));
- }
- assert dest == hi;
+ assert j == dest;
}
@Override
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SorterTemplate.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SorterTemplate.java?rev=1461834&r1=1461833&r2=1461834&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SorterTemplate.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/SorterTemplate.java Wed Mar 27 20:14:04 2013
@@ -222,7 +222,7 @@ public abstract class SorterTemplate {
final int l = runBase(i+1);
final int pivot = runBase(i);
final int h = runEnd(i);
- merge(l, pivot, h, pivot - l, h - pivot);
+ runMerge(l, pivot, h, pivot - l, h - pivot);
for (int j = i + 1; j > 0; --j) {
setRunEnd(j, runEnd(j-1));
}
@@ -340,22 +340,43 @@ public abstract class SorterTemplate {
mergeSort(lo, mid);
mergeSort(mid, hi);
- merge(lo, mid, hi, mid - lo, hi - mid);
+ runMerge(lo, mid, hi, mid - lo, hi - mid);
}
- /** Merge the slices [lo-pivot[ (of length len1) and [pivot-hi[ (of length
- * len2) which are already sorted. This method merges in-place but can be
- * extended to provide a faster implementation using extra memory. */
- protected void merge(int lo, int pivot, int hi, int len1, int len2) {
+ /** Sort out trivial cases and reduce the scope of the merge as much as
+ * possible before calling {@link #merge}/ */
+ private void runMerge(int lo, int pivot, int hi, int len1, int len2) {
if (len1 == 0 || len2 == 0) {
return;
}
+ setPivot(pivot - 1);
+ if (comparePivot(pivot) <= 0) {
+ // all values from the first run are below all values from the 2nd run
+ // this shortcut makes mergeSort run in linear time on sorted arrays
+ return;
+ }
+ while (comparePivot(hi - 1) <= 0) {
+ --hi;
+ --len2;
+ }
+ setPivot(pivot);
+ while (comparePivot(lo) >= 0) {
+ ++lo;
+ --len1;
+ }
if (len1 + len2 == 2) {
- if (compare(pivot, lo) < 0) {
- swap(pivot, lo);
- }
+ assert len1 == len2;
+ assert compare(lo, pivot) > 0;
+ swap(pivot, lo);
return;
}
+ merge(lo, pivot, hi, len1, len2);
+ }
+
+ /** Merge the slices [lo-pivot[ (of length len1) and [pivot-hi[ (of length
+ * len2) which are already sorted. This method merges in-place but can be
+ * extended to provide a faster implementation using extra memory. */
+ protected void merge(int lo, int pivot, int hi, int len1, int len2) {
int first_cut, second_cut;
int len11, len22;
if (len1 > len2) {
@@ -371,8 +392,8 @@ public abstract class SorterTemplate {
}
rotate(first_cut, pivot, second_cut);
final int new_mid = first_cut + len22;
- merge(lo, first_cut, new_mid, len11, len22);
- merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
+ runMerge(lo, first_cut, new_mid, len11, len22);
+ runMerge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
}
private void rotate(int lo, int mid, int hi) {
Modified: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSorterTemplate.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSorterTemplate.java?rev=1461834&r1=1461833&r2=1461834&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSorterTemplate.java (original)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestSorterTemplate.java Wed Mar 27 20:14:04 2013
@@ -62,6 +62,18 @@ public class TestSorterTemplate extends
return compareValues(pivot, arr[j]);
}
+ @Override
+ protected void merge(int lo, int pivot, int hi, int len1, int len2) {
+ // timSort and mergeSort should call runMerge to sort out trivial cases
+ assertTrue(len1 >= 1);
+ assertTrue(len2 >= 1);
+ assertTrue(len1 + len2 >= 3);
+ assertTrue(compare(lo, pivot) > 0);
+ assertTrue(compare(pivot - 1, hi - 1) > 0);
+ assertFalse(compare(pivot - 1, pivot) <= 0);
+ super.merge(lo, pivot, hi, len1, len2);
+ }
+
}
void testSort(int[] intArr) {