You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by sr...@apache.org on 2009/11/25 04:41:31 UTC
svn commit: r883974 [20/20] - in
/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix:
./ bench/ doublealgo/ impl/ linalg/ objectalgo/
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Partitioning.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Partitioning.java?rev=883974&r1=883973&r2=883974&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Partitioning.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Partitioning.java Wed Nov 25 03:41:28 2009
@@ -23,8 +23,6 @@
*
* @see org.apache.mahout.matrix.Partitioning "Partitioning arrays (provides more documentation)"
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
@@ -53,42 +51,42 @@
<b>Example:</b>
<table border="1" cellspacing="0">
<tr nowrap>
- <td valign="top"><tt>8 x 3 matrix:<br>
- 23, 22, 21<br>
- 20, 19, 18<br>
- 17, 16, 15<br>
- 14, 13, 12<br>
- 11, 10, 9<br>
- 8, 7, 6<br>
- 5, 4, 3<br>
- 2, 1, 0 </tt></td>
- <td align="left" valign="top">
- <p><tt>column = 0;<br>
- rowIndexes = {0,1,2,..,matrix.rows()-1};
- rowFrom = 0;<br>
- rowTo = matrix.rows()-1;<br>
- splitters = {5,10,12}<br>
- c = 0; <br>
- d = splitters.length-1;<br>
- partition(matrix,rowIndexes,rowFrom,rowTo,column,splitters,c,d,splitIndexes);<br>
- ==><br>
- splitIndexes == {0, 2, 3}<br>
- rowIndexes == {7, 6, 5, 4, 0, 1, 2, 3}</tt></p>
- </td>
- <td valign="top">
- The matrix IS NOT REORDERED.<br>
- Here is how it would look<br>
- like, if it would be reordered<br>
- accoring to <tt>rowIndexes</tt>.<br>
- <tt>8 x 3 matrix:<br>
- 2, 1, 0<br>
- 5, 4, 3<br>
- 8, 7, 6<br>
- 11, 10, 9<br>
- 23, 22, 21<br>
- 20, 19, 18<br>
- 17, 16, 15<br>
- 14, 13, 12 </tt></td>
+ <td valign="top"><tt>8 x 3 matrix:<br>
+ 23, 22, 21<br>
+ 20, 19, 18<br>
+ 17, 16, 15<br>
+ 14, 13, 12<br>
+ 11, 10, 9<br>
+ 8, 7, 6<br>
+ 5, 4, 3<br>
+ 2, 1, 0 </tt></td>
+ <td align="left" valign="top">
+ <p><tt>column = 0;<br>
+ rowIndexes = {0,1,2,..,matrix.rows()-1};
+ rowFrom = 0;<br>
+ rowTo = matrix.rows()-1;<br>
+ splitters = {5,10,12}<br>
+ c = 0; <br>
+ d = splitters.length-1;<br>
+ partition(matrix,rowIndexes,rowFrom,rowTo,column,splitters,c,d,splitIndexes);<br>
+ ==><br>
+ splitIndexes == {0, 2, 3}<br>
+ rowIndexes == {7, 6, 5, 4, 0, 1, 2, 3}</tt></p>
+ </td>
+ <td valign="top">
+ The matrix IS NOT REORDERED.<br>
+ Here is how it would look<br>
+ like, if it would be reordered<br>
+ accoring to <tt>rowIndexes</tt>.<br>
+ <tt>8 x 3 matrix:<br>
+ 2, 1, 0<br>
+ 5, 4, 3<br>
+ 8, 7, 6<br>
+ 11, 10, 9<br>
+ 23, 22, 21<br>
+ 20, 19, 18<br>
+ 17, 16, 15<br>
+ 14, 13, 12 </tt></td>
</tr>
</table>
@param matrix the matrix to be partitioned.
@@ -97,64 +95,64 @@
@param rowTo the index of the last row (inclusive).
@param column the index of the column to partition on.
@param splitters the values at which the rows 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.
+ 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>.
+ The method considers the splitter elements <tt>splitters[splitFrom] .. splitters[splitTo]</tt>.
@param splitIndexes a list into which this method fills the indexes of rows delimiting intervals.
Upon return <tt>splitIndexes[splitFrom..splitTo]</tt> will be set accordingly.
Therefore, must satisfy <tt>splitIndexes.length >= splitters.length</tt>.
*/
public static void partition(ObjectMatrix2D matrix, int[] rowIndexes, int rowFrom, int rowTo, int column, final Object[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
- if (rowFrom < 0 || rowTo >= matrix.rows() || rowTo >= rowIndexes.length) throw new IllegalArgumentException();
- if (column < 0 || column >= matrix.columns()) throw new IllegalArgumentException();
- if (splitFrom < 0 || splitTo >= splitters.length) throw new IllegalArgumentException();
- if (splitIndexes.length < splitters.length) throw new IllegalArgumentException();
-
- // this one knows how to swap two row indexes (a,b)
- final int[] g = rowIndexes;
- Swapper swapper = new Swapper() {
- public void swap(int b, int c) {
- int tmp = g[b]; g[b] = g[c]; g[c] = tmp;
- }
- };
-
- // compare splitter[a] with columnView[rowIndexes[b]]
- final ObjectMatrix1D columnView = matrix.viewColumn(column);
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- Comparable av = (Comparable) (splitters[a]);
- Comparable bv = (Comparable) (columnView.getQuick(g[b]));
- int r = av.compareTo(bv);
- return r<0 ? -1 : (r==0 ? 0 : 1);
- }
- };
-
- // compare columnView[rowIndexes[a]] with columnView[rowIndexes[b]]
- IntComparator comp2 = new IntComparator() {
- public int compare(int a, int b) {
- Comparable av = (Comparable) (columnView.getQuick(g[a]));
- Comparable bv = (Comparable) (columnView.getQuick(g[b]));
- int r = av.compareTo(bv);
- return r<0 ? -1 : (r==0 ? 0 : 1);
- }
- };
-
- // compare splitter[a] with splitter[b]
- IntComparator comp3 = new IntComparator() {
- public int compare(int a, int b) {
- Comparable av = (Comparable) (splitters[a]);
- Comparable bv = (Comparable) (splitters[b]);
- int r = av.compareTo(bv);
- return r<0 ? -1 : (r==0 ? 0 : 1);
- }
- };
+ if (rowFrom < 0 || rowTo >= matrix.rows() || rowTo >= rowIndexes.length) throw new IllegalArgumentException();
+ if (column < 0 || column >= matrix.columns()) throw new IllegalArgumentException();
+ if (splitFrom < 0 || splitTo >= splitters.length) throw new IllegalArgumentException();
+ if (splitIndexes.length < splitters.length) throw new IllegalArgumentException();
+
+ // this one knows how to swap two row indexes (a,b)
+ final int[] g = rowIndexes;
+ Swapper swapper = new Swapper() {
+ public void swap(int b, int c) {
+ int tmp = g[b]; g[b] = g[c]; g[c] = tmp;
+ }
+ };
+
+ // compare splitter[a] with columnView[rowIndexes[b]]
+ final ObjectMatrix1D columnView = matrix.viewColumn(column);
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ Comparable av = (Comparable) (splitters[a]);
+ Comparable bv = (Comparable) (columnView.getQuick(g[b]));
+ int r = av.compareTo(bv);
+ return r<0 ? -1 : (r==0 ? 0 : 1);
+ }
+ };
+
+ // compare columnView[rowIndexes[a]] with columnView[rowIndexes[b]]
+ IntComparator comp2 = new IntComparator() {
+ public int compare(int a, int b) {
+ Comparable av = (Comparable) (columnView.getQuick(g[a]));
+ Comparable bv = (Comparable) (columnView.getQuick(g[b]));
+ int r = av.compareTo(bv);
+ return r<0 ? -1 : (r==0 ? 0 : 1);
+ }
+ };
+
+ // compare splitter[a] with splitter[b]
+ IntComparator comp3 = new IntComparator() {
+ public int compare(int a, int b) {
+ Comparable av = (Comparable) (splitters[a]);
+ Comparable bv = (Comparable) (splitters[b]);
+ int r = av.compareTo(bv);
+ return r<0 ? -1 : (r==0 ? 0 : 1);
+ }
+ };
- // generic partitioning does the main work of reordering row indexes
- org.apache.mahout.matrix.Partitioning.genericPartition(rowFrom,rowTo,splitFrom,splitTo,splitIndexes,comp,comp2,comp3,swapper);
+ // generic partitioning does the main work of reordering row indexes
+ org.apache.mahout.matrix.Partitioning.genericPartition(rowFrom,rowTo,splitFrom,splitTo,splitIndexes,comp,comp2,comp3,swapper);
}
/**
Same as {@link org.apache.mahout.matrix.Partitioning#partition(int[],int,int,int[],int,int,int[])}
@@ -174,41 +172,41 @@
<b>Example:</b>
<table border="1" cellspacing="0">
<tr nowrap>
- <td valign="top"><tt>8 x 3 matrix:<br>
- 23, 22, 21<br>
- 20, 19, 18<br>
- 17, 16, 15<br>
- 14, 13, 12<br>
- 11, 10, 9<br>
- 8, 7, 6<br>
- 5, 4, 3<br>
- 2, 1, 0 </tt></td>
- <td align="left" valign="top">
- <tt>column = 0;<br>
- splitters = {5,10,12}<br>
- partition(matrix,column,splitters,splitIndexes);<br>
- ==><br>
- splitIndexes == {0, 2, 3}</tt></p>
- </td>
- <td valign="top">
- The matrix IS NOT REORDERED.<br>
- The new VIEW IS REORDERED:<br>
- <tt>8 x 3 matrix:<br>
- 2, 1, 0<br>
- 5, 4, 3<br>
- 8, 7, 6<br>
- 11, 10, 9<br>
- 23, 22, 21<br>
- 20, 19, 18<br>
- 17, 16, 15<br>
- 14, 13, 12 </tt></td>
+ <td valign="top"><tt>8 x 3 matrix:<br>
+ 23, 22, 21<br>
+ 20, 19, 18<br>
+ 17, 16, 15<br>
+ 14, 13, 12<br>
+ 11, 10, 9<br>
+ 8, 7, 6<br>
+ 5, 4, 3<br>
+ 2, 1, 0 </tt></td>
+ <td align="left" valign="top">
+ <tt>column = 0;<br>
+ splitters = {5,10,12}<br>
+ partition(matrix,column,splitters,splitIndexes);<br>
+ ==><br>
+ splitIndexes == {0, 2, 3}</tt></p>
+ </td>
+ <td valign="top">
+ The matrix IS NOT REORDERED.<br>
+ The new VIEW IS REORDERED:<br>
+ <tt>8 x 3 matrix:<br>
+ 2, 1, 0<br>
+ 5, 4, 3<br>
+ 8, 7, 6<br>
+ 11, 10, 9<br>
+ 23, 22, 21<br>
+ 20, 19, 18<br>
+ 17, 16, 15<br>
+ 14, 13, 12 </tt></td>
</tr>
</table>
@param matrix the matrix to be partitioned.
@param column the index of the column to partition on.
@param splitters the values at which the rows 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.
+ Must be sorted ascending and must not contain multiple identical values.
+ These preconditions are not checked; be sure that they are met.
@param splitIndexes a list into which this method fills the indexes of rows delimiting intervals.
Therefore, must satisfy <tt>splitIndexes.length >= splitters.length</tt>.
@@ -216,21 +214,21 @@
@return a new matrix view having rows partitioned by the given column and splitters.
*/
public static ObjectMatrix2D partition(ObjectMatrix2D matrix, int column, final Object[] splitters, int[] splitIndexes) {
- int rowFrom = 0;
- int rowTo = matrix.rows()-1;
- int splitFrom = 0;
- int splitTo = splitters.length-1;
- int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder instead of matrix itself
- for (int i=rowIndexes.length; --i >= 0; ) rowIndexes[i] = i;
-
- partition(matrix,rowIndexes,rowFrom,rowTo,column,splitters,splitFrom,splitTo,splitIndexes);
-
- // take all columns in the original order
- int[] columnIndexes = new int[matrix.columns()];
- for (int i=columnIndexes.length; --i >= 0; ) columnIndexes[i] = i;
+ int rowFrom = 0;
+ int rowTo = matrix.rows()-1;
+ int splitFrom = 0;
+ int splitTo = splitters.length-1;
+ int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder instead of matrix itself
+ for (int i=rowIndexes.length; --i >= 0; ) rowIndexes[i] = i;
+
+ partition(matrix,rowIndexes,rowFrom,rowTo,column,splitters,splitFrom,splitTo,splitIndexes);
+
+ // take all columns in the original order
+ int[] columnIndexes = new int[matrix.columns()];
+ for (int i=columnIndexes.length; --i >= 0; ) columnIndexes[i] = i;
- // view the matrix according to the reordered row indexes
- return matrix.viewSelection(rowIndexes,columnIndexes);
+ // view the matrix according to the reordered row indexes
+ return matrix.viewSelection(rowIndexes,columnIndexes);
}
/**
Same as {@link #partition(int[],int,int,int[],int,int,int[])}
@@ -254,108 +252,108 @@
<b>Example:</b>
<table border="1" cellspacing="0">
<tr nowrap>
- <td valign="top"><tt>8 x 3 matrix:<br>
- 23, 22, 21<br>
- 20, 19, 18<br>
- 17, 16, 15<br>
- 14, 13, 12<br>
- 11, 10, 9<br>
- 8, 7, 6<br>
- 5, 4, 3<br>
- 2, 1, 0 </tt></td>
- <td align="left">
- <p><tt>column = matrix.viewColumn(0);<br>
- a = 0;<br>
- b = column.size()-1;</tt><tt><br>
- splitters={5,10,12}<br>
- c=0; <br>
- d=splitters.length-1;</tt><tt><br>
- partition(matrix,column,a,b,splitters,c,d,splitIndexes);<br>
- ==><br>
- splitIndexes == {0, 2, 3}</tt></p>
- </td>
- <td valign="top"><tt>8 x 3 matrix:<br>
- 2, 1, 0<br>
- 5, 4, 3<br>
- 8, 7, 6<br>
- 11, 10, 9<br>
- 23, 22, 21<br>
- 20, 19, 18<br>
- 17, 16, 15<br>
- 14, 13, 12 </tt></td>
+ <td valign="top"><tt>8 x 3 matrix:<br>
+ 23, 22, 21<br>
+ 20, 19, 18<br>
+ 17, 16, 15<br>
+ 14, 13, 12<br>
+ 11, 10, 9<br>
+ 8, 7, 6<br>
+ 5, 4, 3<br>
+ 2, 1, 0 </tt></td>
+ <td align="left">
+ <p><tt>column = matrix.viewColumn(0);<br>
+ a = 0;<br>
+ b = column.size()-1;</tt><tt><br>
+ splitters={5,10,12}<br>
+ c=0; <br>
+ d=splitters.length-1;</tt><tt><br>
+ partition(matrix,column,a,b,splitters,c,d,splitIndexes);<br>
+ ==><br>
+ splitIndexes == {0, 2, 3}</tt></p>
+ </td>
+ <td valign="top"><tt>8 x 3 matrix:<br>
+ 2, 1, 0<br>
+ 5, 4, 3<br>
+ 8, 7, 6<br>
+ 11, 10, 9<br>
+ 23, 22, 21<br>
+ 20, 19, 18<br>
+ 17, 16, 15<br>
+ 14, 13, 12 </tt></td>
</tr>
</table>
*/
private static void xPartitionOld(ObjectMatrix2D matrix, ObjectMatrix1D column, int from, int to, Object[] splitters, int splitFrom, int splitTo, int[] splitIndexes) {
- /*
- Object splitter; // int, Object --> 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(column, l, l+s, l+2*s);
- m = med3(column, m-s, m, m+s);
- n = med3(column, n-2*s, n-s, n);
- }
- m = med3(column, 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 = org.apache.mahout.matrix.Sorting.binarySearchFromTo(splitters,column.getQuick(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 = xPartitionOld(matrix,column,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) {
- xPartitionOld(matrix, column, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
- }
-
- // recursively partition right half
- if (medianIndex+1 <= splitTo) {
- xPartitionOld(matrix, column, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
- }
- */
+ /*
+ Object splitter; // int, Object --> 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(column, l, l+s, l+2*s);
+ m = med3(column, m-s, m, m+s);
+ n = med3(column, n-2*s, n-s, n);
+ }
+ m = med3(column, 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 = org.apache.mahout.matrix.Sorting.binarySearchFromTo(splitters,column.getQuick(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 = xPartitionOld(matrix,column,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) {
+ xPartitionOld(matrix, column, from, splitIndex, splitters, splitFrom, medianIndex-1, splitIndexes);
+ }
+
+ // recursively partition right half
+ if (medianIndex+1 <= splitTo) {
+ xPartitionOld(matrix, column, splitIndex+1, to, splitters, medianIndex+1, splitTo, splitIndexes);
+ }
+ */
}
/**
* Same as {@link #partition(int[],int,int,int)}
@@ -377,18 +375,18 @@
* Note that arguments are not checked for validity.
*/
private static int xPartitionOld(ObjectMatrix2D matrix, ObjectMatrix1D column, int from, int to, Object splitter) {
- /*
- Object element; // int, Object --> template type dependent
- for (int i=from-1; ++i<=to; ) {
- element = column.getQuick(i);
- if (element < splitter) {
- // swap x[i] with x[from]
- matrix.swapRows(i,from);
- from++;
- }
- }
- return from-1;
- */
- return 0;
+ /*
+ Object element; // int, Object --> template type dependent
+ for (int i=from-1; ++i<=to; ) {
+ element = column.getQuick(i);
+ if (element < splitter) {
+ // swap x[i] with x[from]
+ matrix.swapRows(i,from);
+ from++;
+ }
+ }
+ return from-1;
+ */
+ return 0;
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Sorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Sorting.java?rev=883974&r1=883973&r2=883974&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Sorting.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/objectalgo/Sorting.java Wed Nov 25 03:41:28 2009
@@ -41,31 +41,31 @@
*/
@Deprecated
public class Sorting extends org.apache.mahout.matrix.PersistentObject {
- /**
- * A prefabricated quicksort.
- */
- public static final Sorting quickSort = new Sorting(); // already has quicksort implemented
-
- /**
- * A prefabricated mergesort.
- */
- public static final Sorting mergeSort = new Sorting() { // override quicksort with mergesort
- protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
- org.apache.mahout.matrix.Sorting.mergeSort(a,fromIndex,toIndex,c);
- }
- protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.matrix.Swapper swapper) {
- org.apache.mahout.matrix.GenericSorting.mergeSort(fromIndex, toIndex, c, swapper);
- }
- };
+ /**
+ * A prefabricated quicksort.
+ */
+ public static final Sorting quickSort = new Sorting(); // already has quicksort implemented
+
+ /**
+ * A prefabricated mergesort.
+ */
+ public static final Sorting mergeSort = new Sorting() { // override quicksort with mergesort
+ protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
+ org.apache.mahout.matrix.Sorting.mergeSort(a,fromIndex,toIndex,c);
+ }
+ protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.matrix.Swapper swapper) {
+ org.apache.mahout.matrix.GenericSorting.mergeSort(fromIndex, toIndex, c, swapper);
+ }
+ };
/**
* Makes this class non instantiable, but still let's others inherit from it.
*/
protected Sorting() {}
protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
- org.apache.mahout.matrix.Sorting.quickSort(a,fromIndex,toIndex,c);
+ org.apache.mahout.matrix.Sorting.quickSort(a,fromIndex,toIndex,c);
}
protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.matrix.Swapper swapper) {
- org.apache.mahout.matrix.GenericSorting.quickSort(fromIndex, toIndex, c, swapper);
+ org.apache.mahout.matrix.GenericSorting.quickSort(fromIndex, toIndex, c, swapper);
}
/**
Sorts the vector into ascending order, according to the <i>natural ordering</i>.
@@ -75,36 +75,36 @@
<b>Example:</b>
<table border="1" cellspacing="0">
<tr nowrap>
- <td valign="top"><tt> 7, 1, 3, 1<br>
- </tt></td>
- <td valign="top">
- <p><tt> ==> 1, 1, 3, 7<br>
- The vector IS NOT SORTED.<br>
- The new VIEW IS SORTED.</tt></p>
- </td>
+ <td valign="top"><tt> 7, 1, 3, 1<br>
+ </tt></td>
+ <td valign="top">
+ <p><tt> ==> 1, 1, 3, 7<br>
+ The vector IS NOT SORTED.<br>
+ The new VIEW IS SORTED.</tt></p>
+ </td>
</tr>
</table>
@param vector the vector to be sorted.
@return a new sorted vector (matrix) view.
- <b>Note that the original matrix is left unaffected.</b>
+ <b>Note that the original matrix is left unaffected.</b>
*/
public ObjectMatrix1D sort(final ObjectMatrix1D vector) {
- int[] indexes = new int[vector.size()]; // row indexes to reorder instead of matrix itself
- for (int i=indexes.length; --i >= 0; ) indexes[i] = i;
+ int[] indexes = new int[vector.size()]; // row indexes to reorder instead of matrix itself
+ for (int i=indexes.length; --i >= 0; ) indexes[i] = i;
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- Comparable av = (Comparable) (vector.getQuick(a));
- Comparable bv = (Comparable) (vector.getQuick(b));
- int r = av.compareTo(bv);
- return r<0 ? -1 : (r>0 ? 1 : 0);
- }
- };
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ Comparable av = (Comparable) (vector.getQuick(a));
+ Comparable bv = (Comparable) (vector.getQuick(b));
+ int r = av.compareTo(bv);
+ return r<0 ? -1 : (r>0 ? 1 : 0);
+ }
+ };
- runSort(indexes,0,indexes.length,comp);
+ runSort(indexes,0,indexes.length,comp);
- return vector.viewSelection(indexes);
+ return vector.viewSelection(indexes);
}
/**
Sorts the vector into ascending order, according to the order induced by the specified comparator.
@@ -127,21 +127,21 @@
@param vector the vector to be sorted.
@param c the comparator to determine the order.
@return a new matrix view sorted as specified.
- <b>Note that the original vector (matrix) is left unaffected.</b>
+ <b>Note that the original vector (matrix) is left unaffected.</b>
*/
public ObjectMatrix1D sort(final ObjectMatrix1D vector, final java.util.Comparator c) {
- int[] indexes = new int[vector.size()]; // row indexes to reorder instead of matrix itself
- for (int i=indexes.length; --i >= 0; ) indexes[i] = i;
+ int[] indexes = new int[vector.size()]; // row indexes to reorder instead of matrix itself
+ for (int i=indexes.length; --i >= 0; ) indexes[i] = i;
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- return c.compare(vector.getQuick(a), vector.getQuick(b));
- }
- };
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ return c.compare(vector.getQuick(a), vector.getQuick(b));
+ }
+ };
- runSort(indexes,0,indexes.length,comp);
+ runSort(indexes,0,indexes.length,comp);
- return vector.viewSelection(indexes);
+ return vector.viewSelection(indexes);
}
/**
Sorts the matrix rows into ascending order, according to the <i>natural ordering</i> of the matrix values in the given column.
@@ -151,57 +151,57 @@
<b>Example:</b>
<table border="1" cellspacing="0">
<tr nowrap>
- <td valign="top"><tt>4 x 2 matrix: <br>
- 7, 6<br>
- 5, 4<br>
- 3, 2<br>
- 1, 0 <br>
- </tt></td>
- <td align="left" valign="top">
- <p><tt>column = 0;<br>
- view = quickSort(matrix,column);<br>
- System.out.println(view); </tt><tt><br>
- ==> </tt></p>
- </td>
- <td valign="top">
- <p><tt>4 x 2 matrix:<br>
- 1, 0<br>
- 3, 2<br>
- 5, 4<br>
- 7, 6</tt><br>
- The matrix IS NOT SORTED.<br>
- The new VIEW IS SORTED.</p>
- </td>
+ <td valign="top"><tt>4 x 2 matrix: <br>
+ 7, 6<br>
+ 5, 4<br>
+ 3, 2<br>
+ 1, 0 <br>
+ </tt></td>
+ <td align="left" valign="top">
+ <p><tt>column = 0;<br>
+ view = quickSort(matrix,column);<br>
+ System.out.println(view); </tt><tt><br>
+ ==> </tt></p>
+ </td>
+ <td valign="top">
+ <p><tt>4 x 2 matrix:<br>
+ 1, 0<br>
+ 3, 2<br>
+ 5, 4<br>
+ 7, 6</tt><br>
+ The matrix IS NOT SORTED.<br>
+ The new VIEW IS SORTED.</p>
+ </td>
</tr>
</table>
@param matrix the matrix to be sorted.
@param column the index of the column inducing the order.
@return a new matrix view having rows sorted by the given column.
- <b>Note that the original matrix is left unaffected.</b>
+ <b>Note that the original matrix is left unaffected.</b>
@throws IndexOutOfBoundsException if <tt>column < 0 || column >= matrix.columns()</tt>.
*/
public ObjectMatrix2D sort(ObjectMatrix2D matrix, int column) {
- if (column < 0 || column >= matrix.columns()) throw new IndexOutOfBoundsException("column="+column+", matrix="+Formatter.shape(matrix));
+ if (column < 0 || column >= matrix.columns()) throw new IndexOutOfBoundsException("column="+column+", matrix="+Formatter.shape(matrix));
- int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder instead of matrix itself
- for (int i=rowIndexes.length; --i >= 0; ) rowIndexes[i] = i;
+ int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder instead of matrix itself
+ for (int i=rowIndexes.length; --i >= 0; ) rowIndexes[i] = i;
- final ObjectMatrix1D col = matrix.viewColumn(column);
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- Comparable av = (Comparable) (col.getQuick(a));
- Comparable bv = (Comparable) (col.getQuick(b));
- int r = av.compareTo(bv);
- return r<0 ? -1 : (r>0 ? 1 : 0);
- }
- };
-
- runSort(rowIndexes,0,rowIndexes.length,comp);
-
- // view the matrix according to the reordered row indexes
- // take all columns in the original order
- return matrix.viewSelection(rowIndexes,null);
+ final ObjectMatrix1D col = matrix.viewColumn(column);
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ Comparable av = (Comparable) (col.getQuick(a));
+ Comparable bv = (Comparable) (col.getQuick(b));
+ int r = av.compareTo(bv);
+ return r<0 ? -1 : (r>0 ? 1 : 0);
+ }
+ };
+
+ runSort(rowIndexes,0,rowIndexes.length,comp);
+
+ // view the matrix according to the reordered row indexes
+ // take all columns in the original order
+ return matrix.viewSelection(rowIndexes,null);
}
/**
Sorts the matrix rows according to the order induced by the specified comparator.
@@ -224,27 +224,27 @@
@param matrix the matrix to be sorted.
@param c the comparator to determine the order.
@return a new matrix view having rows sorted as specified.
- <b>Note that the original matrix is left unaffected.</b>
+ <b>Note that the original matrix is left unaffected.</b>
*/
public ObjectMatrix2D sort(final ObjectMatrix2D matrix, final ObjectMatrix1DComparator c) {
- int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder instead of matrix itself
- for (int i=rowIndexes.length; --i >= 0; ) rowIndexes[i] = i;
+ int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder instead of matrix itself
+ for (int i=rowIndexes.length; --i >= 0; ) rowIndexes[i] = i;
- final ObjectMatrix1D[] views = new ObjectMatrix1D[matrix.rows()]; // precompute views for speed
- for (int i=views.length; --i >= 0; ) views[i] = matrix.viewRow(i);
+ final ObjectMatrix1D[] views = new ObjectMatrix1D[matrix.rows()]; // precompute views for speed
+ for (int i=views.length; --i >= 0; ) views[i] = matrix.viewRow(i);
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- //return c.compare(matrix.viewRow(a), matrix.viewRow(b));
- return c.compare(views[a], views[b]);
- }
- };
-
- runSort(rowIndexes,0,rowIndexes.length,comp);
-
- // view the matrix according to the reordered row indexes
- // take all columns in the original order
- return matrix.viewSelection(rowIndexes,null);
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ //return c.compare(matrix.viewRow(a), matrix.viewRow(b));
+ return c.compare(views[a], views[b]);
+ }
+ };
+
+ runSort(rowIndexes,0,rowIndexes.length,comp);
+
+ // view the matrix according to the reordered row indexes
+ // take all columns in the original order
+ return matrix.viewSelection(rowIndexes,null);
}
/**
Sorts the matrix slices into ascending order, according to the <i>natural ordering</i> of the matrix values in the given <tt>[row,column]</tt> position.
@@ -264,31 +264,31 @@
@param row the index of the row inducing the order.
@param column the index of the column inducing the order.
@return a new matrix view having slices sorted by the values of the slice view <tt>matrix.viewRow(row).viewColumn(column)</tt>.
- <b>Note that the original matrix is left unaffected.</b>
+ <b>Note that the original matrix is left unaffected.</b>
@throws IndexOutOfBoundsException if <tt>row < 0 || row >= matrix.rows() || column < 0 || column >= matrix.columns()</tt>.
*/
public ObjectMatrix3D sort(ObjectMatrix3D matrix, int row, int column) {
- if (row < 0 || row >= matrix.rows()) throw new IndexOutOfBoundsException("row="+row+", matrix="+Formatter.shape(matrix));
- if (column < 0 || column >= matrix.columns()) throw new IndexOutOfBoundsException("column="+column+", matrix="+Formatter.shape(matrix));
+ if (row < 0 || row >= matrix.rows()) throw new IndexOutOfBoundsException("row="+row+", matrix="+Formatter.shape(matrix));
+ if (column < 0 || column >= matrix.columns()) throw new IndexOutOfBoundsException("column="+column+", matrix="+Formatter.shape(matrix));
- int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder instead of matrix itself
- for (int i=sliceIndexes.length; --i >= 0; ) sliceIndexes[i] = i;
+ int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder instead of matrix itself
+ for (int i=sliceIndexes.length; --i >= 0; ) sliceIndexes[i] = i;
- final ObjectMatrix1D sliceView = matrix.viewRow(row).viewColumn(column);
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- Comparable av = (Comparable) (sliceView.getQuick(a));
- Comparable bv = (Comparable) (sliceView.getQuick(b));
- int r = av.compareTo(bv);
- return r<0 ? -1 : (r>0 ? 1 : 0);
- }
- };
-
- runSort(sliceIndexes,0,sliceIndexes.length,comp);
-
- // view the matrix according to the reordered slice indexes
- // take all rows and columns in the original order
- return matrix.viewSelection(sliceIndexes,null,null);
+ final ObjectMatrix1D sliceView = matrix.viewRow(row).viewColumn(column);
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ Comparable av = (Comparable) (sliceView.getQuick(a));
+ Comparable bv = (Comparable) (sliceView.getQuick(b));
+ int r = av.compareTo(bv);
+ return r<0 ? -1 : (r>0 ? 1 : 0);
+ }
+ };
+
+ runSort(sliceIndexes,0,sliceIndexes.length,comp);
+
+ // view the matrix according to the reordered slice indexes
+ // take all rows and columns in the original order
+ return matrix.viewSelection(sliceIndexes,null,null);
}
/**
Sorts the matrix slices according to the order induced by the specified comparator.
@@ -311,26 +311,26 @@
@param matrix the matrix to be sorted.
@param c the comparator to determine the order.
@return a new matrix view having slices sorted as specified.
- <b>Note that the original matrix is left unaffected.</b>
+ <b>Note that the original matrix is left unaffected.</b>
*/
public ObjectMatrix3D sort(final ObjectMatrix3D matrix, final ObjectMatrix2DComparator c) {
- int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder instead of matrix itself
- for (int i=sliceIndexes.length; --i >= 0; ) sliceIndexes[i] = i;
+ int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder instead of matrix itself
+ for (int i=sliceIndexes.length; --i >= 0; ) sliceIndexes[i] = i;
- final ObjectMatrix2D[] views = new ObjectMatrix2D[matrix.slices()]; // precompute views for speed
- for (int i=views.length; --i >= 0; ) views[i] = matrix.viewSlice(i);
+ final ObjectMatrix2D[] views = new ObjectMatrix2D[matrix.slices()]; // precompute views for speed
+ for (int i=views.length; --i >= 0; ) views[i] = matrix.viewSlice(i);
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- //return c.compare(matrix.viewSlice(a), matrix.viewSlice(b));
- return c.compare(views[a], views[b]);
- }
- };
-
- runSort(sliceIndexes,0,sliceIndexes.length,comp);
-
- // view the matrix according to the reordered slice indexes
- // take all rows and columns in the original order
- return matrix.viewSelection(sliceIndexes,null,null);
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ //return c.compare(matrix.viewSlice(a), matrix.viewSlice(b));
+ return c.compare(views[a], views[b]);
+ }
+ };
+
+ runSort(sliceIndexes,0,sliceIndexes.length,comp);
+
+ // view the matrix according to the reordered slice indexes
+ // take all rows and columns in the original order
+ return matrix.viewSelection(sliceIndexes,null,null);
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/package.html
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/package.html?rev=883974&r1=883973&r2=883974&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/package.html (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/matrix/package.html Wed Nov 25 03:41:28 2009
@@ -464,7 +464,7 @@
<td>
<p>Note that the result of a slicing operation is not a 2-d matrix with
one row, but a true 1-d <b>type</b> with all capabilities of the type,
- namely {@link cern.colt.matrix.DoubleMatrix1D}, generated in constant
+ namely {@link org.apache.mahout.matrix.matrix.DoubleMatrix1D}, generated in constant
time.</p>
<p>The slicing view is now fed into some external algorithm expecting a
@@ -561,9 +561,9 @@
adhere to some common interface.</p>
<p>The common interface for matrices is defined in abstract base classes (e.g.
- {@link cern.colt.matrix.DoubleMatrix2D}). Note that looking at the documentation
- of some concrete instantiable class (e.g. {@link cern.colt.matrix.impl.DenseDoubleMatrix2D},
- {@link cern.colt.matrix.impl.SparseDoubleMatrix2D}, {@link cern.colt.matrix.impl.RCDoubleMatrix2D}<img
+ {@link org.apache.mahout.matrix.matrix.DoubleMatrix2D}). Note that looking at the documentation
+ of some concrete instantiable class (e.g. {@link org.apache.mahout.matrix.matrix.impl.DenseDoubleMatrix2D},
+ {@link org.apache.mahout.matrix.matrix.impl.SparseDoubleMatrix2D}, {@link org.apache.mahout.matrix.matrix.impl.RCDoubleMatrix2D}<img
src="../doc-files/new.gif" width="32" height="22" align="top">)
will not reveal more information than can be obtained by looking at the abstract
base classes. The convention is that concrete classes <i>do no subsetting or
@@ -638,7 +638,7 @@
over time, as more and more features are added. </p>
<p>Some algorithms for formatting, sorting, statistics and partitioning, are,
- for example, provided in the package {@link cern.colt.matrix.doublealgo}. </p>
+ for example, provided in the package {@link org.apache.mahout.matrix.matrix.doublealgo}. </p>
<p><a href="#Overview">Back</a> to Overview</p>
@@ -646,7 +646,7 @@
<h2><a name="LinearAlgebra"></a>7. Linear Algebra</h2>
-<p>See the documentation of the linear algebra package {@link cern.colt.matrix.linalg}.</p>
+<p>See the documentation of the linear algebra package {@link org.apache.mahout.matrix.matrix.linalg}.</p>
<p><a href="#Overview">Back</a> to Overview </p>
@@ -659,20 +659,20 @@
a common abstract base class named <tt><ValueType>Matrix<Rank>D</tt>,
which is in many ways equivalent to an "interface". <b>99% of the
time you will operate on these abstract classes only</b>. For example, all 2-dimensional
- matrices operating on <tt>double</tt> values are derived from {@link cern.colt.matrix.DoubleMatrix2D}.
+ matrices operating on <tt>double</tt> values are derived from {@link org.apache.mahout.matrix.matrix.DoubleMatrix2D}.
This is the interface to operate on.</p>
<p>Class naming for concrete instantiable classes follows the schema <tt><Property><ValueType>Matrix<Rank>D</tt>.
- For example, we have a {@link cern.colt.matrix.impl.DenseDoubleMatrix2D}, a
- {@link cern.colt.matrix.impl.SparseDoubleMatrix2D}, a {@link cern.colt.matrix.impl.DenseIntMatrix3D},
+ For example, we have a {@link org.apache.mahout.matrix.matrix.impl.DenseDoubleMatrix2D}, a
+ {@link org.apache.mahout.matrix.matrix.impl.SparseDoubleMatrix2D}, a {@link org.apache.mahout.matrix.matrix.impl.DenseIntMatrix3D},
and so on. All concrete instantiable classes are separated into an extra package,
- {@link cern.colt.matrix.impl}, to clearly distinguish between interfaces and
+ {@link org.apache.mahout.matrix.matrix.impl}, to clearly distinguish between interfaces and
implementations.</p>
-<p>{@link cern.colt.matrix.DoubleMatrix2D} in turn is derived from an abstract
+<p>{@link org.apache.mahout.matrix.matrix.DoubleMatrix2D} in turn is derived from an abstract
base class tying together all 2-dimensional matrices regardless of value type,
- {@link cern.colt.matrix.impl.AbstractMatrix2D}, which finally is rooted in grandmother
- {@link cern.colt.matrix.impl.AbstractMatrix}.</p>
+ {@link org.apache.mahout.matrix.matrix.impl.AbstractMatrix2D}, which finally is rooted in grandmother
+ {@link org.apache.mahout.matrix.matrix.impl.AbstractMatrix}.</p>
<p>The abstract base classes provide skeleton implementations for all but few
methods. Experimental data layouts can easily be implemented and inherit a rich
@@ -697,7 +697,7 @@
no methods to fill results into empty result matrices. Use idioms like <tt>result
= matrix.copy().mult(5)</tt> to achieve the same functionality. Some convenience
methods are provided in the factory classes as well as in external packages
- like {@link cern.colt.matrix.doublealgo}.</p>
+ like {@link org.apache.mahout.matrix.matrix.doublealgo}.</p>
<p><a href="#Overview">Back</a> to Overview
@@ -784,4 +784,4 @@
<p><a href="#Overview">Back</a> to Overview</p>
</BODY>
-</HTML>
\ No newline at end of file
+</HTML>