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/05/03 15:37:48 UTC
svn commit: r1478785 [2/2] - in /lucene/dev/trunk: lucene/
lucene/core/src/java/org/apache/lucene/index/
lucene/core/src/java/org/apache/lucene/search/
lucene/core/src/java/org/apache/lucene/search/spans/
lucene/core/src/java/org/apache/lucene/util/ lu...
Modified: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java (original)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestCollectionUtil.java Fri May 3 13:37:45 2013
@@ -35,39 +35,20 @@ public class TestCollectionUtil extends
return Arrays.asList(a);
}
- public void testQuickSort() {
+ public void testIntroSort() {
for (int i = 0, c = atLeast(500); i < c; i++) {
List<Integer> list1 = createRandomList(2000), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.quickSort(list1);
+ CollectionUtil.introSort(list1);
Collections.sort(list2);
assertEquals(list2, list1);
list1 = createRandomList(2000);
list2 = new ArrayList<Integer>(list1);
- CollectionUtil.quickSort(list1, Collections.reverseOrder());
+ CollectionUtil.introSort(list1, Collections.reverseOrder());
Collections.sort(list2, Collections.reverseOrder());
assertEquals(list2, list1);
// reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.quickSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
- }
- }
-
- public void testMergeSort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- List<Integer> list1 = createRandomList(2000), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.mergeSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
-
- list1 = createRandomList(2000);
- list2 = new ArrayList<Integer>(list1);
- CollectionUtil.mergeSort(list1, Collections.reverseOrder());
- Collections.sort(list2, Collections.reverseOrder());
- assertEquals(list2, list1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.mergeSort(list1);
+ CollectionUtil.introSort(list1);
Collections.sort(list2);
assertEquals(list2, list1);
}
@@ -92,86 +73,30 @@ public class TestCollectionUtil extends
}
}
- public void testInsertionSort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- List<Integer> list1 = createRandomList(30), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.insertionSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
-
- list1 = createRandomList(30);
- list2 = new ArrayList<Integer>(list1);
- CollectionUtil.insertionSort(list1, Collections.reverseOrder());
- Collections.sort(list2, Collections.reverseOrder());
- assertEquals(list2, list1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.insertionSort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
- }
- }
-
- public void testBinarySort() {
- for (int i = 0, c = atLeast(500); i < c; i++) {
- List<Integer> list1 = createRandomList(30), list2 = new ArrayList<Integer>(list1);
- CollectionUtil.binarySort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
-
- list1 = createRandomList(30);
- list2 = new ArrayList<Integer>(list1);
- CollectionUtil.binarySort(list1, Collections.reverseOrder());
- Collections.sort(list2, Collections.reverseOrder());
- assertEquals(list2, list1);
- // reverse back, so we can test that completely backwards sorted array (worst case) is working:
- CollectionUtil.binarySort(list1);
- Collections.sort(list2);
- assertEquals(list2, list1);
- }
- }
-
public void testEmptyListSort() {
// should produce no exceptions
List<Integer> list = Arrays.asList(new Integer[0]); // LUCENE-2989
- CollectionUtil.quickSort(list);
- CollectionUtil.mergeSort(list);
+ CollectionUtil.introSort(list);
CollectionUtil.timSort(list);
- CollectionUtil.insertionSort(list);
- CollectionUtil.binarySort(list);
- CollectionUtil.quickSort(list, Collections.reverseOrder());
- CollectionUtil.mergeSort(list, Collections.reverseOrder());
+ CollectionUtil.introSort(list, Collections.reverseOrder());
CollectionUtil.timSort(list, Collections.reverseOrder());
- CollectionUtil.insertionSort(list, Collections.reverseOrder());
- CollectionUtil.binarySort(list, Collections.reverseOrder());
// check that empty non-random access lists pass sorting without ex (as sorting is not needed)
list = new LinkedList<Integer>();
- CollectionUtil.quickSort(list);
- CollectionUtil.mergeSort(list);
+ CollectionUtil.introSort(list);
CollectionUtil.timSort(list);
- CollectionUtil.insertionSort(list);
- CollectionUtil.binarySort(list);
- CollectionUtil.quickSort(list, Collections.reverseOrder());
- CollectionUtil.mergeSort(list, Collections.reverseOrder());
+ CollectionUtil.introSort(list, Collections.reverseOrder());
CollectionUtil.timSort(list, Collections.reverseOrder());
- CollectionUtil.insertionSort(list, Collections.reverseOrder());
- CollectionUtil.binarySort(list, Collections.reverseOrder());
}
public void testOneElementListSort() {
// check that one-element non-random access lists pass sorting without ex (as sorting is not needed)
List<Integer> list = new LinkedList<Integer>();
list.add(1);
- CollectionUtil.quickSort(list);
- CollectionUtil.mergeSort(list);
+ CollectionUtil.introSort(list);
CollectionUtil.timSort(list);
- CollectionUtil.insertionSort(list);
- CollectionUtil.binarySort(list);
- CollectionUtil.quickSort(list, Collections.reverseOrder());
- CollectionUtil.mergeSort(list, Collections.reverseOrder());
+ CollectionUtil.introSort(list, Collections.reverseOrder());
CollectionUtil.timSort(list, Collections.reverseOrder());
- CollectionUtil.insertionSort(list, Collections.reverseOrder());
- CollectionUtil.binarySort(list, Collections.reverseOrder());
}
}
Added: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestInPlaceMergeSorter.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestInPlaceMergeSorter.java?rev=1478785&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestInPlaceMergeSorter.java (added)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestInPlaceMergeSorter.java Fri May 3 13:37:45 2013
@@ -0,0 +1,36 @@
+package org.apache.lucene.util;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.junit.runner.RunWith;
+
+import com.carrotsearch.randomizedtesting.RandomizedRunner;
+
+@RunWith(RandomizedRunner.class)
+public class TestInPlaceMergeSorter extends BaseSortTestCase {
+
+ public TestInPlaceMergeSorter() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayInPlaceMergeSorter<Entry>(arr, ArrayUtil.<Entry>naturalComparator());
+ }
+
+}
Added: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestIntroSorter.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestIntroSorter.java?rev=1478785&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestIntroSorter.java (added)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestIntroSorter.java Fri May 3 13:37:45 2013
@@ -0,0 +1,32 @@
+package org.apache.lucene.util;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+public class TestIntroSorter extends BaseSortTestCase {
+
+ public TestIntroSorter() {
+ super(false);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayIntroSorter<Entry>(arr, ArrayUtil.<Entry>naturalComparator());
+ }
+
+}
Added: lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestTimSorter.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestTimSorter.java?rev=1478785&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestTimSorter.java (added)
+++ lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestTimSorter.java Fri May 3 13:37:45 2013
@@ -0,0 +1,31 @@
+package org.apache.lucene.util;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class TestTimSorter extends BaseSortTestCase {
+
+ public TestTimSorter() {
+ super(true);
+ }
+
+ @Override
+ public Sorter newSorter(Entry[] arr) {
+ return new ArrayTimSorter<Entry>(arr, ArrayUtil.<Entry>naturalComparator(), random().nextInt(arr.length));
+ }
+
+}
Modified: lucene/dev/trunk/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java (original)
+++ lucene/dev/trunk/lucene/facet/src/test/org/apache/lucene/facet/search/TestDrillSideways.java Fri May 3 13:37:45 2013
@@ -65,8 +65,8 @@ import org.apache.lucene.store.Directory
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.InfoStream;
-import org.apache.lucene.util.SorterTemplate;
import org.apache.lucene.util._TestUtil;
public class TestDrillSideways extends FacetTestCase {
@@ -875,9 +875,7 @@ public class TestDrillSideways extends F
// Naive (on purpose, to reduce bug in tester/gold):
// sort all ids, then return top N slice:
- new SorterTemplate() {
-
- private int pivot;
+ new InPlaceMergeSorter() {
@Override
protected void swap(int i, int j) {
@@ -901,26 +899,7 @@ public class TestDrillSideways extends F
}
}
- @Override
- protected void setPivot(int i) {
- pivot = ids[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- int counti = counts[pivot];
- int countj = counts[ids[j]];
- // Sort by count descending...
- if (counti > countj) {
- return -1;
- } else if (counti < countj) {
- return 1;
- } else {
- // ... then by ord ascending:
- return new BytesRef(values[pivot]).compareTo(new BytesRef(values[ids[j]]));
- }
- }
- }.mergeSort(0, ids.length-1);
+ }.sort(0, ids.length);
if (topN > ids.length) {
topN = ids.length;
Modified: lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java (original)
+++ lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenSources.java Fri May 3 13:37:45 2013
@@ -251,7 +251,7 @@ public class TokenSources {
if (unsortedTokens != null) {
tokensInOriginalOrder = unsortedTokens.toArray(new Token[unsortedTokens
.size()]);
- ArrayUtil.mergeSort(tokensInOriginalOrder, new Comparator<Token>() {
+ ArrayUtil.timSort(tokensInOriginalOrder, new Comparator<Token>() {
@Override
public int compare(Token t1, Token t2) {
if (t1.startOffset() == t2.startOffset()) return t1.endOffset()
Modified: lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java (original)
+++ lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TokenStreamFromTermPositionVector.java Fri May 3 13:37:45 2013
@@ -86,7 +86,7 @@ public final class TokenStreamFromTermPo
this.positionedTokens.add(token);
}
}
- CollectionUtil.mergeSort(this.positionedTokens, tokenComparator);
+ CollectionUtil.timSort(this.positionedTokens, tokenComparator);
int lastPosition = -1;
for (final Token token : this.positionedTokens) {
int thisPosition = token.getPositionIncrement();
Modified: lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java (original)
+++ lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/Passage.java Fri May 3 13:37:45 2013
@@ -19,8 +19,8 @@ package org.apache.lucene.search.posting
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.RamUsageEstimator;
-import org.apache.lucene.util.SorterTemplate;
/**
* Represents a passage (typically a sentence of the document).
@@ -64,7 +64,7 @@ public final class Passage {
final int starts[] = matchStarts;
final int ends[] = matchEnds;
final BytesRef terms[] = matchTerms;
- new SorterTemplate() {
+ new InPlaceMergeSorter() {
@Override
protected void swap(int i, int j) {
int temp = starts[i];
@@ -85,18 +85,7 @@ public final class Passage {
return Integer.compare(starts[i], starts[j]);
}
- @Override
- protected void setPivot(int i) {
- pivot = starts[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- return Integer.compare(pivot, starts[j]);
- }
-
- int pivot;
- }.mergeSort(0, numMatches-1);
+ }.sort(0, numMatches);
}
void reset() {
Modified: lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java (original)
+++ lucene/dev/trunk/lucene/highlighter/src/java/org/apache/lucene/search/postingshighlight/PostingsHighlighter.java Fri May 3 13:37:45 2013
@@ -48,7 +48,7 @@ import org.apache.lucene.search.Query;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.SorterTemplate;
+import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.UnicodeUtil;
/**
@@ -313,9 +313,8 @@ public class PostingsHighlighter {
// sort for sequential io
Arrays.sort(docids);
- new SorterTemplate() {
- String pivot;
-
+ new InPlaceMergeSorter() {
+
@Override
protected void swap(int i, int j) {
String tmp = fields[i];
@@ -330,18 +329,8 @@ public class PostingsHighlighter {
protected int compare(int i, int j) {
return fields[i].compareTo(fields[j]);
}
-
- @Override
- protected void setPivot(int i) {
- pivot = fields[i];
- }
-
- @Override
- protected int comparePivot(int j) {
- return pivot.compareTo(fields[j]);
- }
- }.mergeSort(0, fields.length-1);
+ }.sort(0, fields.length);
// pull stored data:
String[][] contents = loadFieldValues(searcher, fields, docids, maxLength);
Modified: lucene/dev/trunk/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java (original)
+++ lucene/dev/trunk/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java Fri May 3 13:37:45 2013
@@ -572,7 +572,7 @@ public class MemoryIndex {
entries[i] = iter.next();
}
- if (size > 1) ArrayUtil.quickSort(entries, termComparator);
+ if (size > 1) ArrayUtil.introSort(entries, termComparator);
return entries;
}
Modified: lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java (original)
+++ lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/CompoundFileExtractor.java Fri May 3 13:37:45 2013
@@ -87,7 +87,7 @@ public class CompoundFileExtractor {
cfr = new CompoundFileDirectory(dir, filename, IOContext.DEFAULT, false);
String [] files = cfr.listAll();
- ArrayUtil.mergeSort(files); // sort the array of filename so that the output is more readable
+ ArrayUtil.timSort(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/misc/src/java/org/apache/lucene/index/sorter/Sorter.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java (original)
+++ lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/Sorter.java Fri May 3 13:37:45 2013
@@ -22,7 +22,7 @@ import java.util.Comparator;
import org.apache.lucene.index.AtomicReader;
import org.apache.lucene.index.IndexReader;
-import org.apache.lucene.util.SorterTemplate;
+import org.apache.lucene.util.TimSorter;
import org.apache.lucene.util.packed.MonotonicAppendingLongBuffer;
/**
@@ -113,16 +113,17 @@ public abstract class Sorter {
}
};
- private static final class DocValueSorterTemplate extends SorterTemplate {
+ private static final class DocValueSorter extends TimSorter {
private final int[] docs;
private final Sorter.DocComparator comparator;
+ private final int[] tmp;
- private int pivot;
-
- public DocValueSorterTemplate(int[] docs, Sorter.DocComparator comparator) {
+ public DocValueSorter(int[] docs, Sorter.DocComparator comparator) {
+ super(docs.length / 64);
this.docs = docs;
this.comparator = comparator;
+ tmp = new int[docs.length / 64];
}
@Override
@@ -131,21 +132,31 @@ public abstract class Sorter {
}
@Override
- protected int comparePivot(int j) {
- return comparator.compare(pivot, docs[j]);
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = docs[i];
- }
-
- @Override
protected void swap(int i, int j) {
int tmpDoc = docs[i];
docs[i] = docs[j];
docs[j] = tmpDoc;
}
+
+ @Override
+ protected void copy(int src, int dest) {
+ docs[dest] = docs[src];
+ }
+
+ @Override
+ protected void save(int i, int len) {
+ System.arraycopy(docs, i, tmp, 0, len);
+ }
+
+ @Override
+ protected void restore(int i, int j) {
+ docs[j] = tmp[i];
+ }
+
+ @Override
+ protected int compareSaved(int i, int j) {
+ return comparator.compare(tmp[i], docs[j]);
+ }
}
/** Computes the old-to-new permutation over the given comparator. */
@@ -168,10 +179,10 @@ public abstract class Sorter {
docs[i] = i;
}
- SorterTemplate sorter = new DocValueSorterTemplate(docs, comparator);
+ DocValueSorter sorter = new DocValueSorter(docs, comparator);
// It can be common to sort a reader, add docs, sort it again, ... and in
// that case timSort can save a lot of time
- sorter.timSort(0, docs.length - 1); // docs is now the newToOld mapping
+ sorter.sort(0, docs.length); // docs is now the newToOld mapping
// The reason why we use MonotonicAppendingLongBuffer here is that it
// wastes very little memory if the index is in random order but can save
Modified: lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java (original)
+++ lucene/dev/trunk/lucene/misc/src/java/org/apache/lucene/index/sorter/SortingAtomicReader.java Fri May 3 13:37:45 2013
@@ -43,7 +43,7 @@ import org.apache.lucene.store.RAMOutput
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.SorterTemplate;
+import org.apache.lucene.util.TimSorter;
import org.apache.lucene.util.automaton.CompiledAutomaton;
/**
@@ -157,7 +157,7 @@ public class SortingAtomicReader extends
final DocsEnum inDocs = in.docs(newToOld(liveDocs), inReuse, flags);
final boolean withFreqs = indexOptions.compareTo(IndexOptions.DOCS_AND_FREQS) >=0 && (flags & DocsEnum.FLAG_FREQS) != 0;
- return new SortingDocsEnum(wrapReuse, inDocs, withFreqs, docMap);
+ return new SortingDocsEnum(docMap.size(), wrapReuse, inDocs, withFreqs, docMap);
}
@Override
@@ -184,7 +184,7 @@ public class SortingAtomicReader extends
// ask for everything. if that assumption changes in the future, we can
// factor in whether 'flags' says offsets are not required.
final boolean storeOffsets = indexOptions.compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS) >= 0;
- return new SortingDocsAndPositionsEnum(wrapReuse, inDocsAndPositions, docMap, storeOffsets);
+ return new SortingDocsAndPositionsEnum(docMap.size(), wrapReuse, inDocsAndPositions, docMap, storeOffsets);
}
}
@@ -295,34 +295,32 @@ public class SortingAtomicReader extends
static class SortingDocsEnum extends FilterDocsEnum {
- private static final class DocFreqSorterTemplate extends SorterTemplate {
+ private static final class DocFreqSorter extends TimSorter {
- private final int[] docs;
- private final int[] freqs;
+ private int[] docs;
+ private int[] freqs;
+ private final int[] tmpDocs;
+ private int[] tmpFreqs;
- private int pivot;
-
- public DocFreqSorterTemplate(int[] docs, int[] freqs) {
+ public DocFreqSorter(int maxDoc) {
+ super(maxDoc / 64);
+ this.tmpDocs = new int[maxDoc / 64];
+ }
+
+ public void reset(int[] docs, int[] freqs) {
this.docs = docs;
this.freqs = freqs;
+ if (freqs != null && tmpFreqs == null) {
+ tmpFreqs = new int[tmpDocs.length];
+ }
}
-
+
@Override
protected int compare(int i, int j) {
return docs[i] - docs[j];
}
@Override
- protected int comparePivot(int j) {
- return pivot - docs[j];
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = docs[i];
- }
-
- @Override
protected void swap(int i, int j) {
int tmpDoc = docs[i];
docs[i] = docs[j];
@@ -334,22 +332,60 @@ public class SortingAtomicReader extends
freqs[j] = tmpFreq;
}
}
+
+ @Override
+ protected void copy(int src, int dest) {
+ docs[dest] = docs[src];
+ if (freqs != null) {
+ freqs[dest] = freqs[src];
+ }
+ }
+
+ @Override
+ protected void save(int i, int len) {
+ System.arraycopy(docs, i, tmpDocs, 0, len);
+ if (freqs != null) {
+ System.arraycopy(freqs, i, tmpFreqs, 0, len);
+ }
+ }
+
+ @Override
+ protected void restore(int i, int j) {
+ docs[j] = tmpDocs[i];
+ if (freqs != null) {
+ freqs[j] = tmpFreqs[i];
+ }
+ }
+
+ @Override
+ protected int compareSaved(int i, int j) {
+ return tmpDocs[i] - docs[j];
+ }
}
-
+
+ private final int maxDoc;
+ private final DocFreqSorter sorter;
private int[] docs;
private int[] freqs;
private int docIt = -1;
private final int upto;
private final boolean withFreqs;
- SortingDocsEnum(SortingDocsEnum reuse, final DocsEnum in, boolean withFreqs, final Sorter.DocMap docMap) throws IOException {
+ SortingDocsEnum(int maxDoc, SortingDocsEnum reuse, final DocsEnum in, boolean withFreqs, final Sorter.DocMap docMap) throws IOException {
super(in);
+ this.maxDoc = maxDoc;
this.withFreqs = withFreqs;
if (reuse != null) {
+ if (reuse.maxDoc == maxDoc) {
+ sorter = reuse.sorter;
+ } else {
+ sorter = new DocFreqSorter(maxDoc);
+ }
docs = reuse.docs;
freqs = reuse.freqs; // maybe null
} else {
docs = new int[64];
+ sorter = new DocFreqSorter(maxDoc);
}
docIt = -1;
int i = 0;
@@ -378,7 +414,8 @@ public class SortingAtomicReader extends
}
// TimSort can save much time compared to other sorts in case of
// reverse sorting, or when sorting a concatenation of sorted readers
- new DocFreqSorterTemplate(docs, freqs).timSort(0, i - 1);
+ sorter.reset(docs, freqs);
+ sorter.sort(0, i);
upto = i;
}
@@ -422,38 +459,34 @@ public class SortingAtomicReader extends
static class SortingDocsAndPositionsEnum extends FilterDocsAndPositionsEnum {
/**
- * A {@link SorterTemplate} which sorts two parallel arrays of doc IDs and
+ * A {@link Sorter} which sorts two parallel arrays of doc IDs and
* offsets in one go. Everytime a doc ID is 'swapped', its correponding offset
* is swapped too.
*/
- private static final class DocOffsetSorterTemplate extends SorterTemplate {
+ private static final class DocOffsetSorter extends TimSorter {
- private final int[] docs;
- private final long[] offsets;
+ private int[] docs;
+ private long[] offsets;
+ private final int[] tmpDocs;
+ private final long[] tmpOffsets;
- private int pivot;
-
- public DocOffsetSorterTemplate(int[] docs, long[] offsets) {
+ public DocOffsetSorter(int maxDoc) {
+ super(maxDoc / 64);
+ this.tmpDocs = new int[maxDoc / 64];
+ this.tmpOffsets = new long[maxDoc / 64];
+ }
+
+ public void reset(int[] docs, long[] offsets) {
this.docs = docs;
this.offsets = offsets;
}
-
+
@Override
protected int compare(int i, int j) {
return docs[i] - docs[j];
}
@Override
- protected int comparePivot(int j) {
- return pivot - docs[j];
- }
-
- @Override
- protected void setPivot(int i) {
- pivot = docs[i];
- }
-
- @Override
protected void swap(int i, int j) {
int tmpDoc = docs[i];
docs[i] = docs[j];
@@ -463,8 +496,33 @@ public class SortingAtomicReader extends
offsets[i] = offsets[j];
offsets[j] = tmpOffset;
}
+
+ @Override
+ protected void copy(int src, int dest) {
+ docs[dest] = docs[src];
+ offsets[dest] = offsets[src];
+ }
+
+ @Override
+ protected void save(int i, int len) {
+ System.arraycopy(docs, i, tmpDocs, 0, len);
+ System.arraycopy(offsets, i, tmpOffsets, 0, len);
+ }
+
+ @Override
+ protected void restore(int i, int j) {
+ docs[j] = tmpDocs[i];
+ offsets[j] = tmpOffsets[i];
+ }
+
+ @Override
+ protected int compareSaved(int i, int j) {
+ return tmpDocs[i] - docs[j];
+ }
}
+ private final int maxDoc;
+ private final DocOffsetSorter sorter;
private int[] docs;
private long[] offsets;
private final int upto;
@@ -481,19 +539,26 @@ public class SortingAtomicReader extends
private final RAMFile file;
- SortingDocsAndPositionsEnum(SortingDocsAndPositionsEnum reuse, final DocsAndPositionsEnum in, Sorter.DocMap docMap, boolean storeOffsets) throws IOException {
+ SortingDocsAndPositionsEnum(int maxDoc, SortingDocsAndPositionsEnum reuse, final DocsAndPositionsEnum in, Sorter.DocMap docMap, boolean storeOffsets) throws IOException {
super(in);
+ this.maxDoc = maxDoc;
this.storeOffsets = storeOffsets;
if (reuse != null) {
docs = reuse.docs;
offsets = reuse.offsets;
payload = reuse.payload;
file = reuse.file;
+ if (reuse.maxDoc == maxDoc) {
+ sorter = reuse.sorter;
+ } else {
+ sorter = new DocOffsetSorter(maxDoc);
+ }
} else {
docs = new int[32];
offsets = new long[32];
payload = new BytesRef(32);
file = new RAMFile();
+ sorter = new DocOffsetSorter(maxDoc);
}
final IndexOutput out = new RAMOutputStream(file);
int doc;
@@ -510,7 +575,8 @@ public class SortingAtomicReader extends
i++;
}
upto = i;
- new DocOffsetSorterTemplate(docs, offsets).timSort(0, upto - 1);
+ sorter.reset(docs, offsets);
+ sorter.sort(0, upto);
out.close();
this.postingInput = new RAMInputStream("", file);
}
Modified: lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java (original)
+++ lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/spell/DirectSpellChecker.java Fri May 3 13:37:45 2013
@@ -376,7 +376,7 @@ public class DirectSpellChecker {
suggestions[index--] = suggestion;
}
- ArrayUtil.mergeSort(suggestions, Collections.reverseOrder(comparator));
+ ArrayUtil.timSort(suggestions, Collections.reverseOrder(comparator));
if (numSug < suggestions.length) {
SuggestWord trimmed[] = new SuggestWord[numSug];
System.arraycopy(suggestions, 0, trimmed, 0, numSug);
Modified: lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java (original)
+++ lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/BytesRefArray.java Fri May 3 13:37:45 2013
@@ -21,12 +21,12 @@ import java.util.Arrays;
import java.util.Comparator;
import org.apache.lucene.util.ArrayUtil;
-import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.ByteBlockPool;
+import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.BytesRefIterator;
import org.apache.lucene.util.Counter;
+import org.apache.lucene.util.IntroSorter;
import org.apache.lucene.util.RamUsageEstimator;
-import org.apache.lucene.util.SorterTemplate;
/**
* A simple append only random-access {@link BytesRef} array that stores full
@@ -120,7 +120,7 @@ public final class BytesRefArray {
for (int i = 0; i < orderedEntries.length; i++) {
orderedEntries[i] = i;
}
- new SorterTemplate() {
+ new IntroSorter() {
@Override
protected void swap(int i, int j) {
final int o = orderedEntries[i];
@@ -148,7 +148,7 @@ public final class BytesRefArray {
private final BytesRef pivot = new BytesRef(), scratch1 = new BytesRef(),
scratch2 = new BytesRef();
- }.quickSort(0, size() - 1);
+ }.sort(0, size());
return orderedEntries;
}
Modified: lucene/dev/trunk/solr/core/src/java/org/apache/solr/handler/AnalysisRequestHandlerBase.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/solr/core/src/java/org/apache/solr/handler/AnalysisRequestHandlerBase.java?rev=1478785&r1=1478784&r2=1478785&view=diff
==============================================================================
--- lucene/dev/trunk/solr/core/src/java/org/apache/solr/handler/AnalysisRequestHandlerBase.java (original)
+++ lucene/dev/trunk/solr/core/src/java/org/apache/solr/handler/AnalysisRequestHandlerBase.java Fri May 3 13:37:45 2013
@@ -211,7 +211,7 @@ public abstract class AnalysisRequestHan
final AttributeSource[] tokens = tokenList.toArray(new AttributeSource[tokenList.size()]);
// sort the tokens by absoulte position
- ArrayUtil.mergeSort(tokens, new Comparator<AttributeSource>() {
+ ArrayUtil.timSort(tokens, new Comparator<AttributeSource>() {
@Override
public int compare(AttributeSource a, AttributeSource b) {
return arrayCompare(