You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by us...@apache.org on 2011/05/03 15:07:25 UTC
svn commit: r1099041 - in /lucene/dev/trunk/lucene:
contrib/highlighter/src/java/org/apache/lucene/search/highlight/
src/java/org/apache/lucene/index/ src/java/org/apache/lucene/search/
src/java/org/apache/lucene/search/spans/ src/java/org/apache/lucen...
Author: uschindler
Date: Tue May 3 13:07:24 2011
New Revision: 1099041
URL: http://svn.apache.org/viewvc?rev=1099041&view=rev
Log:
LUCENE-3054: fix remaining quickSort
Modified:
lucene/dev/trunk/lucene/contrib/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java
lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/IndexReader.java
lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/MultiPhraseQuery.java
lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/PhraseQuery.java
lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/TopTermsRewrite.java
lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/SorterTemplate.java
Modified: lucene/dev/trunk/lucene/contrib/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/contrib/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/contrib/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java (original)
+++ lucene/dev/trunk/lucene/contrib/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java Tue May 3 13:07:24 2011
@@ -231,7 +231,7 @@ public class TokenSources {
if (unsortedTokens != null) {
tokensInOriginalOrder = unsortedTokens.toArray(new Token[unsortedTokens
.size()]);
- ArrayUtil.quickSort(tokensInOriginalOrder, new Comparator<Token>() {
+ ArrayUtil.mergeSort(tokensInOriginalOrder, new Comparator<Token>() {
public int compare(Token t1, Token t2) {
if (t1.startOffset() == t2.startOffset())
return t1.endOffset() - t2.endOffset();
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/IndexReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/IndexReader.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/IndexReader.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/IndexReader.java Tue May 3 13:07:24 2011
@@ -1420,7 +1420,7 @@ public abstract class IndexReader implem
cfr = new CompoundFileReader(dir, filename);
String [] files = cfr.listAll();
- ArrayUtil.quickSort(files); // sort the array of filename so that the output is more readable
+ ArrayUtil.mergeSort(files); // sort the array of filename so that the output is more readable
for (int i = 0; i < files.length; ++i) {
long len = cfr.fileLength(files[i]);
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/MultiPhraseQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/MultiPhraseQuery.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/MultiPhraseQuery.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/MultiPhraseQuery.java Tue May 3 13:07:24 2011
@@ -219,7 +219,7 @@ public class MultiPhraseQuery extends Qu
// sort by increasing docFreq order
if (slop == 0) {
- ArrayUtil.quickSort(postingsFreqs);
+ ArrayUtil.mergeSort(postingsFreqs);
}
if (slop == 0) {
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/PhraseQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/PhraseQuery.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/PhraseQuery.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/PhraseQuery.java Tue May 3 13:07:24 2011
@@ -234,7 +234,7 @@ public class PhraseQuery extends Query {
// sort by increasing docFreq order
if (slop == 0) {
- ArrayUtil.quickSort(postingsFreqs);
+ ArrayUtil.mergeSort(postingsFreqs);
}
if (slop == 0) { // optimize exact case
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/TopTermsRewrite.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/TopTermsRewrite.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/TopTermsRewrite.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/TopTermsRewrite.java Tue May 3 13:07:24 2011
@@ -134,7 +134,7 @@ public abstract class TopTermsRewrite<Q
final Term placeholderTerm = new Term(query.field);
final Q q = getTopLevelQuery();
final ScoreTerm[] scoreTerms = stQueue.toArray(new ScoreTerm[stQueue.size()]);
- ArrayUtil.quickSort(scoreTerms, scoreTermSortByTermComp);
+ ArrayUtil.mergeSort(scoreTerms, scoreTermSortByTermComp);
for (final ScoreTerm st : scoreTerms) {
final Term term = placeholderTerm.createTerm(st.bytes);
assert reader.docFreq(term) == st.termState.docFreq() : "reader DF is " + reader.docFreq(term) + " vs " + st.termState.docFreq();
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java Tue May 3 13:07:24 2011
@@ -190,7 +190,7 @@ public class NearSpansOrdered extends Sp
/** Advance the subSpans to the same document */
private boolean toSameDoc() throws IOException {
- ArrayUtil.quickSort(subSpansByDoc, spanDocComparator);
+ ArrayUtil.mergeSort(subSpansByDoc, spanDocComparator);
int firstIndex = 0;
int maxDoc = subSpansByDoc[subSpansByDoc.length - 1].doc();
while (subSpansByDoc[firstIndex].doc() != maxDoc) {
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/SorterTemplate.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/SorterTemplate.java?rev=1099041&r1=1099040&r2=1099041&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/SorterTemplate.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/SorterTemplate.java Tue May 3 13:07:24 2011
@@ -30,7 +30,6 @@ package org.apache.lucene.util;
public abstract class SorterTemplate {
private static final int MERGESORT_THRESHOLD = 12;
- private static final int MERGE_TO_QUICKSORT_THRESHOLD = 40;
private static final int QUICKSORT_THRESHOLD = 7;
/** Implement this method, that swaps slots {@code i} and {@code j} in your data */
@@ -63,17 +62,26 @@ public abstract class SorterTemplate {
/** Sorts via in-place, but unstable, QuickSort algorithm.
* For small collections falls back to {@link #insertionSort(int,int)}. */
- public final void quickSort(int lo, int hi) {
- quickSort(lo, hi, MERGE_TO_QUICKSORT_THRESHOLD);
+ public final void quickSort(final int lo, final int hi) {
+ if (hi <= lo) return;
+ // from Integer's Javadocs: ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)
+ quickSort(lo, hi, (Integer.SIZE - Integer.numberOfLeadingZeros(hi - lo)) << 1);
}
private void quickSort(int lo, int hi, int maxDepth) {
+ // fall back to insertion when array has short length
final int diff = hi - lo;
if (diff <= QUICKSORT_THRESHOLD) {
insertionSort(lo, hi);
return;
}
+ // fall back to merge sort when recursion depth gets too big
+ if (--maxDepth == 0) {
+ mergeSort(lo, hi);
+ return;
+ }
+
final int mid = lo + (diff >>> 1);
if (compare(lo, mid) > 0) {
@@ -106,16 +114,8 @@ public abstract class SorterTemplate {
}
}
- // fall back to merge sort when recursion depth gets too big
- if (maxDepth == 0) {
- // for testing: new Exception("Hit recursion depth limit").printStackTrace();
- mergeSort(lo, left);
- mergeSort(left + 1, hi);
- } else {
- --maxDepth;
- quickSort(lo, left, maxDepth);
- quickSort(left + 1, hi, maxDepth);
- }
+ quickSort(lo, left, maxDepth);
+ quickSort(left + 1, hi, maxDepth);
}
/** Sorts via stable in-place MergeSort algorithm