You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by gs...@apache.org on 2009/11/23 16:14:38 UTC
svn commit: r883365 [10/47] - in /lucene/mahout/trunk: ./ examples/ matrix/
matrix/src/ matrix/src/main/ matrix/src/main/java/
matrix/src/main/java/org/ matrix/src/main/java/org/apache/
matrix/src/main/java/org/apache/mahout/ matrix/src/main/java/org/a...
Added: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java?rev=883365&view=auto
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java (added)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java Mon Nov 23 15:14:26 2009
@@ -0,0 +1,276 @@
+/*
+Copyright � 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.colt;
+
+/**
+Generically reorders (permutes) arbitrary shaped data (for example, an array, three arrays, a 2-d matrix, two linked lists) using an <i>in-place</i> swapping algorithm.
+Imagine having a couple of apples. For some reason you decide to reorder them. The green one before the red one. The pale one after the shiny one, etc. This class helps to do the job.
+<p>
+This class swaps elements around, in a way that avoids stumbling over its own feet:
+Let <tt>before</tt> be the generic data before calling the reordering method.
+Let <tt>after</tt> be the generic data after calling the reordering method.
+Then there holds <tt>after[i] == before[indexes[i]]</tt>.
+<p>
+Similar to {@link GenericSorting}, this class has no idea what kind of data it is reordering.
+It can decide to swap the data at index <tt>a</tt> with the data at index <tt>b</tt>.
+It calls a user provided {@link org.apache.mahout.colt.Swapper} object that knows how to swap the data of these indexes.
+<p>
+For convenience, some non-generic variants are also provided.
+Further a method to generate the p-th lexicographical permutation indexes.
+<p>
+<b>Example:</b>
+<table>
+<td class="PRE">
+<pre>
+Reordering
+[A,B,C,D,E] with indexes [0,4,2,3,1] yields
+[A,E,C,D,B]
+In other words, in the reordered list, we first have the element at old index 0, then the one at old index 4, then the ones at old indexes 2,3,1.
+g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1].
+
+Reordering
+[A,B,C,D,E] with indexes [0,4,1,2,3] yields
+[A,E,B,C,D]
+In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
+</pre>
+</td>
+</table>
+<p>
+Here are some example swappers:
+<table>
+<td class="PRE">
+<pre>
+// a swapper knows how to swap two indexes (a,b)
+
+// reordering an array
+Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ String tmp; // reordering String[]
+ // int tmp; // reordering int[]
+ tmp = array[a]; array[a] = array[b]; array[b] = tmp;
+ }
+};
+
+// reordering a list
+Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ Object tmp;
+ tmp = list.get(a);
+ list.set(a, list.get(b));
+ list.set(b, tmp);
+ }
+};
+
+// reordering the rows of a 2-d matrix (see {@link org.apache.mahout.colt.matrix})
+Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ matrix.viewRow(a).swap(matrix.viewRow(b));
+ }
+};
+
+// reordering the columns of a 2-d matrix
+Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ matrix.viewColumn(a).swap(matrix.viewColumn(b));
+ }
+};
+</pre>
+</td>
+</table>
+
+@see org.apache.mahout.colt.Swapper
+@see org.apache.mahout.colt.GenericSorting
+
+@author wolfgang.hoschek@cern.ch
+@version 1.0, 10-Oct-99
+*/
+/**
+ * @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
+ */
+@Deprecated
+public class GenericPermuting extends Object {
+/**
+ * Makes this class non instantiable, but still let's others inherit from it.
+ */
+protected GenericPermuting() {}
+/**
+Returns the <tt>p</tt>-th permutation of the sequence <tt>[0,1,...,N-1]</tt>.
+A small but smart and efficient routine, ported from <A HREF="http://www.hep.net/wwwmirrors/cernlib/CNASDOC/shortwrups_html3/node255.html"> Cernlib</A>.
+The <A HREF="ftp://asisftp.cern.ch/cernlib/share/pro/src/mathlib/gen/v/permu.F"> Fortran source</A>.
+A sequence of <tt>N</tt> distinct elements has <tt>N!</tt> permutations, which are enumerated in lexicographical order <tt>1 .. N!</tt>.
+<p>
+This is, for example, useful for Monte-Carlo-tests where one might want to compute <tt>k</tt> distinct and random permutations of a sequence, obtaining <tt>p</tt> from {@link org.apache.mahout.jet.random.sampling} without replacement or a random engine like {@link org.apache.mahout.jet.random.engine.MersenneTwister}.
+<br>
+Note: When <tt>N!</tt> exceeds the 64-bit range (i.e. for <tt>N > 20</tt>), this method has <i>different</i> behaviour: it makes a sequence <tt>[0,1,...,N-1]</tt> and randomizes it, seeded with parameter <tt>p</tt>.
+<p>
+<b>Examples:</b>
+<pre>
+http://www.hep.net/wwwmirrors/cernlib/CNASDOC/shortwrups_html3/node255.html
+// exactly lexicographically enumerated (ascending)
+permutation(1,3) --> [ 0,1,2 ]
+permutation(2,3) --> [ 0,2,1 ]
+permutation(3,3) --> [ 1,0,2 ]
+permutation(4,3) --> [ 1,2,0 ]
+permutation(5,3) --> [ 2,0,1 ]
+permutation(6,3) --> [ 2,1,0 ]
+permutation(1 ,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
+permutation(2 ,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 18]
+permutation(1000000,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 17, 18, 13, 19, 11, 15, 14, 16, 10]
+permutation(20! -2 ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0]
+permutation(20! -1 ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1]
+permutation(20! ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
+<br>
+// not exactly enumerated, rather randomly shuffled
+permutation(1,21) --> [18, 20, 11, 0, 15, 1, 19, 13, 3, 6, 16, 17, 9, 5, 12, 4, 7, 14, 8, 10, 2]
+permutation(2,21) --> [1, 9, 4, 16, 14, 13, 11, 20, 10, 8, 18, 0, 15, 3, 17, 5, 12, 2, 6, 7, 19]
+permutation(3,21) --> [12, 0, 19, 1, 20, 5, 8, 16, 6, 14, 2, 4, 3, 17, 11, 13, 9, 10, 15, 18, 7]
+</pre>
+
+@param p the lexicographical ordinal number of the permutation to be computed.
+@param N the length of the sequence to be generated.
+@return the <tt>p</tt>-th permutation.
+@throws IllegalArgumentException if <tt>p < 1 || N < 0 || p > N!</tt>.
+*/
+public static int[] permutation(long p, int N) {
+ if (p<1) throw new IllegalArgumentException("Permutations are enumerated 1 .. N!");
+ if (N<0) throw new IllegalArgumentException("Must satisfy N >= 0");
+
+ int[] permutation = new int[N];
+
+ if (N > 20) { // factorial(21) would overflow 64-bit long)
+ // Simply make a list (0,1,..N-1) and randomize it, seeded with "p".
+ // Note that this is perhaps not what you want...
+ for (int i=N; --i >= 0; ) permutation[i]=i;
+ org.apache.mahout.jet.random.Uniform gen = new org.apache.mahout.jet.random.Uniform(new org.apache.mahout.jet.random.engine.MersenneTwister((int)p));
+ for (int i=0; i<N-1; i++) {
+ int random = gen.nextIntFromTo(i, N-1);
+
+ //swap(i, random)
+ int tmp = permutation[random];
+ permutation[random]=permutation[i];
+ permutation[i]=tmp;
+ }
+
+ return permutation;
+ }
+
+ // the normal case - exact enumeration
+ if (p > org.apache.mahout.jet.math.Arithmetic.longFactorial(N)) throw new IllegalArgumentException("N too large (a sequence of N elements only has N! permutations).");
+
+ int[] tmp = new int[N];
+ for (int i=1; i<=N; i++) tmp[i-1]= i;
+
+ long io = p-1;
+ for (int M = N-1; M>=1; M--) {
+ long fac = org.apache.mahout.jet.math.Arithmetic.longFactorial(M);
+ int in = ((int) (io / fac)) + 1;
+ io = io % fac;
+ permutation[N-M-1] = tmp[in-1];
+
+ for (int j = in; j <= M; j++) tmp[j-1] = tmp[j];
+ }
+ if (N>0) permutation[N-1] = tmp[0];
+
+ for (int i=N; --i >= 0; ) permutation[i] = permutation[i]-1;
+ return permutation;
+}
+/**
+A non-generic variant of reordering, specialized for <tt>int[]</tt>, same semantics.
+Quicker than generic reordering. Also for convenience (forget about the Swapper object).
+*/
+public static void permute(int[] list, int[] indexes) {
+ int[] copy = (int[]) list.clone();
+ for (int i=list.length; --i >=0; ) list[i] = copy[indexes[i]];
+}
+/**
+Deprecated. Generically reorders arbitrary shaped generic data <tt>g</tt> such that <tt>g[i] == g[indexes[i]]</tt>.
+(The generic data may be one array, a 2-d matrix, two linked lists or whatever).
+This class swaps elements around, in a way that avoids stumbling over its own feet.
+<p>
+<b>Example:</b>
+<pre>
+Reordering
+[A,B,C,D,E] with indexes [0,4,2,3,1] yields
+[A,E,C,D,B]
+In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1].
+
+Reordering
+[A,B,C,D,E] with indexes [0,4,1,2,3] yields
+[A,E,B,C,D]
+In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
+</pre>
+<p>
+@deprecated
+@param indexes the permutation indexes.
+@param swapper an object that knows how to swap two indexes a,b.
+@param work the working storage, must satisfy <tt>work.length >= indexes.length</tt>; set <tt>work==null</tt> if you don't care about performance.
+*/
+public static void permute(int[] indexes, org.apache.mahout.colt.Swapper swapper, int[] work) {
+ permute(indexes,swapper,work,null);
+}
+/**
+Generically reorders arbitrary shaped generic data <tt>g</tt> such that <tt>g[i] == g[indexes[i]]</tt>.
+(The generic data may be one array, a 2-d matrix, two linked lists or whatever).
+This class swaps elements around, in a way that avoids stumbling over its own feet.
+<p>
+<b>Example:</b>
+<pre>
+Reordering
+[A,B,C,D,E] with indexes [0,4,2,3,1] yields
+[A,E,C,D,B]
+In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1].
+
+Reordering
+[A,B,C,D,E] with indexes [0,4,1,2,3] yields
+[A,E,B,C,D]
+In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
+</pre>
+<p>
+@param indexes the permutation indexes.
+@param swapper an object that knows how to swap two indexes a,b.
+@param work1 some working storage, must satisfy <tt>work1.length >= indexes.length</tt>; set <tt>work1==null</tt> if you don't care about performance.
+@param work2 some working storage, must satisfy <tt>work2.length >= indexes.length</tt>; set <tt>work2==null</tt> if you don't care about performance.
+*/
+public static void permute(int[] indexes, org.apache.mahout.colt.Swapper swapper, int[] work1, int[] work2) {
+ // "tracks" and "pos" keeps track of the current indexes of the elements
+ // Example: We have a list==[A,B,C,D,E], indexes==[0,4,1,2,3] and swap B and E we need to know that the element formlerly at index 1 is now at index 4, and the one formerly at index 4 is now at index 1.
+ // Otherwise we stumble over our own feet and produce nonsense.
+ // Initially index i really is at index i, but this will change due to swapping.
+
+ // work1, work2 to avoid high frequency memalloc's
+ int s = indexes.length;
+ int[] tracks = work1;
+ int[] pos = work2;
+ if (tracks==null || tracks.length<s) tracks = new int[s];
+ if (pos==null || pos.length<s) pos = new int[s];
+ for (int i=s; --i >= 0; ) {
+ tracks[i] = i;
+ pos[i] = i;
+ }
+
+ for (int i=0; i<s; i++) {
+ int index = indexes[i];
+ int track = tracks[index];
+
+ if (i!=track) {
+ swapper.swap(i,track);
+ tracks[index]=i; tracks[pos[i]]=track;
+ int tmp = pos[i]; pos[i]=pos[track]; pos[track]=tmp;
+ }
+ }
+}
+/**
+A non-generic variant of reordering, specialized for <tt>Object[]</tt>, same semantics.
+Quicker than generic reordering. Also for convenience (forget about the Swapper object).
+*/
+public static void permute(Object[] list, int[] indexes) {
+ Object[] copy = (Object[]) list.clone();
+ for (int i=list.length; --i >=0; ) list[i] = copy[indexes[i]];
+}
+}
Propchange: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java?rev=883365&view=auto
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java (added)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java Mon Nov 23 15:14:26 2009
@@ -0,0 +1,469 @@
+/*
+Copyright � 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.colt;
+
+import org.apache.mahout.colt.function.IntComparator;
+/**
+Generically sorts arbitrary shaped data (for example multiple arrays, 1,2 or 3-d matrices, and so on) using a
+quicksort or mergesort. This class addresses two problems, namely
+<ul>
+ <li><i>Sorting multiple arrays in sync</i>
+ <li><i>Sorting by multiple sorting criteria</i> (primary, secondary, tertiary,
+ ...)
+</ul>
+<h4>Sorting multiple arrays in sync</h4>
+<p>
+Assume we have three arrays X, Y and Z. We want to sort all three arrays by
+ X (or some arbitrary comparison function). For example, we have<br>
+ <tt>X=[3, 2, 1], Y=[3.0, 2.0, 1.0], Z=[6.0, 7.0, 8.0]</tt>. The output should
+ be <tt><br>
+ X=[1, 2, 3], Y=[1.0, 2.0, 3.0], Z=[8.0, 7.0, 6.0]</tt>. </p>
+<p>How can we achive this? Here are several alternatives. We could ... </p>
+<ol>
+ <li> make a list of Point3D objects, sort the list as desired using a comparison
+ function, then copy the results back into X, Y and Z. The classic object-oriented
+ way. </li>
+ <li>make an index list [0,1,2,...,N-1], sort the index list using a comparison function,
+ then reorder the elements of X,Y,Z as defined by the index list. Reordering
+ cannot be done in-place, so we need to copy X to some temporary array, then
+ copy in the right order back from the temporary into X. Same for Y and Z.
+ </li>
+ <li> use a generic quicksort or mergesort which, whenever two elements in X are swapped,
+ also swaps the corresponding elements in Y and Z. </li>
+</ol>
+Alternatives 1 and 2 involve quite a lot of copying and allocate significant amounts
+of temporary memory. Alternative 3 involves more swapping, more polymorphic message dispatches, no copying and does not need any temporary memory.
+<p> This class implements alternative 3. It operates on arbitrary shaped data.
+ In fact, it has no idea what kind of data it is sorting. Comparisons and swapping
+ are delegated to user provided objects which know their data and can do the
+ job.
+<p> Lets call the generic data <tt>g</tt> (it may be one array, three linked lists
+ or whatever). This class takes a user comparison function operating on two indexes
+ <tt>(a,b)</tt>, namely an {@link IntComparator}. The comparison function determines
+ whether <tt>g[a]</tt> is equal, less or greater than <tt>g[b]</tt>. The sort,
+ depending on its implementation, can decide to swap the data at index <tt>a</tt>
+ with the data at index <tt>b</tt>. It calls a user provided {@link org.apache.mahout.colt.Swapper}
+ object that knows how to swap the data of these indexes.
+<p>The following snippet shows how to solve the problem.
+<table>
+<td class="PRE">
+<pre>
+final int[] x;
+final double[] y;
+final double[] z;
+
+x = new int[] {3, 2, 1 };
+y = new double[] {3.0, 2.0, 1.0};
+z = new double[] {6.0, 7.0, 8.0};
+
+
+// this one knows how to swap two indexes (a,b)
+Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ int t1; double t2, t3;
+ t1 = x[a]; x[a] = x[b]; x[b] = t1;
+ t2 = y[a]; y[a] = y[b]; y[b] = t2;
+ t3 = z[a]; z[a] = z[b]; z[b] = t3;
+ }
+};
+// simple comparison: compare by X and ignore Y,Z<br>
+IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ return x[a]==x[b] ? 0 : (x[a]<x[b] ? -1 : 1);
+ }
+};
+
+System.out.println("before:");
+System.out.println("X="+Arrays.toString(x));
+System.out.println("Y="+Arrays.toString(y));
+System.out.println("Z="+Arrays.toString(z));
+
+GenericSorting.quickSort(0, X.length, comp, swapper);
+// GenericSorting.mergeSort(0, X.length, comp, swapper);
+
+System.out.println("after:");
+System.out.println("X="+Arrays.toString(x));
+System.out.println("Y="+Arrays.toString(y));
+System.out.println("Z="+Arrays.toString(z));
+</pre>
+</td>
+</table>
+<h4>Sorting by multiple sorting criterias (primary, secondary, tertiary, ...)</h4>
+<p>Assume again we have three arrays X, Y and Z. Now we want to sort all three
+ arrays, primarily by Y, secondarily by Z (if Y elements are equal). For example,
+ we have<br>
+ <tt>X=[6, 7, 8, 9], Y=[3.0, 2.0, 1.0, 3.0], Z=[5.0, 4.0, 4.0, 1.0]</tt>. The
+ output should be <tt><br>
+ X=[8, 7, 9, 6], Y=[1.0, 2.0, 3.0, 3.0], Z=[4.0, 4.0, 1.0, 5.0]</tt>. </p>
+<p>Here is how to solve the problem. All code in the above example stays the same,
+ except that we modify the comparison function as follows</p>
+<table>
+<td class="PRE">
+<pre>
+//compare by Y, if that doesn't help, reside to Z
+IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ if (y[a]==y[b]) return z[a]==z[b] ? 0 : (z[a]<z[b] ? -1 : 1);
+ return y[a]<y[b] ? -1 : 1;
+ }
+};
+</pre>
+</td>
+</table>
+
+<h4>Notes</h4>
+<p></p>
+<p> Sorts involving floating point data and not involving comparators, like, for
+ example provided in the JDK {@link java.util.Arrays} and in the Colt {@link
+ org.apache.mahout.colt.Sorting} handle floating point numbers in special ways to guarantee
+ that NaN's are swapped to the end and -0.0 comes before 0.0. Methods delegating
+ to comparators cannot do this. They rely on the comparator. Thus, if such boundary
+ cases are an issue for the application at hand, comparators explicitly need
+ to implement -0.0 and NaN aware comparisons. Remember: <tt>-0.0 < 0.0 == false</tt>,
+ <tt>(-0.0 == 0.0) == true</tt>, as well as <tt>5.0 < Double.NaN == false</tt>,
+ <tt>5.0 > Double.NaN == false</tt>. Same for <tt>float</tt>.
+<h4>Implementation </h4>
+<p>The quicksort is a derivative of the JDK 1.2 V1.26 algorithms (which are, in
+ turn, based on Bentley's and McIlroy's fine work).
+ The mergesort is a derivative of the JAL algorithms, with optimisations taken from the JDK algorithms.
+Both quick and merge sort are "in-place", i.e. do not allocate temporary memory (helper arrays).
+Mergesort is <i>stable</i> (by definition), while quicksort is not.
+A stable sort is, for example, helpful, if matrices are sorted successively
+by multiple columns. It preserves the relative position of equal elements.
+
+@see java.util.Arrays
+@see org.apache.mahout.colt.Sorting
+@see org.apache.mahout.colt.matrix.doublealgo.Sorting
+
+@author wolfgang.hoschek@cern.ch
+@version 1.0, 03-Jul-99
+*/
+/**
+ * @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
+ */
+@Deprecated
+public class GenericSorting extends Object {
+ private static final int SMALL = 7;
+ private static final int MEDIUM = 40;
+/**
+ * Makes this class non instantiable, but still let's others inherit from it.
+ */
+protected GenericSorting() {}
+/**
+ * Transforms two consecutive sorted ranges into a single sorted
+ * range. The initial ranges are <code>[first, middle)</code>
+ * and <code>[middle, last)</code>, and the resulting range is
+ * <code>[first, last)</code>.
+ * Elements in the first input range will precede equal elements in the
+ * second.
+ */
+private static void inplace_merge(int first, int middle, int last, IntComparator comp, Swapper swapper) {
+ if (first >= middle || middle >= last)
+ return;
+ if (last - first == 2) {
+ if (comp.compare(middle, first)<0) {
+ swapper.swap(first,middle);
+ }
+ return;
+ }
+ int firstCut;
+ int secondCut;
+ if (middle - first > last - middle) {
+ firstCut = first + (middle - first) / 2;
+ secondCut = lower_bound(middle, last, firstCut, comp);
+ }
+ else {
+ secondCut = middle + (last - middle) / 2;
+ firstCut = upper_bound(first, middle, secondCut, comp);
+ }
+
+ // rotate(firstCut, middle, secondCut, swapper);
+ // is manually inlined for speed (jitter inlining seems to work only for small call depths, even if methods are "static private")
+ // speedup = 1.7
+ // begin inline
+ int first2 = firstCut; int middle2 = middle; int last2 = secondCut;
+ if (middle2 != first2 && middle2 != last2) {
+ int first1 = first2; int last1 = middle2;
+ while (first1 < --last1) swapper.swap(first1++,last1);
+ first1 = middle2; last1 = last2;
+ while (first1 < --last1) swapper.swap(first1++,last1);
+ first1 = first2; last1 = last2;
+ while (first1 < --last1) swapper.swap(first1++,last1);
+ }
+ // end inline
+
+ middle = firstCut + (secondCut - middle);
+ inplace_merge(first, firstCut, middle, comp, swapper);
+ inplace_merge(middle, secondCut, last, comp, swapper);
+}
+/**
+ * Performs a binary search on an already-sorted range: finds the first
+ * position where an element can be inserted without violating the ordering.
+ * Sorting is by a user-supplied comparison function.
+ * @param array Array containing the range.
+ * @param first Beginning of the range.
+ * @param last One past the end of the range.
+ * @param x Element to be searched for.
+ * @param comp Comparison function.
+ * @return The largest index i such that, for every j in the
+ * range <code>[first, i)</code>,
+ * <code>comp.apply(array[j], x)</code> is
+ * <code>true</code>.
+ * @see Sorting#upper_bound
+ * @see Sorting#equal_range
+ * @see Sorting#binary_search
+ */
+private static int lower_bound(int first, int last, int x, IntComparator comp) {
+ //if (comp==null) throw new NullPointerException();
+ int len = last - first;
+ while (len > 0) {
+ int half = len / 2;
+ int middle = first + half;
+ if (comp.compare(middle, x)<0) {
+ first = middle + 1;
+ len -= half + 1;
+ }
+ else {
+ len = half;
+ }
+ }
+ return first;
+}
+/**
+ * Returns the index of the median of the three indexed chars.
+ */
+private static int med3(int a, int b, int c, IntComparator comp) {
+ int ab = comp.compare(a,b);
+ int ac = comp.compare(a,c);
+ int bc = comp.compare(b,c);
+ return (ab<0 ?
+ (bc<0 ? b : ac<0 ? c : a) :
+ (bc>0 ? b : ac>0 ? c : a));
+}
+/**
+ * Sorts the specified range of elements according
+ * to the order induced by the specified comparator. All elements in the
+ * range must be <i>mutually comparable</i> by the specified comparator
+ * (that is, <tt>c.compare(a, b)</tt> must not throw an
+ * exception for any indexes <tt>a</tt> and
+ * <tt>b</tt> in the range).<p>
+ *
+ * This sort is guaranteed to be <i>stable</i>: equal elements will
+ * not be reordered as a result of the sort.<p>
+ *
+ * The sorting algorithm is a modified mergesort (in which the merge is
+ * omitted if the highest element in the low sublist is less than the
+ * lowest element in the high sublist). This algorithm offers guaranteed
+ * n*log(n) performance, and can approach linear performance on nearly
+ * sorted lists.
+ *
+ * @param fromIndex the index of the first element (inclusive) to be sorted.
+ * @param toIndex the index of the last element (exclusive) to be sorted.
+ * @param c the comparator to determine the order of the generic data.
+ * @param swapper an object that knows how to swap the elements at any two indexes (a,b).
+ *
+ * @see IntComparator
+ * @see Swapper
+ */
+public static void mergeSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
+ /*
+ We retain the same method signature as quickSort.
+ Given only a comparator and swapper we do not know how to copy and move elements from/to temporary arrays.
+ Hence, in contrast to the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary arrays.
+ A non-inplace mergesort would perhaps be faster in most cases, but would require non-intuitive delegate objects...
+ */
+ int length = toIndex - fromIndex;
+
+ // Insertion sort on smallest arrays
+ if (length < SMALL) {
+ for (int i = fromIndex; i < toIndex; i++) {
+ for (int j = i; j > fromIndex && (c.compare(j - 1, j) > 0); j--) {
+ swapper.swap(j, j - 1);
+ }
+ }
+ return;
+ }
+
+ // Recursively sort halves
+ int mid = (fromIndex + toIndex) / 2;
+ mergeSort(fromIndex, mid, c, swapper);
+ mergeSort(mid, toIndex, c, swapper);
+
+ // If list is already sorted, nothing left to do. This is an
+ // optimization that results in faster sorts for nearly ordered lists.
+ if (c.compare(mid - 1, mid) <= 0) return;
+
+ // Merge sorted halves
+ inplace_merge(fromIndex, mid, toIndex, c, swapper);
+}
+/**
+ * Sorts the specified range of elements according
+ * to the order induced by the specified comparator. All elements in the
+ * range must be <i>mutually comparable</i> by the specified comparator
+ * (that is, <tt>c.compare(a, b)</tt> must not throw an
+ * exception for any indexes <tt>a</tt> and
+ * <tt>b</tt> in the range).<p>
+ *
+ * The sorting algorithm is a tuned quicksort,
+ * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a
+ * Sort Function", Software-Practice and Experience, Vol. 23(11)
+ * P. 1249-1265 (November 1993). This algorithm offers n*log(n)
+ * performance on many data sets that cause other quicksorts to degrade to
+ * quadratic performance.
+ *
+ * @param fromIndex the index of the first element (inclusive) to be sorted.
+ * @param toIndex the index of the last element (exclusive) to be sorted.
+ * @param c the comparator to determine the order of the generic data.
+ * @param swapper an object that knows how to swap the elements at any two indexes (a,b).
+ *
+ * @see IntComparator
+ * @see Swapper
+ */
+public static void quickSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
+ quickSort1(fromIndex, toIndex-fromIndex, c, swapper);
+}
+/**
+ * Sorts the specified sub-array into ascending order.
+ */
+private static void quickSort1(int off, int len, IntComparator comp, Swapper swapper) {
+ // Insertion sort on smallest arrays
+ if (len < SMALL) {
+ for (int i=off; i<len+off; i++)
+ for (int j=i; j>off && (comp.compare(j-1,j)>0); j--) {
+ swapper.swap(j, j-1);
+ }
+ return;
+ }
+
+ // Choose a partition element, v
+ int m = off + len/2; // Small arrays, middle element
+ if (len > SMALL) {
+ int l = off;
+ int n = off + len - 1;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(l, l+s, l+2*s, comp);
+ m = med3(m-s, m, m+s, comp);
+ n = med3(n-2*s, n-s, n, comp);
+ }
+ m = med3(l, m, n, comp); // Mid-size, med of 3
+ }
+ //long v = x[m];
+
+ // Establish Invariant: v* (<v)* (>v)* v*
+ int a = off, b = a, c = off + len - 1, d = c;
+ while(true) {
+ int comparison;
+ while (b <= c && ((comparison=comp.compare(b,m))<=0)) {
+ if (comparison == 0) {
+ if (a==m) m = b; // moving target; DELTA to JDK !!!
+ else if (b==m) m = a; // moving target; DELTA to JDK !!!
+ swapper.swap(a++, b);
+ }
+ b++;
+ }
+ while (c >= b && ((comparison=comp.compare(c,m))>=0)) {
+ if (comparison == 0) {
+ if (c==m) m = d; // moving target; DELTA to JDK !!!
+ else if (d==m) m = c; // moving target; DELTA to JDK !!!
+ swapper.swap(c, d--);
+ }
+ c--;
+ }
+ if (b > c) break;
+ if (b==m) m = d; // moving target; DELTA to JDK !!!
+ else if (c==m) m = c; // moving target; DELTA to JDK !!!
+ swapper.swap(b++, c--);
+ }
+
+ // Swap partition elements back to middle
+ int s, n = off + len;
+ s = Math.min(a-off, b-a ); vecswap(swapper, off, b-s, s);
+ s = Math.min(d-c, n-d-1); vecswap(swapper, b, n-s, s);
+
+ // Recursively sort non-partition-elements
+ if ((s = b-a) > 1)
+ quickSort1(off, s, comp, swapper);
+ if ((s = d-c) > 1)
+ quickSort1(n-s, s, comp, swapper);
+}
+/**
+ * Reverses a sequence of elements.
+ * @param array Array containing the sequence
+ * @param first Beginning of the range
+ * @param last One past the end of the range
+ * @exception ArrayIndexOutOfBoundsException If the range
+ * is invalid.
+ */
+private static void reverse(int first, int last, Swapper swapper) {
+ // no more needed since manually inlined
+ while (first < --last) {
+ swapper.swap(first++,last);
+ }
+}
+/**
+ * Rotate a range in place: <code>array[middle]</code> is put in
+ * <code>array[first]</code>, <code>array[middle+1]</code> is put in
+ * <code>array[first+1]</code>, etc. Generally, the element in position
+ * <code>i</code> is put into position
+ * <code>(i + (last-middle)) % (last-first)</code>.
+ * @param array Array containing the range
+ * @param first Beginning of the range
+ * @param middle Index of the element that will be put in
+ * <code>array[first]</code>
+ * @param last One past the end of the range
+ */
+private static void rotate(int first, int middle, int last, Swapper swapper) {
+ // no more needed since manually inlined
+ if (middle != first && middle != last) {
+ reverse(first, middle, swapper);
+ reverse(middle, last, swapper);
+ reverse(first, last, swapper);
+ }
+}
+/**
+ * Performs a binary search on an already-sorted range: finds the last
+ * position where an element can be inserted without violating the ordering.
+ * Sorting is by a user-supplied comparison function.
+ * @param array Array containing the range.
+ * @param first Beginning of the range.
+ * @param last One past the end of the range.
+ * @param x Element to be searched for.
+ * @param comp Comparison function.
+ * @return The largest index i such that, for every j in the
+ * range <code>[first, i)</code>,
+ * <code>comp.apply(x, array[j])</code> is
+ * <code>false</code>.
+ * @see Sorting#lower_bound
+ * @see Sorting#equal_range
+ * @see Sorting#binary_search
+ */
+private static int upper_bound(int first, int last, int x, IntComparator comp) {
+ //if (comp==null) throw new NullPointerException();
+ int len = last - first;
+ while (len > 0) {
+ int half = len / 2;
+ int middle = first + half;
+ if (comp.compare(x, middle)<0) {
+ len = half;
+ }
+ else {
+ first = middle + 1;
+ len -= half + 1;
+ }
+ }
+ return first;
+}
+/**
+ * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
+ */
+private static void vecswap(Swapper swapper, int a, int b, int n) {
+ for (int i=0; i<n; i++, a++, b++) swapper.swap(a, b);
+}
+}
Propchange: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java?rev=883365&view=auto
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java (added)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java Mon Nov 23 15:14:26 2009
@@ -0,0 +1,157 @@
+/*
+Copyright 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.colt;
+
+import org.apache.mahout.colt.function.IntComparator;
+/**
+Demonstrates how to use {@link Sort}.
+
+@author wolfgang.hoschek@cern.ch
+@version 1.0, 03-Jul-99
+*/
+class GenericSortingTest extends Object {
+/**
+ * Makes this class non instantiable, but still let's others inherit from it.
+ */
+protected GenericSortingTest() {}
+/**
+ * Just a demo.
+ */
+public static void demo1() {
+ final int[] x;
+ final double[] y;
+ final double[] z;
+
+ x = new int[] {3, 2, 1 };
+ y = new double[] {3.0, 2.0, 1.0};
+ z = new double[] {6.0, 7.0, 8.0};
+
+ Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ int t1; double t2, t3;
+ t1 = x[a]; x[a] = x[b]; x[b] = t1;
+ t2 = y[a]; y[a] = y[b]; y[b] = t2;
+ t3 = z[a]; z[a] = z[b]; z[b] = t3;
+ }
+ };
+
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ return x[a]==x[b] ? 0 : (x[a]<x[b] ? -1 : 1);
+ }
+ };
+
+ System.out.println("before:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+
+
+ int from = 0;
+ int to = x.length;
+ GenericSorting.quickSort(from, to, comp, swapper);
+
+ System.out.println("after:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+ System.out.println("\n\n");
+}
+/**
+ * Just a demo.
+ */
+public static void demo2() {
+ final int[] x;
+ final double[] y;
+ final double[] z;
+
+ x = new int[] {6, 7, 8, 9 };
+ y = new double[] {3.0, 2.0, 1.0, 3.0};
+ z = new double[] {5.0, 4.0, 4.0, 1.0};
+
+ Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ int t1; double t2, t3;
+ t1 = x[a]; x[a] = x[b]; x[b] = t1;
+ t2 = y[a]; y[a] = y[b]; y[b] = t2;
+ t3 = z[a]; z[a] = z[b]; z[b] = t3;
+ }
+ };
+
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ if (y[a]==y[b]) return z[a]==z[b] ? 0 : (z[a]<z[b] ? -1 : 1);
+ return y[a]<y[b] ? -1 : 1;
+ }
+ };
+
+
+ System.out.println("before:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+
+
+ int from = 0;
+ int to = x.length;
+ GenericSorting.quickSort(from, to, comp, swapper);
+
+ System.out.println("after:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+ System.out.println("\n\n");
+}
+/**
+ * Checks the correctness of the partition method by generating random input parameters and checking whether results are correct.
+ */
+public static void testRandomly(int runs) {
+ org.apache.mahout.jet.random.engine.RandomEngine engine = new org.apache.mahout.jet.random.engine.MersenneTwister();
+ org.apache.mahout.jet.random.Uniform gen = new org.apache.mahout.jet.random.Uniform(engine);
+
+ for (int run=0; run<runs; run++) {
+ int maxSize = 50;
+ int maxSplittersSize = 2*maxSize;
+
+
+ int size = gen.nextIntFromTo(1,maxSize);
+ int from, to;
+ if (size==0) {
+ from=0; to=-1;
+ }
+ else {
+ from = gen.nextIntFromTo(0,size-1);
+ to = gen.nextIntFromTo(Math.min(from,size-1),size-1);
+ }
+
+ org.apache.mahout.colt.matrix.DoubleMatrix2D A1 = new org.apache.mahout.colt.matrix.impl.DenseDoubleMatrix2D(size,size);
+ org.apache.mahout.colt.matrix.DoubleMatrix2D P1 = A1.viewPart(from,from,size-to,size-to);
+
+ int intervalFrom = gen.nextIntFromTo(size/2,2*size);
+ int intervalTo = gen.nextIntFromTo(intervalFrom,2*size);
+
+ for (int i=0; i<size; i++) {
+ for (int j=0; j<size; j++) {
+ A1.set(i,j,gen.nextIntFromTo(intervalFrom,intervalTo));
+ }
+ }
+
+ org.apache.mahout.colt.matrix.DoubleMatrix2D A2 = A1.copy();
+ org.apache.mahout.colt.matrix.DoubleMatrix2D P2 = A2.viewPart(from,from,size-to,size-to);
+
+ int c = 0;
+ org.apache.mahout.colt.matrix.DoubleMatrix2D S1 = org.apache.mahout.colt.matrix.doublealgo.Sorting.quickSort.sort(P1,c);
+ org.apache.mahout.colt.matrix.DoubleMatrix2D S2 = org.apache.mahout.colt.matrix.doublealgo.Sorting.mergeSort.sort(P2,c);
+
+ if (!(S1.viewColumn(c).equals(S2.viewColumn(c)))) throw new InternalError();
+ }
+
+ System.out.println("All tests passed. No bug detected.");
+}
+}
Propchange: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Partitioning.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Partitioning.java?rev=883365&view=auto
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Partitioning.java (added)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Partitioning.java Mon Nov 23 15:14:26 2009
@@ -0,0 +1,1260 @@
+/*
+Copyright � 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.colt;
+
+import org.apache.mahout.colt.function.IntComparator;
+import org.apache.mahout.colt.list.DoubleArrayList;
+import org.apache.mahout.colt.list.IntArrayList;
+/**
+ * Given some interval boundaries, partitions arrays such that all elements falling into an interval are placed next to each other.
+ * <p>
+ * The algorithms partition arrays into two or more intervals.
+ * They distinguish between <i>synchronously</i> partitioning either one, two or three arrays.
+ * They further come in templated versions, either partitioning <tt>int[]</tt> arrays or <tt>double[]</tt> arrays.
+ * <p>
+ * You may want to start out reading about the simplest case: Partitioning one <tt>int[]</tt> array into two intervals.
+ * To do so, read {@link #partition(int[],int,int,int)}.
+ *
+ * Next, building upon that foundation comes a method partitioning <tt>int[]</tt> arrays into multiple intervals.
+ * See {@link #partition(int[],int,int,int[],int,int,int[])} for related documentation.
+ * <p>
+ * All other methods are no different than the one's you now already understand, except that they operate on slightly different data types.
+ * <p>
+ * <b>Performance</b>
+ * <p>
+ * Partitioning into two intervals is <tt>O( N )</tt>.
+ * Partitioning into k intervals is <tt>O( N * log(k))</tt>.
+ * Constants factors are minimized.
+ * No temporary memory is allocated; Partitioning is in-place.
+ *
+ * @see org.apache.mahout.colt.matrix.doublealgo.Partitioning
+ *
+ * @author wolfgang.hoschek@cern.ch
+ * @version 1.0, 03-Jul-99
+ */
+/**
+ * @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
+ */
+@Deprecated
+public class Partitioning extends Object {
+ private static final int SMALL = 7;
+ private static final int MEDIUM = 40;
+
+ // benchmark only
+ protected static int steps = 0;
+ public static int swappedElements = 0;
+/**
+ * Makes this class non instantiable, but still let's others inherit from it.
+ */
+protected Partitioning() {}
+/**
+Finds the given key "a" within some generic data using the binary search algorithm.
+@param a the index of the key to search for.
+@param from the leftmost search position, inclusive.
+@param to the rightmost search position, inclusive.
+@param comp the comparator determining the order of the generic data.
+ Takes as first argument the index <tt>a</tt> within the generic splitters <tt>s</tt>.
+ Takes as second argument the index <tt>b</tt> within the generic data <tt>g</tt>.
+@return index of the search key, if it is contained in the list;
+ otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The <i>insertion
+ point</i> is defined as the the point at which the value would
+ be inserted into the list: the index of the first
+ element greater than the key, or <tt>list.length</tt>, if all
+ elements in the list are less than the specified key. Note
+ that this guarantees that the return value will be >= 0 if
+ and only if the key is found.
+*/
+private static int binarySearchFromTo(int a, int from, int to, IntComparator comp) {
+ while (from <= to) {
+ int mid = (from + to) / 2;
+ int comparison = comp.compare(mid,a);
+ if (comparison < 0) from = mid + 1;
+ else if (comparison > 0) to = mid - 1;
+ else return mid; // key found
+ }
+ return -(from + 1); // key not found.
+}
+/**
+ * Same as {@link #dualPartition(int[],int[],int,int,int[],int,int,int[])}
+ * except that it <i>synchronously</i> partitions <tt>double[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static void dualPartition(double[] list, double[] secondary, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
+ double splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s);
+ m = med3(list, m-s, m, m+s);
+ n = med3(list, n-2*s, n-s, n);
+ }
+ m = med3(list, l, m, n); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = dualPartition(list,secondary,from,to,splitter);
+ splitIndexes[medianIndex] = splitIndex;
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(splitter < splitters[i]))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(splitter > splitters[i]))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ dualPartition(list, secondary, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ dualPartition(list, secondary, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+}
+/**
+ * Same as {@link #dualPartition(int[],int[],int,int,int)}
+ * except that it <i>synchronously</i> partitions <tt>double[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static int dualPartition(double[] list, double[] secondary, int from, int to, double splitter) {
+ double element; // int, double --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from] = element;
+
+ element = secondary[i];
+ secondary[i] = secondary[from];
+ secondary[from++] = element;
+ }
+ }
+ return from-1;
+}
+/**
+ * Same as {@link #partition(int[],int,int,int[],int,int,int[])} except that this method <i>synchronously</i> partitions two arrays at the same time;
+ * both arrays are partially sorted according to the elements of the primary array.
+ * In other words, each time an element in the primary array is moved from index A to B, the correspoding element within the secondary array is also moved from index A to B.
+ * <p>
+ * <b>Use cases:</b>
+ * <p>
+ * Image having a large list of 2-dimensional points.
+ * If memory consumption and performance matter, it is a good idea to physically lay them out as two 1-dimensional arrays
+ * (using something like <tt>Point2D</tt> objects would be prohibitively expensive, both in terms of time and space).
+ * Now imagine wanting to histogram the points.
+ * We may want to partially sort the points by x-coordinate into intervals.
+ * This method efficiently does the job.
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Same as for single-partition methods.
+ */
+public static void dualPartition(int[] list, int[] secondary, int from, int to, int[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
+ int splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s);
+ m = med3(list, m-s, m, m+s);
+ n = med3(list, n-2*s, n-s, n);
+ }
+ m = med3(list, l, m, n); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = dualPartition(list,secondary,from,to,splitter);
+ splitIndexes[medianIndex] = splitIndex;
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(splitter < splitters[i]))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(splitter > splitters[i]))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ dualPartition(list, secondary, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ dualPartition(list, secondary, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+}
+/**
+ * Same as {@link #partition(int[],int,int,int)} except that this method <i>synchronously</i> partitions two arrays at the same time;
+ * both arrays are partially sorted according to the elements of the primary array.
+ * In other words, each time an element in the primary array is moved from index A to B, the correspoding element within the secondary array is also moved from index A to B.
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Same as for single-partition methods.
+ */
+public static int dualPartition(int[] list, int[] secondary, int from, int to, int splitter) {
+ int element; // int, double --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from] = element;
+
+ element = secondary[i];
+ secondary[i] = secondary[from];
+ secondary[from++] = element;
+ }
+ }
+ return from-1;
+}
+/**
+Same as {@link #partition(int[],int,int,int[],int,int,int[])}
+except that it <i>generically</i> partitions arbitrary shaped data (for example matrices or multiple arrays) rather than <tt>int[]</tt> arrays.
+<p>
+This method operates on arbitrary shaped data and arbitrary shaped splitters.
+In fact, it has no idea what kind of data by what kind of splitters it is partitioning. Comparisons and swapping
+are delegated to user provided objects which know their data and can do the
+job.
+<p>
+Lets call the generic data <tt>g</tt> (it may be a matrix, one array, three linked lists
+or whatever). Lets call the generic splitters <tt>s</tt>.
+This class takes a user comparison function operating on two indexes
+<tt>(a,b)</tt>, namely an {@link IntComparator}.
+The comparison function determines whether <tt>s[a]</tt> is equal, less or greater than <tt>g[b]</tt>.
+This method can then decide to swap the data <tt>g[b]</tt>
+with the data <tt>g[c]</tt> (yes, <tt>c</tt>, not <tt>a</tt>).
+It calls a user provided {@link org.apache.mahout.colt.Swapper}
+object that knows how to swap the data of these two indexes.
+<p>
+Again, note the details: Comparisons compare <tt>s[a]</tt> with <tt>g[b]</tt>.
+Swaps swap <tt>g[b]</tt> with <tt>g[c]</tt>.
+Prior to calling this method, the generic splitters <tt>s</tt> must be sorted ascending and must not contain multiple equal values.
+These preconditions are not checked; be sure that they are met.
+
+@param from the index of the first element within <tt>g</tt> to be considered.
+@param to the index of the last element within <tt>g</tt> to be considered.
+The method considers the elements <tt>g[from] .. g[to]</tt>.
+
+
+@param splitFrom the index of the first splitter element to be considered.
+@param splitTo the index of the last splitter element to be considered.
+The method considers the splitter elements <tt>s[splitFrom] .. s[splitTo]</tt>.
+
+@param splitIndexes a list into which this method fills the indexes of elements delimiting intervals.
+Upon return <tt>splitIndexes[splitFrom..splitTo]</tt> will be set accordingly.
+Therefore, must satisfy <tt>splitIndexes.length > splitTo</tt>.
+
+@param comp the comparator comparing a splitter with an element of the generic data.
+ Takes as first argument the index <tt>a</tt> within the generic splitters <tt>s</tt>.
+ Takes as second argument the index <tt>b</tt> within the generic data <tt>g</tt>.
+@param comp2 the comparator to determine the order of the generic data.
+ Takes as first argument the index <tt>a</tt> within the generic data <tt>g</tt>.
+ Takes as second argument the index <tt>b</tt> within the generic data <tt>g</tt>.
+@param comp3 the comparator comparing a splitter with another splitter.
+ Takes as first argument the index <tt>a</tt> within the generic splitters <tt>s</tt>.
+ Takes as second argument the index <tt>b</tt> within the generic splitters <tt>g</tt>.
+@param swapper an object that knows how to swap the elements at any two indexes (a,b).
+ Takes as first argument the index <tt>b</tt> within the generic data <tt>g</tt>.
+ Takes as second argument the index <tt>c</tt> within the generic data <tt>g</tt>.
+
+<p>
+Tip: Normally you will have <tt>splitIndexes.length == s.length</tt> as well as <tt>from==0, to==g.length-1</tt> and <tt>splitFrom==0, splitTo==s.length-1</tt>.
+
+@see Sort
+@see Sort#sort(int,int,IntComparator,Swapper)
+@see Sorting#binarySearchFromTo(int,int,IntComparator)
+*/
+public static void genericPartition(int from, int to, int splitFrom, int splitTo, int[] splitIndexes, IntComparator comp, IntComparator comp2, IntComparator comp3, Swapper swapper) {
+ int splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(l, l+s, l+2*s, comp2);
+ m = med3(m-s, m, m+s, comp2);
+ n = med3(n-2*s, n-s, n, comp2);
+ }
+ m = med3(l, m, n, comp2); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = binarySearchFromTo(m,splitFrom,splitTo,comp);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = medianIndex;
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = genericPartition(from,to,splitter,comp,swapper);
+ splitIndexes[medianIndex] = splitIndex;
+
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(comp3.compare(splitter,i) < 0))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(comp3.compare(splitter,i) > 0))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ genericPartition(from, splitIndex, splitFrom, medianIndex-1, splitIndexes, comp, comp2, comp3, swapper);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ genericPartition(splitIndex+1, to, medianIndex+1, splitTo, splitIndexes, comp, comp2, comp3, swapper);
+ }
+}
+/**
+Same as {@link #partition(int[],int,int,int)}
+except that it <i>generically</i> partitions arbitrary shaped data (for example matrices or multiple arrays) rather than <tt>int[]</tt> arrays.
+*/
+private static int genericPartition(int from, int to, int splitter, IntComparator comp, Swapper swapper) {
+ for (int i=from-1; ++i<=to; ) {
+ if (comp.compare(splitter,i) > 0) {
+ // swap x[i] with x[from]
+ swapper.swap(i,from);
+ from++;
+ }
+ }
+ return from-1;
+}
+/**
+ * Returns the index of the median of the three indexed elements.
+ */
+private static int med3(double x[], int a, int b, int c) {
+ return (x[a] < x[b] ?
+ (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
+ (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
+}
+/**
+ * Returns the index of the median of the three indexed elements.
+ */
+private static int med3(int x[], int a, int b, int c) {
+ return (x[a] < x[b] ?
+ (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
+ (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
+}
+/**
+ * Returns the index of the median of the three indexed chars.
+ */
+private static int med3(Object x[], int a, int b, int c, java.util.Comparator comp) {
+ int ab = comp.compare(x[a],x[b]);
+ int ac = comp.compare(x[a],x[c]);
+ int bc = comp.compare(x[b],x[c]);
+ return (ab<0 ?
+ (bc<0 ? b : ac<0 ? c : a) :
+ (bc>0 ? b : ac>0 ? c : a));
+}
+/**
+ * Returns the index of the median of the three indexed chars.
+ */
+private static int med3(int a, int b, int c, IntComparator comp) {
+ int ab = comp.compare(a,b);
+ int ac = comp.compare(a,c);
+ int bc = comp.compare(b,c);
+ return (ab<0 ?
+ (bc<0 ? b : ac<0 ? c : a) :
+ (bc>0 ? b : ac>0 ? c : a));
+}
+/**
+ * Same as {@link #partition(int[],int,int,int[],int,int,int[])}
+ * except that it partitions <tt>double[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static void partition(double[] list, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
+ double splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s);
+ m = med3(list, m-s, m, m+s);
+ n = med3(list, n-2*s, n-s, n);
+ }
+ m = med3(list, l, m, n); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = partition(list,from,to,splitter);
+ splitIndexes[medianIndex] = splitIndex;
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(splitter < splitters[i]))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(splitter > splitters[i]))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ partition(list, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ partition(list, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+}
+/**
+ * Same as {@link #partition(int[],int,int,int)}
+ * except that it partitions <tt>double[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static int partition(double[] list, int from, int to, double splitter) {
+ double element; // int, double --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from++] = element;
+ }
+ }
+ return from-1;
+}
+/**
+ * Partitions (partially sorts) the given list such that all elements falling into some intervals are placed next to each other.
+ * Returns the indexes of elements delimiting intervals.
+ * <p>
+ * <b>Example:</b>
+ * <p>
+ * <tt>list = (7, 4, 5, 50, 6, 4, 3, 6), splitters = (5, 10, 30)</tt>
+ * defines the three intervals <tt>[-infinity,5), [5,10), [10,30)</tt>.
+ * Lets define to sort the entire list (<tt>from=0, to=7</tt>) using all splitters (<tt>splitFrom==0, splitTo=2</tt>).
+ * <p>
+ * The method modifies the list to be <tt>list = (4, 4, 3, 6, 7, 5, 6, 50)</tt>
+ * and returns the <tt>splitIndexes = (2, 6, 6)</tt>.
+ * In other words,
+ * <ul>
+ * <li>All values <tt>list[0..2]</tt> fall into <tt>[-infinity,5)</tt>.
+ * <li>All values <tt>list[3..6]</tt> fall into <tt>[5,10)</tt>.
+ * <li>All values <tt>list[7..6]</tt> fall into <tt>[10,30)</tt>, i.e. no elements, since <tt>7>6</tt>.
+ * <li>All values <tt>list[7 .. 7=list.length-1]</tt> fall into <tt>[30,infinity]</tt>.
+ * <li>In general, all values <tt>list[splitIndexes[j-1]+1 .. splitIndexes[j]]</tt> fall into interval <tt>j</tt>.
+ * </ul>
+ * As can be seen, the list is partially sorted such that values falling into a certain interval are placed next to each other.
+ * Note that <i>within</i> an interval, elements are entirelly unsorted.
+ * They are only sorted across interval boundaries.
+ * In particular, this partitioning algorithm is not <i>stable</i>: the relative order of elements is not preserved
+ * (Producing a stable algorithm would require no more than minor modifications to method partition(int[],int,int,int)).
+ * <p>
+ * More formally, this method guarantees that upon return <tt>for all j = splitFrom .. splitTo</tt> there holds:
+ * <br><tt>for all i = splitIndexes[j-1]+1 .. splitIndexes[j]: splitters[j-1] <= list[i] < splitters[j]</tt>.
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Let <tt>N=to-from+1</tt> be the number of elements to be partitioned.
+ * Let <tt>k=splitTo-splitFrom+1</tt> be the number of splitter elements.
+ * Then we have the following time complexities
+ * <ul>
+ * <li>Worst case: <tt>O( N * log(k) )</tt>.
+ * <li>Average case: <tt>O( N * log(k) )</tt>.
+ * <li>Best case: <tt>O( N )</tt>.
+ * In general, the more uniform (skewed) the data is spread across intervals, the more performance approaches the worst (best) case.
+ * If no elements fall into the given intervals, running time is linear.
+ * </ul>
+ * No temporary memory is allocated; the sort is in-place.
+ * <p>
+ * <b>Implementation:</b>
+ * <p>
+ * The algorithm can be seen as a Bentley/McIlroy quicksort where swapping and insertion sort are omitted.
+ * It is designed to detect and take advantage of skew while maintaining good performance in the uniform case.
+ *
+ * @param list the list to be partially sorted.
+
+ * @param from the index of the first element within <tt>list</tt> to be considered.
+ * @param to the index of the last element within <tt>list</tt> to be considered.
+ * The method considers the elements <tt>list[from] .. list[to]</tt>.
+
+ * @param splitters the values at which the list shall be split into intervals.
+ * Must be sorted ascending and must not contain multiple identical values.
+ * These preconditions are not checked; be sure that they are met.
+
+ * @param splitFrom the index of the first splitter element to be considered.
+ * @param splitTo the index of the last splitter element to be considered.
+ * The method considers the splitter elements <tt>splitters[splitFrom] .. splitters[splitTo]</tt>.
+
+ * @param splitIndexes a list into which this method fills the indexes of elements delimiting intervals.
+ * Upon return <tt>splitIndexes[splitFrom..splitTo]</tt> will be set accordingly.
+ * Therefore, must satisfy <tt>splitIndexes.length > splitTo</tt>.
+ * <p>
+ * Tip: Normally you will have <tt>splitIndexes.length == splitters.length</tt> as well as <tt>from==0, to==list.length-1</tt> and <tt>splitFrom==0, splitTo==splitters.length-1</tt>.
+ *
+ * @see org.apache.mahout.colt.Arrays
+ * @see org.apache.mahout.colt.GenericSorting
+ * @see java.util.Arrays
+ */
+public static void partition(int[] list, int from, int to, int[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
+ int element,splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s);
+ m = med3(list, m-s, m, m+s);
+ n = med3(list, n-2*s, n-s, n);
+ }
+ m = med3(list, l, m, n); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo);
+
+ //int key = list[m];
+ /*
+ if (splitTo-splitFrom+1 < 5) { // on short lists linear search is quicker
+ int i=splitFrom-1;
+ while (++i <= splitTo && list[i] < key);
+ if (i > splitTo || list[i] > key) i = -i-1; // not found
+ medianIndex = i;
+ }
+ */
+ //else {
+ /*
+
+ int low = splitFrom;
+ int high = splitTo;
+ int comparison;
+
+ int mid=0;
+ while (low <= high) {
+ mid = (low + high) / 2;
+ comparison = splitters[mid]-key;
+ if (comparison < 0) low = mid + 1;
+ else if (comparison > 0) high = mid - 1;
+ else break; //return mid; // key found
+ }
+ medianIndex = mid;
+ if (low > high) medianIndex = -(medianIndex + 1); // key not found.
+ //}
+ */
+
+
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ //System.out.println("medianIndex="+medianIndex);
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ // Could simply call:
+ int splitIndex = partition(list,from,to,splitter);
+ // but for speed the code is manually inlined.
+ /*
+ steps += to-from+1;
+ int head = from;
+ for (int i=from-1; ++i<=to; ) { // swap all elements < splitter to front
+ element = list[i];
+ if (element < splitter) {
+ list[i] = list[head];
+ list[head++] = element;
+ //swappedElements++;
+ }
+ }
+ int splitIndex = head-1;
+ */
+
+
+
+
+
+
+
+ //System.out.println("splitIndex="+splitIndex);
+ splitIndexes[medianIndex] = splitIndex;
+
+ //if (splitFrom == splitTo) return; // done
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(splitter < splitters[i]))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(splitter > splitters[i]))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ //System.out.println("1.recursive: from="+from+", to="+splitIndex+", splitFrom="+splitFrom+", splitTo="+(medianIndex-1));
+ partition(list, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ //System.out.println("2.recursive: from="+(splitIndex+1)+", to="+to+", splitFrom="+(medianIndex+1)+", splitTo="+splitTo);
+ partition(list, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+ //System.out.println("BACK TRACKING\n\n");
+}
+/**
+ * Partitions (partially sorts) the given list such that all elements falling into the given interval are placed next to each other.
+ * Returns the index of the element delimiting the interval.
+ * <p>
+ * <b>Example:</b>
+ * <p>
+ * <tt>list = (7, 4, 5, 50, 6, 4, 3, 6), splitter = 5</tt>
+ * defines the two intervals <tt>[-infinity,5), [5,+infinity]</tt>.
+ * <p>
+ * The method modifies the list to be <tt>list = (4, 4, 3, 50, 6, 7, 5, 6)</tt>
+ * and returns the split index <tt>2</tt>.
+ * In other words,
+ * <ul>
+ * <li>All values <tt>list[0..2]</tt> fall into <tt>[-infinity,5)</tt>.
+ * <li>All values <tt>list[3=2+1 .. 7=list.length-1]</tt> fall into <tt>[5,+infinity]</tt>.
+ * </ul>
+ * As can be seen, the list is partially sorted such that values falling into a certain interval are placed next to each other.
+ * Note that <i>within</i> an interval, elements are entirelly unsorted.
+ * They are only sorted across interval boundaries.
+ * In particular, this partitioning algorithm is not <i>stable</i>.
+ * <p>
+ * More formally, this method guarantees that upon return there holds:
+ * <ul>
+ * <li>for all <tt>i = from .. returnValue: list[i] < splitter</tt> and
+ * <li>for all <tt>i = returnValue+1 .. list.length-1: !(list[i] < splitter)</tt>.
+ * </ul>
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Let <tt>N=to-from+1</tt> be the number of elements to be partially sorted.
+ * Then the time complexity is <tt>O( N )</tt>.
+ * No temporary memory is allocated; the sort is in-place.
+ *
+ * <p>
+ * @param list the list to be partially sorted.
+
+ * @param from the index of the first element within <tt>list</tt> to be considered.
+ * @param to the index of the last element within <tt>list</tt> to be considered.
+ * The method considers the elements <tt>list[from] .. list[to]</tt>.
+
+ * @param splitter the value at which the list shall be split.
+
+ * @return the index of the largest element falling into the interval <tt>[-infinity,splitter)</tt>, as seen after partitioning.
+ */
+public static int partition(int[] list, int from, int to, int splitter) {
+ steps += to-from+1;
+
+ /*
+ System.out.println();
+ if (from<=to) {
+ System.out.println("SORT WORKING: from="+from+", to="+to+", splitter="+splitter);
+ }
+ else {
+ System.out.println("SORT WORKING: NOTHING TO DO.");
+ }
+ */
+
+
+
+
+
+ // returns index of last element < splitter
+
+
+ /*
+ for (int i=from-1; ++i<=to; ) {
+ if (list[i] < splitter) {
+ int element = list[i];
+ list[i] = list[from];
+ list[from++] = element;
+ }
+ }
+ */
+
+
+
+
+ int element;
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from++] = element;
+ //swappedElements++;
+ }
+ }
+ //if (from<=to) System.out.println("Swapped "+(head-from)+" elements");
+
+
+ /*
+ //JAL:
+ int first = from;
+ int last = to+1;
+ --first;
+ while (true) {
+ while (++first < last && list[first] < splitter);
+ while (first < --last && !(list[last] < splitter));
+ if (first >= last) return first-1;
+ int tmp = list[first];
+ list[first] = list[last];
+ list[last] = tmp;
+ }
+ */
+
+
+
+ /*
+ System.out.println("splitter="+splitter);
+ System.out.println("before="+new IntArrayList(list));
+ int head = from;
+ int trail = to;
+ int element;
+ while (head<=trail) {
+ head--;
+ while (++head < trail && list[head] < splitter);
+
+ trail++;
+ while (--trail > head && list[trail] >= splitter);
+
+ if (head != trail) {
+ element = list[head];
+ list[head] = list[trail];
+ list[trail] = element;
+ }
+ head++;
+ trail--;
+ System.out.println("after ="+new IntArrayList(list)+", head="+head);
+ }
+ */
+
+
+ /*
+ //System.out.println("splitter="+splitter);
+ //System.out.println("before="+new IntArrayList(list));
+ to++;
+ //int head = from;
+ int element;
+ //int oldHead;
+ while (--to >= from) {
+ element = list[to];
+ if (element < splitter) {
+ from--;
+ while (++from < to && list[from] < splitter);
+ //if (head != to) {
+ list[to] = list[from];
+ list[from++] = element;
+ //oldHead = list[head];
+ //list[head] = element;
+ //list[i] = oldHead;
+
+ //head++;
+ //}
+ //head++;
+ }
+ //System.out.println("after ="+new IntArrayList(list)+", head="+head);
+ }
+ */
+
+ /*
+ int i=from-1;
+ int head = from;
+ int trail = to;
+ while (++i <= trail) {
+ int element = list[i];
+ if (element < splitter) {
+ if (head == i) head++;
+ else {
+ // swap list[i] with list[from]
+ int oldHead = list[head];
+ int oldTrail = list[trail];
+ list[head++] = element;
+ list[i--] = oldTrail;
+ list[trail--] = oldHead;
+ }
+ }
+ //System.out.println(new IntArrayList(list));
+
+ }
+ */
+
+
+ return from-1;
+ //return head-1;
+}
+/**
+ * Same as {@link #partition(int[],int,int,int[],int,int,int[])}
+ * except that it partitions <tt>Object[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static void partition(Object[] list, int from, int to, Object[] splitters, int splitFrom, int splitTo, int[] splitIndexes, java.util.Comparator comp) {
+ Object splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s, comp);
+ m = med3(list, m-s, m, m+s, comp);
+ n = med3(list, n-2*s, n-s, n, comp);
+ }
+ m = med3(list, l, m, n, comp); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo,comp);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = partition(list,from,to,splitter,comp);
+ splitIndexes[medianIndex] = splitIndex;
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(comp.compare(splitter,splitters[i]) < 0))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(comp.compare(splitter,splitters[i]) > 0))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ partition(list, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes, comp);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ partition(list, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes, comp);
+ }
+}
+/**
+ * Same as {@link #partition(int[],int,int,int)}
+ * except that it <i>synchronously</i> partitions the objects of the given list by the order of the given comparator.
+ */
+public static int partition(Object[] list, int from, int to, Object splitter, java.util.Comparator comp) {
+ Object element; // int, double --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (comp.compare(element,splitter) < 0) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from] = element;
+ from++;
+ }
+ }
+ return from-1;
+}
+/**
+ * Equivalent to <tt>partition(list.elements(), from, to, splitters.elements(), 0, splitters.size()-1, splitIndexes.elements())</tt>.
+ */
+public static void partition(DoubleArrayList list, int from, int to, DoubleArrayList splitters, IntArrayList splitIndexes) {
+ partition(list.elements(),from,to,splitters.elements(),0,splitters.size()-1,splitIndexes.elements());
+}
+/**
+ * Equivalent to <tt>partition(list.elements(), from, to, splitters.elements(), 0, splitters.size()-1, splitIndexes.elements())</tt>.
+ */
+public static void partition(IntArrayList list, int from, int to, IntArrayList splitters, IntArrayList splitIndexes) {
+ partition(list.elements(),from,to,splitters.elements(),0,splitters.size()-1,splitIndexes.elements());
+}
+/**
+ * Same as {@link #triplePartition(int[],int[],int[],int,int,int[],int,int,int[])}
+ * except that it <i>synchronously</i> partitions <tt>double[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static void triplePartition(double[] list, double[] secondary, double[] tertiary, int from, int to, double[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
+ double splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s);
+ m = med3(list, m-s, m, m+s);
+ n = med3(list, n-2*s, n-s, n);
+ }
+ m = med3(list, l, m, n); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = triplePartition(list,secondary,tertiary,from,to,splitter);
+ splitIndexes[medianIndex] = splitIndex;
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(splitter < splitters[i]))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(splitter > splitters[i]))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ triplePartition(list, secondary, tertiary, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ triplePartition(list, secondary, tertiary, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+}
+/**
+ * Same as {@link #triplePartition(int[],int[],int[],int,int,int)}
+ * except that it <i>synchronously</i> partitions <tt>double[]</tt> rather than <tt>int[]</tt> arrays.
+ */
+public static int triplePartition(double[] list, double[] secondary, double[] tertiary, int from, int to, double splitter) {
+ double element; // int, double --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from] = element;
+
+ element = secondary[i];
+ secondary[i] = secondary[from];
+ secondary[from] = element;
+
+ element = tertiary[i];
+ tertiary[i] = tertiary[from];
+ tertiary[from++] = element;
+ }
+ }
+
+ return from-1;
+}
+/**
+ * Same as {@link #partition(int[],int,int,int[],int,int,int[])} except that this method <i>synchronously</i> partitions three arrays at the same time;
+ * all three arrays are partially sorted according to the elements of the primary array.
+ * In other words, each time an element in the primary array is moved from index A to B, the correspoding element within the secondary array as well as the corresponding element within the tertiary array are also moved from index A to B.
+ * <p>
+ * <b>Use cases:</b>
+ * <p>
+ * Image having a large list of 3-dimensional points.
+ * If memory consumption and performance matter, it is a good idea to physically lay them out as three 1-dimensional arrays
+ * (using something like <tt>Point3D</tt> objects would be prohibitively expensive, both in terms of time and space).
+ * Now imagine wanting to histogram the points.
+ * We may want to partially sort the points by x-coordinate into intervals.
+ * This method efficiently does the job.
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Same as for single-partition methods.
+ */
+public static void triplePartition(int[] list, int[] secondary, int[] tertiary, int from, int to, int[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
+ int splitter; // int, double --> template type dependent
+
+ if (splitFrom>splitTo) return; // nothing to do
+ if (from>to) { // all bins are empty
+ from--;
+ for (int i = splitFrom; i<=splitTo; ) splitIndexes[i++] = from;
+ return;
+ }
+
+ // Choose a partition (pivot) index, m
+ // Ideally, the pivot should be the median, because a median splits a list into two equal sized sublists.
+ // However, computing the median is expensive, so we use an approximation.
+ int medianIndex;
+ if (splitFrom==splitTo) { // we don't really have a choice
+ medianIndex = splitFrom;
+ }
+ else { // we do have a choice
+ int m = (from+to) / 2; // Small arrays, middle element
+ int len = to-from+1;
+ if (len > SMALL) {
+ int l = from;
+ int n = to;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(list, l, l+s, l+2*s);
+ m = med3(list, m-s, m, m+s);
+ n = med3(list, n-2*s, n-s, n);
+ }
+ m = med3(list, l, m, n); // Mid-size, pseudomedian of 3
+ }
+
+ // Find the splitter closest to the pivot, i.e. the splitter that best splits the list into two equal sized sublists.
+ medianIndex = Sorting.binarySearchFromTo(splitters,list[m],splitFrom,splitTo);
+ if (medianIndex < 0) medianIndex = -medianIndex - 1; // not found
+ if (medianIndex > splitTo) medianIndex = splitTo; // not found, one past the end
+
+ }
+ splitter = splitters[medianIndex];
+
+ // Partition the list according to the splitter, i.e.
+ // Establish invariant: list[i] < splitter <= list[j] for i=from..medianIndex and j=medianIndex+1 .. to
+ int splitIndex = triplePartition(list,secondary,tertiary,from,to,splitter);
+ splitIndexes[medianIndex] = splitIndex;
+
+ // Optimization: Handle special cases to cut down recursions.
+ if (splitIndex < from) { // no element falls into this bin
+ // all bins with splitters[i] <= splitter are empty
+ int i = medianIndex-1;
+ while (i>=splitFrom && (!(splitter < splitters[i]))) splitIndexes[i--] = splitIndex;
+ splitFrom = medianIndex+1;
+ }
+ else if (splitIndex >= to) { // all elements fall into this bin
+ // all bins with splitters[i] >= splitter are empty
+ int i = medianIndex+1;
+ while (i<=splitTo && (!(splitter > splitters[i]))) splitIndexes[i++] = splitIndex;
+ splitTo = medianIndex-1;
+ }
+
+ // recursively partition left half
+ if (splitFrom <= medianIndex-1) {
+ triplePartition(list, secondary, tertiary, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ triplePartition(list, secondary, tertiary, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+}
+/**
+ * Same as {@link #partition(int[],int,int,int)} except that this method <i>synchronously</i> partitions three arrays at the same time;
+ * all three arrays are partially sorted according to the elements of the primary array.
+ * In other words, each time an element in the primary array is moved from index A to B, the correspoding element within the secondary array as well as the corresponding element within the tertiary array are also moved from index A to B.
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Same as for single-partition methods.
+ */
+public static int triplePartition(int[] list, int[] secondary, int[] tertiary, int from, int to, int splitter) {
+ int element; // int, double --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = list[i];
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ list[i] = list[from];
+ list[from] = element;
+
+ element = secondary[i];
+ secondary[i] = secondary[from];
+ secondary[from] = element;
+
+ element = tertiary[i];
+ tertiary[i] = tertiary[from];
+ tertiary[from++] = element;
+ }
+ }
+
+ return from-1;
+}
+}
Propchange: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Partitioning.java
------------------------------------------------------------------------------
svn:eol-style = native