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/12/18 00:22:41 UTC
svn commit: r891983 [34/47] - in /lucene/mahout/trunk: ./ core/
core/src/main/java/org/apache/mahout/cf/taste/hadoop/item/
core/src/main/java/org/apache/mahout/clustering/
core/src/main/java/org/apache/mahout/clustering/canopy/
core/src/main/java/org/a...
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,497 @@
+/*
+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.math.matrix.doublealgo;
+
+import org.apache.mahout.math.GenericSorting;
+import org.apache.mahout.math.PersistentObject;
+import org.apache.mahout.math.Swapper;
+import org.apache.mahout.math.function.IntComparator;
+import org.apache.mahout.math.matrix.DoubleMatrix1D;
+import org.apache.mahout.math.matrix.DoubleMatrix2D;
+import org.apache.mahout.math.matrix.DoubleMatrix3D;
+import org.apache.mahout.math.matrix.impl.AbstractFormatter;
+
+/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
+@Deprecated
+public class Sorting extends 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
+
+ @Override
+ protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
+ org.apache.mahout.math.Sorting.mergeSort(a, fromIndex, toIndex, c);
+ }
+
+ @Override
+ protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.math.Swapper swapper) {
+ GenericSorting.mergeSort(fromIndex, toIndex, c, swapper);
+ }
+ };
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ protected Sorting() {
+ }
+
+ /** Compare two values, one of which is assumed to be Double.NaN */
+ private static int compareNaN(double a, double b) {
+ if (a != a) {
+ if (b != b) {
+ return 0; // NaN equals NaN
+ } else {
+ return 1;
+ } // e.g. NaN > 5
+ }
+ return -1; // e.g. 5 < NaN
+ }
+
+ protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
+ org.apache.mahout.math.Sorting.quickSort(a, fromIndex, toIndex, c);
+ }
+
+ protected void runSort(int fromIndex, int toIndex, IntComparator c, org.apache.mahout.math.Swapper swapper) {
+ GenericSorting.quickSort(fromIndex, toIndex, c, swapper);
+ }
+
+ /**
+ * Sorts the vector into ascending order, according to the <i>natural ordering</i>. The returned view is backed by
+ * this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. To sort ranges use
+ * sub-ranging views. To sort descending, use flip views ... <p> <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> </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>
+ */
+ public DoubleMatrix1D sort(final DoubleMatrix1D 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;
+ }
+
+ IntComparator comp = new IntComparator() {
+ @Override
+ public int compare(int a, int b) {
+ double av = vector.getQuick(a);
+ double bv = vector.getQuick(b);
+ if (av != av || bv != bv) {
+ return compareNaN(av, bv);
+ } // swap NaNs to the end
+ return av < bv ? -1 : (av == bv ? 0 : 1);
+ }
+ };
+
+ runSort(indexes, 0, indexes.length, comp);
+
+ return vector.viewSelection(indexes);
+ }
+
+ /**
+ * Sorts the vector into ascending order, according to the order induced by the specified comparator. The returned
+ * view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. The
+ * algorithm compares two cells at a time, determinining whether one is smaller, equal or larger than the other. To
+ * sort ranges use sub-ranging views. To sort descending, use flip views ... <p> <b>Example:</b>
+ * <pre>
+ * // sort by sinus of cells
+ * DoubleComparator comp = new DoubleComparator() {
+ * public int compare(double a, double b) {
+ * double as = Math.sin(a); double bs = Math.sin(b);
+ * return as < bs ? -1 : as == bs ? 0 : 1;
+ * }
+ * };
+ * sorted = quickSort(vector,comp);
+ * </pre>
+ *
+ * @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>
+ */
+ public DoubleMatrix1D sort(final DoubleMatrix1D vector, final org.apache.mahout.math.function.DoubleComparator 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;
+ }
+
+ IntComparator comp = new IntComparator() {
+ @Override
+ public int compare(int a, int b) {
+ return c.compare(vector.getQuick(a), vector.getQuick(b));
+ }
+ };
+
+ runSort(indexes, 0, indexes.length, comp);
+
+ return vector.viewSelection(indexes);
+ }
+
+ /**
+ * Sorts the matrix rows into ascending order, according to the <i>natural ordering</i> of the matrix values in the
+ * virtual column <tt>aggregates</tt>; Particularly efficient when comparing expensive aggregates, because aggregates
+ * need not be recomputed time and again, as is the case for comparator based sorts. Essentially, this algorithm makes
+ * expensive comparisons cheap. Normally each element of <tt>aggregates</tt> is a summary measure of a row. Speedup
+ * over comparator based sorting = <tt>2*log(rows)</tt>, on average. For this operation, quicksort is usually faster.
+ * <p> The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and
+ * vice-versa. To sort ranges use sub-ranging views. To sort columns by rows, use dice views. To sort descending, use
+ * flip views ... <p> <b>Example:</b> Each aggregate is the sum of a row <table border="1" cellspacing="0"> <tr
+ * nowrap> <td valign="top"><tt>4 x 2 matrix: <br> 1, 1<br> 5, 4<br> 3, 0<br> 4, 4 <br> </tt></td> <td align="left"
+ * valign="top"> <tt>aggregates=<br> 2<br> 9<br> 3<br> 8<br> ==></tt></td> <td valign="top"> <p><tt>4 x 2 matrix:<br>
+ * 1, 1<br> 3, 0<br> 4, 4<br> 5, 4</tt><br> The matrix IS NOT SORTED.<br> The new VIEW IS SORTED.</p> </td> </tr>
+ * </table>
+ *
+ * <table> <td class="PRE">
+ * <pre>
+ * // sort 10000 x 1000 matrix by sum of logarithms in a row (i.e. by geometric mean)
+ * DoubleMatrix2D matrix = new DenseDoubleMatrix2D(10000,1000);
+ * matrix.assign(new engine.MersenneTwister()); // initialized randomly
+ * org.apache.mahout.math.jet.math.Functions F = org.apache.mahout.math.jet.math.Functions.functions; // alias for convenience
+ *
+ * // THE QUICK VERSION (takes some 3 secs)
+ * // aggregates[i] = Sum(log(row));
+ * double[] aggregates = new double[matrix.rows()];
+ * for (int i = matrix.rows(); --i >= 0; ) aggregates[i] = matrix.viewRow(i).aggregate(F.plus, F.log);
+ * DoubleMatrix2D sorted = quickSort(matrix,aggregates);
+ *
+ * // THE SLOW VERSION (takes some 90 secs)
+ * DoubleMatrix1DComparator comparator = new DoubleMatrix1DComparator() {
+ * public int compare(DoubleMatrix1D x, DoubleMatrix1D y) {
+ * double a = x.aggregate(F.plus,F.log);
+ * double b = y.aggregate(F.plus,F.log);
+ * return a < b ? -1 : a==b ? 0 : 1;
+ * }
+ * };
+ * DoubleMatrix2D sorted = quickSort(matrix,comparator);
+ * </pre>
+ * </td> </table>
+ *
+ * @param matrix the matrix to be sorted.
+ * @param aggregates the values to sort on. (As a side effect, this array will also get sorted).
+ * @return a new matrix view having rows sorted. <b>Note that the original matrix is left unaffected.</b>
+ * @throws IndexOutOfBoundsException if <tt>aggregates.length != matrix.rows()</tt>.
+ */
+ public DoubleMatrix2D sort(DoubleMatrix2D matrix, final double[] aggregates) {
+ int rows = matrix.rows();
+ if (aggregates.length != rows) {
+ throw new IndexOutOfBoundsException("aggregates.length != matrix.rows()");
+ }
+
+ // set up index reordering
+ final int[] indexes = new int[rows];
+ for (int i = rows; --i >= 0;) {
+ indexes[i] = i;
+ }
+
+ // compares two aggregates at a time
+ IntComparator comp = new IntComparator() {
+ @Override
+ public int compare(int x, int y) {
+ double a = aggregates[x];
+ double b = aggregates[y];
+ if (a != a || b != b) {
+ return compareNaN(a, b);
+ } // swap NaNs to the end
+ return a < b ? -1 : (a == b) ? 0 : 1;
+ }
+ };
+ // swaps aggregates and reorders indexes
+ Swapper swapper = new Swapper() {
+ @Override
+ public void swap(int x, int y) {
+ int t1 = indexes[x];
+ indexes[x] = indexes[y];
+ indexes[y] = t1;
+ double t2 = aggregates[x];
+ aggregates[x] = aggregates[y];
+ aggregates[y] = t2;
+ }
+ };
+
+ // sort indexes and aggregates
+ runSort(0, rows, comp, swapper);
+
+ // view the matrix according to the reordered row indexes
+ // take all columns in the original order
+ return matrix.viewSelection(indexes, null);
+ }
+
+ /**
+ * Sorts the matrix rows into ascending order, according to the <i>natural ordering</i> of the matrix values in the
+ * given column. The returned view is backed by this matrix, so changes in the returned view are reflected in this
+ * matrix, and vice-versa. To sort ranges use sub-ranging views. To sort columns by rows, use dice views. To sort
+ * descending, use flip views ... <p> <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> log.info(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>
+ * @throws IndexOutOfBoundsException if <tt>column < 0 || column >= matrix.columns()</tt>.
+ */
+ public DoubleMatrix2D sort(DoubleMatrix2D matrix, int column) {
+ if (column < 0 || column >= matrix.columns()) {
+ throw new IndexOutOfBoundsException("column=" + column + ", matrix=" + AbstractFormatter.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;
+ }
+
+ final DoubleMatrix1D col = matrix.viewColumn(column);
+ IntComparator comp = new IntComparator() {
+ @Override
+ public int compare(int a, int b) {
+ double av = col.getQuick(a);
+ double bv = col.getQuick(b);
+ if (av != av || bv != bv) {
+ return compareNaN(av, bv);
+ } // swap NaNs to the end
+ return av < bv ? -1 : (av == bv ? 0 : 1);
+ }
+ };
+
+ 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. The returned view is backed by
+ * this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. The algorithm compares
+ * two rows (1-d matrices) at a time, determinining whether one is smaller, equal or larger than the other. To sort
+ * ranges use sub-ranging views. To sort columns by rows, use dice views. To sort descending, use flip views ... <p>
+ * <b>Example:</b>
+ * <pre>
+ * // sort by sum of values in a row
+ * DoubleMatrix1DComparator comp = new DoubleMatrix1DComparator() {
+ * public int compare(DoubleMatrix1D a, DoubleMatrix1D b) {
+ * double as = a.zSum(); double bs = b.zSum();
+ * return as < bs ? -1 : as == bs ? 0 : 1;
+ * }
+ * };
+ * sorted = quickSort(matrix,comp);
+ * </pre>
+ *
+ * @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>
+ */
+ public DoubleMatrix2D sort(DoubleMatrix2D matrix, final DoubleMatrix1DComparator 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;
+ }
+
+ final DoubleMatrix1D[] views = new DoubleMatrix1D[matrix.rows()]; // precompute views for speed
+ for (int i = views.length; --i >= 0;) {
+ views[i] = matrix.viewRow(i);
+ }
+
+ IntComparator comp = new IntComparator() {
+ @Override
+ 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 rows into ascending order, according to the <i>natural ordering</i> of the values computed by applying the given aggregation function to each row;
+ Particularly efficient when comparing expensive aggregates, because aggregates need not be recomputed time and again, as is the case for comparator based sorts.
+ Essentially, this algorithm makes expensive comparisons cheap.
+ Normally <tt>aggregates</tt> defines a summary measure of a row.
+ Speedup over comparator based sorting = <tt>2*log(rows)</tt>, on average.
+ <p>
+ The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa.
+ To sort ranges use sub-ranging views. To sort columns by rows, use dice views. To sort descending, use flip views ...
+ <p>
+ <b>Example:</b>
+ Each aggregate is the sum of a row
+ <table border="1" cellspacing="0">
+ <tr nowrap>
+ <td valign="top"><tt>4 x 2 matrix: <br>
+ 1, 1<br>
+ 5, 4<br>
+ 3, 0<br>
+ 4, 4 <br>
+ </tt></td>
+ <td align="left" valign="top">
+ <tt>aggregates=<br>
+ hep.aida.bin.BinFunctions1D.sum<br>
+ ==></tt></td>
+ <td valign="top">
+ <p><tt>4 x 2 matrix:<br>
+ 1, 1<br>
+ 3, 0<br>
+ 4, 4<br>
+ 5, 4</tt><br>
+ The matrix IS NOT SORTED.<br>
+ The new VIEW IS SORTED.</p>
+ </td>
+ </tr>
+ </table>
+
+ <table>
+ <td class="PRE">
+ <pre>
+ // sort 10000 x 1000 matrix by median or by sum of logarithms in a row (i.e. by geometric mean)
+ DoubleMatrix2D matrix = new DenseDoubleMatrix2D(10000,1000);
+ matrix.assign(new engine.MersenneTwister()); // initialized randomly
+ org.apache.mahout.math.jet.math.Functions F = org.apache.mahout.math.jet.math.Functions.functions; // alias for convenience
+
+ // THE QUICK VERSION (takes some 10 secs)
+ DoubleMatrix2D sorted = quickSort(matrix,hep.aida.bin.BinFunctions1D.median);
+ //DoubleMatrix2D sorted = quickSort(matrix,hep.aida.bin.BinFunctions1D.sumOfLogarithms);
+
+ // THE SLOW VERSION (takes some 300 secs)
+ DoubleMatrix1DComparator comparator = new DoubleMatrix1DComparator() {
+ public int compare(DoubleMatrix1D x, DoubleMatrix1D y) {
+ double a = org.apache.mahout.math.matrix.doublealgo.Statistic.bin(x).median();
+ double b = org.apache.mahout.math.matrix.doublealgo.Statistic.bin(y).median();
+ // double a = x.aggregate(F.plus,F.log);
+ // double b = y.aggregate(F.plus,F.log);
+ return a < b ? -1 : a==b ? 0 : 1;
+ }
+ };
+ DoubleMatrix2D sorted = quickSort(matrix,comparator);
+ </pre>
+ </td>
+ </table>
+
+ @param matrix the matrix to be sorted.
+ @param aggregate the function to sort on; aggregates values in a row.
+ @return a new matrix view having rows sorted.
+ <b>Note that the original matrix is left unaffected.</b>
+
+ public DoubleMatrix2D sort(DoubleMatrix2D matrix, hep.aida.bin.BinFunction1D aggregate) {
+ // precompute aggregates over rows, as defined by "aggregate"
+
+ // a bit clumsy, because Statistic.aggregate(...) is defined on columns, so we need to transpose views
+ DoubleMatrix2D tmp = matrix.like(1,matrix.rows());
+ hep.aida.bin.BinFunction1D[] func = {aggregate};
+ Statistic.aggregate(matrix.viewDice(), func, tmp);
+ double[] aggr = tmp.viewRow(0).toArray();
+ return sort(matrix,aggr);
+ }
+ */
+ /**
+ * 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. The returned view is backed by this matrix, so changes in the returned view
+ * are reflected in this matrix, and vice-versa. To sort ranges use sub-ranging views. To sort by other dimensions,
+ * use dice views. To sort descending, use flip views ... <p> The algorithm compares two 2-d slices at a time,
+ * determinining whether one is smaller, equal or larger than the other. Comparison is based on the cell
+ * <tt>[row,column]</tt> within a slice. Let <tt>A</tt> and <tt>B</tt> be two 2-d slices. Then we have the following
+ * rules <ul> <li><tt>A < B iff A.get(row,column) < B.get(row,column)</tt> <li><tt>A == B iff
+ * A.get(row,column) == B.get(row,column)</tt> <li><tt>A > B iff A.get(row,column) > B.get(row,column)</tt>
+ * </ul>
+ *
+ * @param matrix the matrix to be sorted.
+ * @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>
+ * @throws IndexOutOfBoundsException if <tt>row < 0 || row >= matrix.rows() || column < 0 || column >=
+ * matrix.columns()</tt>.
+ */
+ public DoubleMatrix3D sort(DoubleMatrix3D matrix, int row, int column) {
+ if (row < 0 || row >= matrix.rows()) {
+ throw new IndexOutOfBoundsException("row=" + row + ", matrix=" + AbstractFormatter.shape(matrix));
+ }
+ if (column < 0 || column >= matrix.columns()) {
+ throw new IndexOutOfBoundsException("column=" + column + ", matrix=" + AbstractFormatter.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;
+ }
+
+ final DoubleMatrix1D sliceView = matrix.viewRow(row).viewColumn(column);
+ IntComparator comp = new IntComparator() {
+ @Override
+ public int compare(int a, int b) {
+ double av = sliceView.getQuick(a);
+ double bv = sliceView.getQuick(b);
+ if (av != av || bv != bv) {
+ return compareNaN(av, bv);
+ } // swap NaNs to the end
+ return av < bv ? -1 : (av == bv ? 0 : 1);
+ }
+ };
+
+ 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. The returned view is backed by
+ * this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. The algorithm compares
+ * two slices (2-d matrices) at a time, determinining whether one is smaller, equal or larger than the other. To sort
+ * ranges use sub-ranging views. To sort by other dimensions, use dice views. To sort descending, use flip views ...
+ * <p> <b>Example:</b>
+ * <pre>
+ * // sort by sum of values in a slice
+ * DoubleMatrix2DComparator comp = new DoubleMatrix2DComparator() {
+ * public int compare(DoubleMatrix2D a, DoubleMatrix2D b) {
+ * double as = a.zSum(); double bs = b.zSum();
+ * return as < bs ? -1 : as == bs ? 0 : 1;
+ * }
+ * };
+ * sorted = quickSort(matrix,comp);
+ * </pre>
+ *
+ * @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>
+ */
+ public DoubleMatrix3D sort(DoubleMatrix3D matrix, final DoubleMatrix2DComparator c) {
+ int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder instead of matrix itself
+ for (int i = sliceIndexes.length; --i >= 0;) {
+ sliceIndexes[i] = i;
+ }
+
+ final DoubleMatrix2D[] views = new DoubleMatrix2D[matrix.slices()]; // precompute views for speed
+ for (int i = views.length; --i >= 0;) {
+ views[i] = matrix.viewSlice(i);
+ }
+
+ IntComparator comp = new IntComparator() {
+ @Override
+ 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);
+ }
+
+}
Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Sorting.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Statistic.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Statistic.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Statistic.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Statistic.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,622 @@
+/*
+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.math.matrix.doublealgo;
+
+import org.apache.mahout.math.function.DoubleDoubleFunction;
+import org.apache.mahout.math.jet.math.Functions;
+import org.apache.mahout.math.jet.random.engine.MersenneTwister;
+import org.apache.mahout.math.jet.random.engine.RandomEngine;
+import org.apache.mahout.math.jet.random.sampling.RandomSampler;
+import org.apache.mahout.math.matrix.DoubleMatrix1D;
+import org.apache.mahout.math.matrix.DoubleMatrix2D;
+import org.apache.mahout.math.matrix.DoubleMatrix3D;
+import org.apache.mahout.math.matrix.impl.DenseDoubleMatrix2D;
+
+/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
+@Deprecated
+public class Statistic {
+
+ /** Euclidean distance function; <tt>Sqrt(Sum( (x[i]-y[i])^2 ))</tt>. */
+ public static final VectorVectorFunction EUCLID = new VectorVectorFunction() {
+ @Override
+ public double apply(DoubleMatrix1D a, DoubleMatrix1D b) {
+ return Math.sqrt(a.aggregate(b, Functions.plus, Functions.chain(Functions.square, Functions.minus)));
+ }
+ };
+
+ /** Bray-Curtis distance function; <tt>Sum( abs(x[i]-y[i]) ) / Sum( x[i]+y[i] )</tt>. */
+ public static final VectorVectorFunction BRAY_CURTIS = new VectorVectorFunction() {
+ @Override
+ public double apply(DoubleMatrix1D a, DoubleMatrix1D b) {
+ return a.aggregate(b, Functions.plus, Functions.chain(Functions.abs, Functions.minus)) /
+ a.aggregate(b, Functions.plus, Functions.plus);
+ }
+ };
+
+ /** Canberra distance function; <tt>Sum( abs(x[i]-y[i]) / abs(x[i]+y[i]) )</tt>. */
+ public static final VectorVectorFunction CANBERRA = new VectorVectorFunction() {
+ private final DoubleDoubleFunction fun = new DoubleDoubleFunction() {
+ @Override
+ public double apply(double a, double b) {
+ return Math.abs(a - b) / Math.abs(a + b);
+ }
+ };
+
+ @Override
+ public double apply(DoubleMatrix1D a, DoubleMatrix1D b) {
+ return a.aggregate(b, Functions.plus, fun);
+ }
+ };
+
+ /** Maximum distance function; <tt>Max( abs(x[i]-y[i]) )</tt>. */
+ public static final VectorVectorFunction MAXIMUM = new VectorVectorFunction() {
+ @Override
+ public double apply(DoubleMatrix1D a, DoubleMatrix1D b) {
+ return a.aggregate(b, Functions.max, Functions.chain(Functions.abs, Functions.minus));
+ }
+ };
+
+ /** Manhattan distance function; <tt>Sum( abs(x[i]-y[i]) )</tt>. */
+ public static final VectorVectorFunction MANHATTAN = new VectorVectorFunction() {
+ @Override
+ public double apply(DoubleMatrix1D a, DoubleMatrix1D b) {
+ return a.aggregate(b, Functions.plus, Functions.chain(Functions.abs, Functions.minus));
+ }
+ };
+
+
+/**
+ * Interface that represents a function object: a function that takes
+ * two argument vectors and returns a single value.
+ */
+ /** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
+ @Deprecated
+ public interface VectorVectorFunction {
+
+ /**
+ * Applies a function to two argument vectors.
+ *
+ * @param x the first argument vector passed to the function.
+ * @param y the second argument vector passed to the function.
+ * @return the result of the function.
+ */
+ double apply(DoubleMatrix1D x, org.apache.mahout.math.matrix.DoubleMatrix1D y);
+ }
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ private Statistic() {
+ }
+/**
+ * Applies the given aggregation functions to each column and stores the results in a the result matrix.
+ * If matrix has shape <tt>m x n</tt>, then result must have shape <tt>aggr.length x n</tt>.
+ * Tip: To do aggregations on rows use dice views (transpositions), as in <tt>aggregate(matrix.viewDice(),aggr,result.viewDice())</tt>.
+ *
+ * @param matrix any matrix; a column holds the values of a given variable.
+ * @param aggr the aggregation functions to be applied to each column.
+ * @param result the matrix to hold the aggregation results.
+ * @return <tt>result</tt> (for convenience only).
+ * @see Formatter
+ * @see hep.aida.bin.BinFunction1D
+ * @see hep.aida.bin.BinFunctions1D
+ *
+public static DoubleMatrix2D aggregate(DoubleMatrix2D matrix, hep.aida.bin.BinFunction1D[] aggr, DoubleMatrix2D result) {
+DynamicBin1D bin = new DynamicBin1D();
+double[] elements = new double[matrix.rows()];
+org.apache.mahout.math.list.DoubleArrayList values = new DoubleArrayList(elements);
+for (int column=matrix.columns(); --column >= 0; ) {
+matrix.viewColumn(column).toArray(elements); // copy column into values
+bin.clear();
+bin.addAllOf(values);
+for (int i=aggr.length; --i >= 0; ) {
+result.set(i, column, aggr[i].apply(bin));
+}
+}
+return result;
+}
+ */
+/**
+ Fills all cell values of the given vector into a bin from which statistics measures can be retrieved efficiently.
+ Cells values are copied.
+ <br>
+ Tip: Use <tt>log.info(bin(vector))</tt> to print most measures computed by the bin. Example:
+ <table>
+ <td class="PRE">
+ <pre>
+ Size: 20000
+ Sum: 299858.02350278624
+ SumOfSquares: 5399184.154095971
+ Min: 0.8639113139711261
+ Max: 59.75331890541892
+ Mean: 14.992901175139313
+ RMS: 16.43043540825375
+ Variance: 45.17438077634358
+ Standard deviation: 6.721188940681818
+ Standard error: 0.04752598277592142
+ Geometric mean: 13.516615397064466
+ Product: Infinity
+ Harmonic mean: 11.995174297952191
+ Sum of inversions: 1667.337172700724
+ Skew: 0.8922838940067878
+ Kurtosis: 1.1915828121825598
+ Sum of powers(3): 1.1345828465808412E8
+ Sum of powers(4): 2.7251055344494686E9
+ Sum of powers(5): 7.367125643433887E10
+ Sum of powers(6): 2.215370909100143E12
+ Moment(0,0): 1.0
+ Moment(1,0): 14.992901175139313
+ Moment(2,0): 269.95920770479853
+ Moment(3,0): 5672.914232904206
+ Moment(4,0): 136255.27672247344
+ Moment(5,0): 3683562.8217169433
+ Moment(6,0): 1.1076854545500715E8
+ Moment(0,mean()): 1.0
+ Moment(1,mean()): -2.0806734113421045E-14
+ Moment(2,mean()): 45.172122057305664
+ Moment(3,mean()): 270.92018671421
+ Moment(4,mean()): 8553.8664869067
+ Moment(5,mean()): 153357.41712233616
+ Moment(6,mean()): 4273757.570142922
+ 25%, 50% and 75% Quantiles: 10.030074811938091, 13.977982089912224,
+ 18.86124362967137
+ quantileInverse(mean): 0.559163335012079
+ Distinct elements & frequencies not printed (too many).
+ </pre>
+ </td>
+ </table>
+
+ @param vector the vector to analyze.
+ @return a bin holding the statistics measures of the vector.
+ *
+ public static DynamicBin1D bin(DoubleMatrix1D vector) {
+ DynamicBin1D bin = new DynamicBin1D();
+ bin.addAllOf(DoubleFactory1D.dense.toList(vector));
+ return bin;
+ }
+ */
+ /**
+ * Modifies the given covariance matrix to be a correlation matrix (in-place). The correlation matrix is a square,
+ * symmetric matrix consisting of nothing but correlation coefficients. The rows and the columns represent the
+ * variables, the cells represent correlation coefficients. The diagonal cells (i.e. the correlation between a
+ * variable and itself) will equal 1, for the simple reason that the correlation coefficient of a variable with itself
+ * equals 1. The correlation of two column vectors x and y is given by <tt>corr(x,y) = cov(x,y) /
+ * (stdDev(x)*stdDev(y))</tt> (Pearson's correlation coefficient). A correlation coefficient varies between -1 (for a
+ * perfect negative relationship) to +1 (for a perfect positive relationship). See the <A
+ * HREF="http://www.cquest.utoronto.ca/geog/ggr270y/notes/not05efg.html"> math definition</A> and <A
+ * HREF="http://www.stat.berkeley.edu/users/stark/SticiGui/Text/gloss.htm#correlation_coef"> another def</A>. Compares
+ * two column vectors at a time. Use dice views to compare two row vectors at a time.
+ *
+ * @param covariance a covariance matrix, as, for example, returned by method {@link #covariance(DoubleMatrix2D)}.
+ * @return the modified covariance, now correlation matrix (for convenience only).
+ */
+ public static DoubleMatrix2D correlation(DoubleMatrix2D covariance) {
+ for (int i = covariance.columns(); --i >= 0;) {
+ for (int j = i; --j >= 0;) {
+ double stdDev1 = Math.sqrt(covariance.getQuick(i, i));
+ double stdDev2 = Math.sqrt(covariance.getQuick(j, j));
+ double cov = covariance.getQuick(i, j);
+ double corr = cov / (stdDev1 * stdDev2);
+
+ covariance.setQuick(i, j, corr);
+ covariance.setQuick(j, i, corr); // symmetric
+ }
+ }
+ for (int i = covariance.columns(); --i >= 0;) {
+ covariance.setQuick(i, i, 1);
+ }
+
+ return covariance;
+ }
+
+ /**
+ * Constructs and returns the covariance matrix of the given matrix. The covariance matrix is a square, symmetric
+ * matrix consisting of nothing but covariance coefficients. The rows and the columns represent the variables, the
+ * cells represent covariance coefficients. The diagonal cells (i.e. the covariance between a variable and itself)
+ * will equal the variances. The covariance of two column vectors x and y is given by <tt>cov(x,y) = (1/n) *
+ * Sum((x[i]-mean(x)) * (y[i]-mean(y)))</tt>. See the <A HREF="http://www.cquest.utoronto.ca/geog/ggr270y/notes/not05efg.html">
+ * math definition</A>. Compares two column vectors at a time. Use dice views to compare two row vectors at a time.
+ *
+ * @param matrix any matrix; a column holds the values of a given variable.
+ * @return the covariance matrix (<tt>n x n, n=matrix.columns</tt>).
+ */
+ public static DoubleMatrix2D covariance(DoubleMatrix2D matrix) {
+ int rows = matrix.rows();
+ int columns = matrix.columns();
+ DoubleMatrix2D covariance = new DenseDoubleMatrix2D(columns, columns);
+
+ double[] sums = new double[columns];
+ DoubleMatrix1D[] cols = new DoubleMatrix1D[columns];
+ for (int i = columns; --i >= 0;) {
+ cols[i] = matrix.viewColumn(i);
+ sums[i] = cols[i].zSum();
+ }
+
+ for (int i = columns; --i >= 0;) {
+ for (int j = i + 1; --j >= 0;) {
+ double sumOfProducts = cols[i].zDotProduct(cols[j]);
+ double cov = (sumOfProducts - sums[i] * sums[j] / rows) / rows;
+ covariance.setQuick(i, j, cov);
+ covariance.setQuick(j, i, cov); // symmetric
+ }
+ }
+ return covariance;
+ }
+/**
+ 2-d OLAP cube operator; Fills all cells of the given vectors into the given histogram.
+ If you use hep.aida.ref.Converter.toString(histo) on the result, the OLAP cube of x-"column" vs. y-"column" , summing the weights "column" will be printed.
+ For example, aggregate sales by product by region.
+ <p>
+ Computes the distinct values of x and y, yielding histogram axes that capture one distinct value per bin.
+ Then fills the histogram.
+ <p>
+ Example output:
+ <table>
+ <td class="PRE">
+ <pre>
+ Cube:
+ Entries=5000, ExtraEntries=0
+ MeanX=4.9838, RmsX=NaN
+ MeanY=2.5304, RmsY=NaN
+ xAxis: Min=0, Max=10, Bins=11
+ yAxis: Min=0, Max=5, Bins=6
+ Heights:
+ | X
+ | 0 1 2 3 4 5 6 7 8 9 10 | Sum
+ ----------------------------------------------------------
+ Y 5 | 30 53 51 52 57 39 65 61 55 49 22 | 534
+ 4 | 43 106 112 96 92 94 107 98 98 110 47 | 1003
+ 3 | 39 134 87 93 102 103 110 90 114 98 51 | 1021
+ 2 | 44 81 113 96 101 86 109 83 111 93 42 | 959
+ 1 | 54 94 103 99 115 92 98 97 103 90 44 | 989
+ 0 | 24 54 52 44 42 56 46 47 56 53 20 | 494
+ ----------------------------------------------------------
+ Sum | 234 522 518 480 509 470 535 476 537 493 226 |
+ </pre>
+ </td>
+ </table>
+ @return the histogram containing the cube.
+ @throws IllegalArgumentException if <tt>x.size() != y.size() || y.size() != weights.size()</tt>.
+ *
+ public static hep.aida.IHistogram2D cube(DoubleMatrix1D x, DoubleMatrix1D y, DoubleMatrix1D weights) {
+ if (x.size() != y.size() || y.size() != weights.size()) throw new IllegalArgumentException("vectors must have same size");
+
+ double epsilon = 1.0E-9;
+ org.apache.mahout.math.list.DoubleArrayList distinct = new DoubleArrayList();
+ double[] vals = new double[x.size()];
+ org.apache.mahout.math.list.DoubleArrayList sorted = new DoubleArrayList(vals);
+
+ // compute distinct values of x
+ x.toArray(vals); // copy x into vals
+ sorted.sort();
+ org.apache.mahout.math.jet.stat.Descriptive.frequencies(sorted, distinct, null);
+ // since bins are right-open [from,to) we need an additional dummy bin so that the last distinct value does not fall into the overflow bin
+ if (distinct.size()>0) distinct.add(distinct.get(distinct.size()-1) + epsilon);
+ distinct.trimToSize();
+ hep.aida.IAxis xaxis = new hep.aida.ref.VariableAxis(distinct.elements());
+
+ // compute distinct values of y
+ y.toArray(vals);
+ sorted.sort();
+ org.apache.mahout.math.jet.stat.Descriptive.frequencies(sorted, distinct, null);
+ // since bins are right-open [from,to) we need an additional dummy bin so that the last distinct value does not fall into the overflow bin
+ if (distinct.size()>0) distinct.add(distinct.get(distinct.size()-1) + epsilon);
+ distinct.trimToSize();
+ hep.aida.IAxis yaxis = new hep.aida.ref.VariableAxis(distinct.elements());
+
+ hep.aida.IHistogram2D histo = new hep.aida.ref.Histogram2D("Cube",xaxis,yaxis);
+ return histogram(histo,x,y,weights);
+ }
+ */
+/**
+ 3-d OLAP cube operator; Fills all cells of the given vectors into the given histogram.
+ If you use hep.aida.ref.Converter.toString(histo) on the result, the OLAP cube of x-"column" vs. y-"column" vs. z-"column", summing the weights "column" will be printed.
+ For example, aggregate sales by product by region by time.
+ <p>
+ Computes the distinct values of x and y and z, yielding histogram axes that capture one distinct value per bin.
+ Then fills the histogram.
+ @return the histogram containing the cube.
+ @throws IllegalArgumentException if <tt>x.size() != y.size() || x.size() != z.size() || x.size() != weights.size()</tt>.
+ *
+ public static hep.aida.IHistogram3D cube(DoubleMatrix1D x, DoubleMatrix1D y, DoubleMatrix1D z, DoubleMatrix1D weights) {
+ if (x.size() != y.size() || x.size() != z.size() || x.size() != weights.size()) throw new IllegalArgumentException("vectors must have same size");
+
+ double epsilon = 1.0E-9;
+ org.apache.mahout.math.list.DoubleArrayList distinct = new DoubleArrayList();
+ double[] vals = new double[x.size()];
+ org.apache.mahout.math.list.DoubleArrayList sorted = new DoubleArrayList(vals);
+
+ // compute distinct values of x
+ x.toArray(vals); // copy x into vals
+ sorted.sort();
+ org.apache.mahout.math.jet.stat.Descriptive.frequencies(sorted, distinct, null);
+ // since bins are right-open [from,to) we need an additional dummy bin so that the last distinct value does not fall into the overflow bin
+ if (distinct.size()>0) distinct.add(distinct.get(distinct.size()-1) + epsilon);
+ distinct.trimToSize();
+ hep.aida.IAxis xaxis = new hep.aida.ref.VariableAxis(distinct.elements());
+
+ // compute distinct values of y
+ y.toArray(vals);
+ sorted.sort();
+ org.apache.mahout.math.jet.stat.Descriptive.frequencies(sorted, distinct, null);
+ // since bins are right-open [from,to) we need an additional dummy bin so that the last distinct value does not fall into the overflow bin
+ if (distinct.size()>0) distinct.add(distinct.get(distinct.size()-1) + epsilon);
+ distinct.trimToSize();
+ hep.aida.IAxis yaxis = new hep.aida.ref.VariableAxis(distinct.elements());
+
+ // compute distinct values of z
+ z.toArray(vals);
+ sorted.sort();
+ org.apache.mahout.math.jet.stat.Descriptive.frequencies(sorted, distinct, null);
+ // since bins are right-open [from,to) we need an additional dummy bin so that the last distinct value does not fall into the overflow bin
+ if (distinct.size()>0) distinct.add(distinct.get(distinct.size()-1) + epsilon);
+ distinct.trimToSize();
+ hep.aida.IAxis zaxis = new hep.aida.ref.VariableAxis(distinct.elements());
+
+ hep.aida.IHistogram3D histo = new hep.aida.ref.Histogram3D("Cube",xaxis,yaxis,zaxis);
+ return histogram(histo,x,y,z,weights);
+ }
+ */
+
+
+ /**
+ * Constructs and returns the distance matrix of the given matrix. The distance matrix is a square, symmetric matrix
+ * consisting of nothing but distance coefficients. The rows and the columns represent the variables, the cells
+ * represent distance coefficients. The diagonal cells (i.e. the distance between a variable and itself) will be zero.
+ * Compares two column vectors at a time. Use dice views to compare two row vectors at a time.
+ *
+ * @param matrix any matrix; a column holds the values of a given variable (vector).
+ * @param distanceFunction (EUCLID, CANBERRA, ..., or any user defined distance function operating on two vectors).
+ * @return the distance matrix (<tt>n x n, n=matrix.columns</tt>).
+ */
+ public static DoubleMatrix2D distance(DoubleMatrix2D matrix, VectorVectorFunction distanceFunction) {
+ int columns = matrix.columns();
+ DoubleMatrix2D distance = new DenseDoubleMatrix2D(columns, columns);
+
+ // cache views
+ DoubleMatrix1D[] cols = new DoubleMatrix1D[columns];
+ for (int i = columns; --i >= 0;) {
+ cols[i] = matrix.viewColumn(i);
+ }
+
+ // work out all permutations
+ for (int i = columns; --i >= 0;) {
+ for (int j = i; --j >= 0;) {
+ double d = distanceFunction.apply(cols[i], cols[j]);
+ distance.setQuick(i, j, d);
+ distance.setQuick(j, i, d); // symmetric
+ }
+ }
+ return distance;
+ }
+
+
+ /**
+ * Constructs and returns a sampling view with a size of <tt>round(matrix.size() * fraction)</tt>. Samples "without
+ * replacement" from the uniform distribution.
+ *
+ * @param matrix any matrix.
+ * @param fraction the percentage of rows to be included in the view.
+ * @param randomGenerator a uniform random number generator; set this parameter to <tt>null</tt> to use a default
+ * generator seeded with the current time.
+ * @return the sampling view.
+ * @throws IllegalArgumentException if <tt>! (0 <= rowFraction <= 1 && 0 <= columnFraction <= 1)</tt>.
+ * @see org.apache.mahout.math.jet.random.sampling.RandomSampler
+ */
+ public static DoubleMatrix1D viewSample(DoubleMatrix1D matrix, double fraction, RandomEngine randomGenerator) {
+ // check preconditions and allow for a little tolerance
+ double epsilon = 1e-09;
+ if (fraction < 0 - epsilon || fraction > 1 + epsilon) {
+ throw new IllegalArgumentException();
+ }
+ if (fraction < 0) {
+ fraction = 0;
+ }
+ if (fraction > 1) {
+ fraction = 1;
+ }
+
+ // random generator seeded with current time
+ if (randomGenerator == null) {
+ randomGenerator = new MersenneTwister((int) System.currentTimeMillis());
+ }
+
+ int ncols = (int) Math.round(matrix.size() * fraction);
+ int max = ncols;
+ long[] selected = new long[max]; // sampler works on long's, not int's
+
+ // sample
+ int n = ncols;
+ int N = matrix.size();
+ RandomSampler.sample(n, N, n, 0, selected, 0, randomGenerator);
+ int[] selectedCols = new int[n];
+ for (int i = 0; i < n; i++) {
+ selectedCols[i] = (int) selected[i];
+ }
+
+ return matrix.viewSelection(selectedCols);
+ }
+
+ /**
+ * Constructs and returns a sampling view with <tt>round(matrix.rows() * rowFraction)</tt> rows and
+ * <tt>round(matrix.columns() * columnFraction)</tt> columns. Samples "without replacement". Rows and columns are
+ * randomly chosen from the uniform distribution. Examples: <table border="1" cellspacing="0"> <tr valign="top"
+ * align="center"> <td> <div align="left"><tt>matrix</tt></div> </td> <td> <div align="left"><tt>rowFraction=0.2<br>
+ * columnFraction=0.2</tt></div> </td> <td> <div align="left"><tt>rowFraction=0.2<br> columnFraction=1.0 </tt></div>
+ * </td> <td> <div align="left"><tt>rowFraction=1.0<br> columnFraction=0.2 </tt></div> </td> </tr> <tr valign="top">
+ * <td><tt> 10 x 10 matrix<br> 1 2 3 4 5 6 7 8 9 10<br>
+ * 11 12 13 14 15 16 17 18 19 20<br>
+ * 21 22 23 24 25 26 27 28 29 30<br>
+ * 31 32 33 34 35 36 37 38 39 40<br>
+ * 41 42 43 44 45 46 47 48 49 50<br>
+ * 51 52 53 54 55 56 57 58 59 60<br>
+ * 61 62 63 64 65 66 67 68 69 70<br>
+ * 71 72 73 74 75 76 77 78 79 80<br>
+ * 81 82 83 84 85 86 87 88 89 90<br>
+ * 91 92 93 94 95 96 97 98 99 100 </tt> </td> <td><tt>
+ * 2 x 2 matrix<br> 43 50<br> 53 60 </tt></td> <td><tt> 2 x 10 matrix<br>
+ * 41 42 43 44 45 46 47 48 49 50<br>
+ * 91 92 93 94 95 96 97 98 99 100 </tt> </td> <td><tt>
+ * 10 x 2 matrix<br> 4 8<br> 14 18<br> 24 28<br> 34 38<br>
+ * 44 48<br> 54 58<br> 64 68<br> 74 78<br> 84 88<br> 94 98 </tt> </td> </tr> </table>
+ *
+ * @param matrix any matrix.
+ * @param rowFraction the percentage of rows to be included in the view.
+ * @param columnFraction the percentage of columns to be included in the view.
+ * @param randomGenerator a uniform random number generator; set this parameter to <tt>null</tt> to use a default
+ * generator seeded with the current time.
+ * @return the sampling view.
+ * @throws IllegalArgumentException if <tt>! (0 <= rowFraction <= 1 && 0 <= columnFraction <= 1)</tt>.
+ * @see org.apache.mahout.math.jet.random.sampling.RandomSampler
+ */
+ public static DoubleMatrix2D viewSample(DoubleMatrix2D matrix, double rowFraction, double columnFraction,
+ RandomEngine randomGenerator) {
+ // check preconditions and allow for a little tolerance
+ double epsilon = 1e-09;
+ if (rowFraction < 0 - epsilon || rowFraction > 1 + epsilon) {
+ throw new IllegalArgumentException();
+ }
+ if (rowFraction < 0) {
+ rowFraction = 0;
+ }
+ if (rowFraction > 1) {
+ rowFraction = 1;
+ }
+
+ if (columnFraction < 0 - epsilon || columnFraction > 1 + epsilon) {
+ throw new IllegalArgumentException();
+ }
+ if (columnFraction < 0) {
+ columnFraction = 0;
+ }
+ if (columnFraction > 1) {
+ columnFraction = 1;
+ }
+
+ // random generator seeded with current time
+ if (randomGenerator == null) {
+ randomGenerator = new MersenneTwister((int) System.currentTimeMillis());
+ }
+
+ int nrows = (int) Math.round(matrix.rows() * rowFraction);
+ int ncols = (int) Math.round(matrix.columns() * columnFraction);
+ int max = Math.max(nrows, ncols);
+ long[] selected = new long[max]; // sampler works on long's, not int's
+
+ // sample rows
+ int n = nrows;
+ int N = matrix.rows();
+ RandomSampler.sample(n, N, n, 0, selected, 0, randomGenerator);
+ int[] selectedRows = new int[n];
+ for (int i = 0; i < n; i++) {
+ selectedRows[i] = (int) selected[i];
+ }
+
+ // sample columns
+ n = ncols;
+ N = matrix.columns();
+ RandomSampler.sample(n, N, n, 0, selected, 0, randomGenerator);
+ int[] selectedCols = new int[n];
+ for (int i = 0; i < n; i++) {
+ selectedCols[i] = (int) selected[i];
+ }
+
+ return matrix.viewSelection(selectedRows, selectedCols);
+ }
+
+ /**
+ * Constructs and returns a sampling view with <tt>round(matrix.slices() * sliceFraction)</tt> slices and
+ * <tt>round(matrix.rows() * rowFraction)</tt> rows and <tt>round(matrix.columns() * columnFraction)</tt> columns.
+ * Samples "without replacement". Slices, rows and columns are randomly chosen from the uniform distribution.
+ *
+ * @param matrix any matrix.
+ * @param sliceFraction the percentage of slices to be included in the view.
+ * @param rowFraction the percentage of rows to be included in the view.
+ * @param columnFraction the percentage of columns to be included in the view.
+ * @param randomGenerator a uniform random number generator; set this parameter to <tt>null</tt> to use a default
+ * generator seeded with the current time.
+ * @return the sampling view.
+ * @throws IllegalArgumentException if <tt>! (0 <= sliceFraction <= 1 && 0 <= rowFraction <= 1 && 0 <= columnFraction
+ * <= 1)</tt>.
+ * @see org.apache.mahout.math.jet.random.sampling.RandomSampler
+ */
+ public static DoubleMatrix3D viewSample(DoubleMatrix3D matrix, double sliceFraction, double rowFraction,
+ double columnFraction, RandomEngine randomGenerator) {
+ // check preconditions and allow for a little tolerance
+ double epsilon = 1e-09;
+ if (sliceFraction < 0 - epsilon || sliceFraction > 1 + epsilon) {
+ throw new IllegalArgumentException();
+ }
+ if (sliceFraction < 0) {
+ sliceFraction = 0;
+ }
+ if (sliceFraction > 1) {
+ sliceFraction = 1;
+ }
+
+ if (rowFraction < 0 - epsilon || rowFraction > 1 + epsilon) {
+ throw new IllegalArgumentException();
+ }
+ if (rowFraction < 0) {
+ rowFraction = 0;
+ }
+ if (rowFraction > 1) {
+ rowFraction = 1;
+ }
+
+ if (columnFraction < 0 - epsilon || columnFraction > 1 + epsilon) {
+ throw new IllegalArgumentException();
+ }
+ if (columnFraction < 0) {
+ columnFraction = 0;
+ }
+ if (columnFraction > 1) {
+ columnFraction = 1;
+ }
+
+ // random generator seeded with current time
+ if (randomGenerator == null) {
+ randomGenerator = new MersenneTwister((int) System.currentTimeMillis());
+ }
+
+ int nslices = (int) Math.round(matrix.slices() * sliceFraction);
+ int nrows = (int) Math.round(matrix.rows() * rowFraction);
+ int ncols = (int) Math.round(matrix.columns() * columnFraction);
+ int max = Math.max(nslices, Math.max(nrows, ncols));
+ long[] selected = new long[max]; // sampler works on long's, not int's
+
+ // sample slices
+ int n = nslices;
+ int N = matrix.slices();
+ RandomSampler.sample(n, N, n, 0, selected, 0, randomGenerator);
+ int[] selectedSlices = new int[n];
+ for (int i = 0; i < n; i++) {
+ selectedSlices[i] = (int) selected[i];
+ }
+
+ // sample rows
+ n = nrows;
+ N = matrix.rows();
+ RandomSampler.sample(n, N, n, 0, selected, 0, randomGenerator);
+ int[] selectedRows = new int[n];
+ for (int i = 0; i < n; i++) {
+ selectedRows[i] = (int) selected[i];
+ }
+
+ // sample columns
+ n = ncols;
+ N = matrix.columns();
+ RandomSampler.sample(n, N, n, 0, selected, 0, randomGenerator);
+ int[] selectedCols = new int[n];
+ for (int i = 0; i < n; i++) {
+ selectedCols[i] = (int) selected[i];
+ }
+
+ return matrix.viewSelection(selectedSlices, selectedRows, selectedCols);
+ }
+
+}
Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Statistic.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Stencil.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Stencil.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Stencil.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Stencil.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,99 @@
+/*
+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.math.matrix.doublealgo;
+
+import org.apache.mahout.math.matrix.DoubleMatrix2D;
+import org.apache.mahout.math.matrix.DoubleMatrix2DProcedure;
+import org.apache.mahout.math.matrix.DoubleMatrix3D;
+import org.apache.mahout.math.matrix.DoubleMatrix3DProcedure;
+
+/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
+@Deprecated
+public class Stencil {
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ private Stencil() {
+ }
+
+ /**
+ * 27 point stencil operation. Applies a function to a moving <tt>3 x 3 x 3</tt> window.
+ *
+ * @param A the matrix to operate on.
+ * @param function the function to be applied to each window.
+ * @param maxIterations the maximum number of times the stencil shall be applied to the matrix. Should be a
+ * multiple of 2 because two iterations are always done in one atomic step.
+ * @param hasConverged Convergence condition; will return before maxIterations are done when
+ * <tt>hasConverged.apply(A)==true</tt>. Set this parameter to <tt>null</tt> to indicate
+ * that no convergence checks shall be made.
+ * @param convergenceIterations the number of iterations to pass between each convergence check. (Since a convergence
+ * may be expensive, you may want to do it only every 2,4 or 8 iterations.)
+ * @return the number of iterations actually executed.
+ */
+ public static int stencil27(DoubleMatrix3D A, org.apache.mahout.math.function.Double27Function function,
+ int maxIterations, DoubleMatrix3DProcedure hasConverged, int convergenceIterations) {
+ DoubleMatrix3D B = A.copy();
+ if (convergenceIterations <= 1) {
+ convergenceIterations = 2;
+ }
+ if (convergenceIterations % 2 != 0) {
+ convergenceIterations++;
+ } // odd -> make it even
+
+ int i = 0;
+ while (i < maxIterations) { // do two steps at a time for efficiency
+ A.zAssign27Neighbors(B, function);
+ B.zAssign27Neighbors(A, function);
+ i += 2;
+ if (i % convergenceIterations == 0 && hasConverged != null) {
+ if (hasConverged.apply(A)) {
+ return i;
+ }
+ }
+ }
+ return i;
+ }
+
+ /**
+ * 9 point stencil operation. Applies a function to a moving <tt>3 x 3</tt> window.
+ *
+ * @param A the matrix to operate on.
+ * @param function the function to be applied to each window.
+ * @param maxIterations the maximum number of times the stencil shall be applied to the matrix. Should be a
+ * multiple of 2 because two iterations are always done in one atomic step.
+ * @param hasConverged Convergence condition; will return before maxIterations are done when
+ * <tt>hasConverged.apply(A)==true</tt>. Set this parameter to <tt>null</tt> to indicate
+ * that no convergence checks shall be made.
+ * @param convergenceIterations the number of iterations to pass between each convergence check. (Since a convergence
+ * may be expensive, you may want to do it only every 2,4 or 8 iterations.)
+ * @return the number of iterations actually executed.
+ */
+ public static int stencil9(DoubleMatrix2D A, org.apache.mahout.math.function.Double9Function function,
+ int maxIterations, DoubleMatrix2DProcedure hasConverged, int convergenceIterations) {
+ DoubleMatrix2D B = A.copy();
+ if (convergenceIterations <= 1) {
+ convergenceIterations = 2;
+ }
+ if (convergenceIterations % 2 != 0) {
+ convergenceIterations++;
+ } // odd -> make it even
+
+ int i = 0;
+ while (i < maxIterations) { // do two steps at a time for efficiency
+ A.zAssign8Neighbors(B, function);
+ B.zAssign8Neighbors(A, function);
+ i += 2;
+ if (i % convergenceIterations == 0 && hasConverged != null) {
+ if (hasConverged.apply(A)) {
+ return i;
+ }
+ }
+ }
+ return i;
+ }
+}
Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Stencil.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Transform.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Transform.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Transform.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Transform.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,395 @@
+/*
+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.math.matrix.doublealgo;
+
+import org.apache.mahout.math.PersistentObject;
+import org.apache.mahout.math.jet.math.Functions;
+import org.apache.mahout.math.matrix.DoubleMatrix1D;
+import org.apache.mahout.math.matrix.DoubleMatrix2D;
+
+/** @deprecated until unit tests are in place. Until this time, this class/interface is unsupported. */
+@Deprecated
+public class Transform extends PersistentObject {
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ protected Transform() {
+ }
+
+ /**
+ * <tt>A[i] = Math.abs(A[i])</tt>.
+ *
+ * @param A the matrix to modify.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D abs(DoubleMatrix1D A) {
+ return A.assign(Functions.abs);
+ }
+
+ /**
+ * <tt>A[row,col] = Math.abs(A[row,col])</tt>.
+ *
+ * @param A the matrix to modify.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D abs(DoubleMatrix2D A) {
+ return A.assign(Functions.abs);
+ }
+
+ /**
+ * <tt>A = A / s <=> A[i] = A[i] / s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D div(DoubleMatrix1D A, double s) {
+ return A.assign(Functions.div(s));
+ }
+
+ /**
+ * <tt>A = A / B <=> A[i] = A[i] / B[i]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D div(DoubleMatrix1D A, DoubleMatrix1D B) {
+ return A.assign(B, Functions.div);
+ }
+
+ /**
+ * <tt>A = A / s <=> A[row,col] = A[row,col] / s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D div(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.div(s));
+ }
+
+ /**
+ * <tt>A = A / B <=> A[row,col] = A[row,col] / B[row,col]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D div(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.div);
+ }
+
+ /**
+ * <tt>A[row,col] = A[row,col] == s ? 1 : 0</tt>; ignores tolerance.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D equals(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.equals(s));
+ }
+
+ /**
+ * <tt>A[row,col] = A[row,col] == B[row,col] ? 1 : 0</tt>; ignores tolerance.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D equals(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.equals);
+ }
+
+ /**
+ * <tt>A[row,col] = A[row,col] > s ? 1 : 0</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D greater(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.greater(s));
+ }
+
+ /**
+ * <tt>A[row,col] = A[row,col] > B[row,col] ? 1 : 0</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D greater(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.greater);
+ }
+
+ /**
+ * <tt>A[row,col] = A[row,col] < s ? 1 : 0</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D less(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.less(s));
+ }
+
+ /**
+ * <tt>A[row,col] = A[row,col] < B[row,col] ? 1 : 0</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D less(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.less);
+ }
+
+ /**
+ * <tt>A = A - s <=> A[i] = A[i] - s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D minus(DoubleMatrix1D A, double s) {
+ return A.assign(Functions.minus(s));
+ }
+
+ /**
+ * <tt>A = A - B <=> A[i] = A[i] - B[i]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D minus(DoubleMatrix1D A, DoubleMatrix1D B) {
+ return A.assign(B, Functions.minus);
+ }
+
+ /**
+ * <tt>A = A - s <=> A[row,col] = A[row,col] - s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D minus(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.minus(s));
+ }
+
+ /**
+ * <tt>A = A - B <=> A[row,col] = A[row,col] - B[row,col]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D minus(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.minus);
+ }
+
+ /**
+ * <tt>A = A - B*s <=> A[i] = A[i] - B[i]*s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D minusMult(DoubleMatrix1D A, DoubleMatrix1D B, double s) {
+ return A.assign(B, Functions.minusMult(s));
+ }
+
+ /**
+ * <tt>A = A - B*s <=> A[row,col] = A[row,col] - B[row,col]*s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D minusMult(DoubleMatrix2D A, DoubleMatrix2D B, double s) {
+ return A.assign(B, Functions.minusMult(s));
+ }
+
+ /**
+ * <tt>A = A * s <=> A[i] = A[i] * s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D mult(DoubleMatrix1D A, double s) {
+ return A.assign(Functions.mult(s));
+ }
+
+ /**
+ * <tt>A = A * B <=> A[i] = A[i] * B[i]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D mult(DoubleMatrix1D A, DoubleMatrix1D B) {
+ return A.assign(B, Functions.mult);
+ }
+
+ /**
+ * <tt>A = A * s <=> A[row,col] = A[row,col] * s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D mult(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.mult(s));
+ }
+
+ /**
+ * <tt>A = A * B <=> A[row,col] = A[row,col] * B[row,col]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D mult(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.mult);
+ }
+
+ /**
+ * <tt>A = -A <=> A[i] = -A[i]</tt> for all cells.
+ *
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D negate(DoubleMatrix1D A) {
+ return A.assign(Functions.mult(-1));
+ }
+
+ /**
+ * <tt>A = -A <=> A[row,col] = -A[row,col]</tt>.
+ *
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D negate(DoubleMatrix2D A) {
+ return A.assign(Functions.mult(-1));
+ }
+
+ /**
+ * <tt>A = A + s <=> A[i] = A[i] + s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D plus(DoubleMatrix1D A, double s) {
+ return A.assign(Functions.plus(s));
+ }
+
+ /**
+ * <tt>A = A + B <=> A[i] = A[i] + B[i]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D plus(DoubleMatrix1D A, DoubleMatrix1D B) {
+ return A.assign(B, Functions.plus);
+ }
+
+ /**
+ * <tt>A = A + s <=> A[row,col] = A[row,col] + s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D plus(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.plus(s));
+ }
+
+ /**
+ * <tt>A = A + B <=> A[row,col] = A[row,col] + B[row,col]</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D plus(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.plus);
+ }
+
+ /**
+ * <tt>A = A + B*s<=> A[i] = A[i] + B[i]*s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D plusMult(DoubleMatrix1D A, DoubleMatrix1D B, double s) {
+ return A.assign(B, Functions.plusMult(s));
+ }
+
+ /**
+ * <tt>A = A + B*s <=> A[row,col] = A[row,col] + B[row,col]*s</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D plusMult(DoubleMatrix2D A, DoubleMatrix2D B, double s) {
+ return A.assign(B, Functions.plusMult(s));
+ }
+
+ /**
+ * <tt>A = A<sup>s</sup> <=> A[i] = Math.pow(A[i], s)</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D pow(DoubleMatrix1D A, double s) {
+ return A.assign(Functions.pow(s));
+ }
+
+ /**
+ * <tt>A = A<sup>B</sup> <=> A[i] = Math.pow(A[i], B[i])</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix1D pow(DoubleMatrix1D A, DoubleMatrix1D B) {
+ return A.assign(B, Functions.pow);
+ }
+
+ /**
+ * <tt>A = A<sup>s</sup> <=> A[row,col] = Math.pow(A[row,col], s)</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param s the scalar; can have any value.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D pow(DoubleMatrix2D A, double s) {
+ return A.assign(Functions.pow(s));
+ }
+
+ /**
+ * <tt>A = A<sup>B</sup> <=> A[row,col] = Math.pow(A[row,col], B[row,col])</tt>.
+ *
+ * @param A the matrix to modify.
+ * @param B the matrix to stay unaffected.
+ * @return <tt>A</tt> (for convenience only).
+ */
+ public static DoubleMatrix2D pow(DoubleMatrix2D A, DoubleMatrix2D B) {
+ return A.assign(B, Functions.pow);
+ }
+}
Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/Transform.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/package.html
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/package.html?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/package.html (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/package.html Thu Dec 17 23:22:16 2009
@@ -0,0 +1,5 @@
+<HTML>
+<BODY>
+Double matrix <i>algorithms</i> such as print formatting, sorting, partitioning and statistics.
+</BODY>
+</HTML>
\ No newline at end of file
Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/doublealgo/package.html
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractFormatter.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractFormatter.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractFormatter.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractFormatter.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,387 @@
+/*
+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.math.matrix.impl;
+
+import org.apache.mahout.math.PersistentObject;
+
+/**
+ Abstract base class for flexible, well human readable matrix print formatting.
+ Value type independent.
+ A single cell is formatted via a format string.
+ Columns can be aligned left, centered, right and by decimal point.
+ <p>A column can be broader than specified by the parameter <tt>minColumnWidth</tt>
+ (because a cell may not fit into that width) but a column is never smaller than
+ <tt>minColumnWidth</tt>. Normally one does not need to specify <tt>minColumnWidth</tt>.
+ Cells in a row are separated by a separator string, similar separators can be set for rows and slices.
+ For more info, see the concrete subclasses.
+
+ @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. */
+@Deprecated
+public abstract class AbstractFormatter extends PersistentObject {
+
+ /** The alignment string aligning the cells of a column to the left. */
+ public static final String LEFT = "left";
+
+ /** The alignment string aligning the cells of a column to its center. */
+ public static final String CENTER = "center";
+
+ /** The alignment string aligning the cells of a column to the right. */
+ public static final String RIGHT = "right";
+
+ /** The alignment string aligning the cells of a column to the decimal point. */
+ public static final String DECIMAL = "decimal";
+
+ /** The default minimum number of characters a column may have; currently <tt>1</tt>. */
+ private static final int DEFAULT_MIN_COLUMN_WIDTH = 1;
+
+ /** The default string separating any two columns from another; currently <tt>" "</tt>. */
+ private static final String DEFAULT_COLUMN_SEPARATOR = " ";
+
+ /** The default string separating any two rows from another; currently <tt>"\n"</tt>. */
+ private static final String DEFAULT_ROW_SEPARATOR = "\n";
+
+ /** The default string separating any two slices from another; currently <tt>"\n\n"</tt>. */
+ private static final String DEFAULT_SLICE_SEPARATOR = "\n\n";
+
+
+ /** The default format string for formatting a single cell value; currently <tt>"%G"</tt>. */
+ protected String alignment = LEFT;
+
+ /** The default format string for formatting a single cell value; currently <tt>"%G"</tt>. */
+ protected String format = "%G";
+
+ /** The default minimum number of characters a column may have; currently <tt>1</tt>. */
+ private int minColumnWidth = DEFAULT_MIN_COLUMN_WIDTH;
+
+ /** The default string separating any two columns from another; currently <tt>" "</tt>. */
+ private String columnSeparator = DEFAULT_COLUMN_SEPARATOR;
+
+ /** The default string separating any two rows from another; currently <tt>"\n"</tt>. */
+ protected String rowSeparator = DEFAULT_ROW_SEPARATOR;
+
+ /** The default string separating any two slices from another; currently <tt>"\n\n"</tt>. */
+ protected String sliceSeparator = DEFAULT_SLICE_SEPARATOR;
+
+ /** Tells whether String representations are to be preceded with summary of the shape; currently <tt>true</tt>. */
+ protected boolean printShape = true;
+
+
+ private static String[] blanksCache; // for efficient String manipulations
+
+ private static final FormerFactory factory = new FormerFactory();
+
+ static {
+ setupBlanksCache();
+ }
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ protected AbstractFormatter() {
+ }
+
+ /** Modifies the strings in a column of the string matrix to be aligned (left,centered,right,decimal). */
+ protected void align(String[][] strings) {
+ int rows = strings.length;
+ int columns = 0;
+ if (rows > 0) {
+ columns = strings[0].length;
+ }
+
+ int[] maxColWidth = new int[columns];
+ int[] maxColLead = null;
+ boolean isDecimal = alignment.equals(DECIMAL);
+ if (isDecimal) {
+ maxColLead = new int[columns];
+ }
+ //int[] maxColTrail = new int[columns];
+
+ // for each column, determine alignment parameters
+ for (int column = 0; column < columns; column++) {
+ int maxWidth = minColumnWidth;
+ int maxLead = Integer.MIN_VALUE;
+ //int maxTrail = Integer.MIN_VALUE;
+ for (int row = 0; row < rows; row++) {
+ String s = strings[row][column];
+ maxWidth = Math.max(maxWidth, s.length());
+ if (isDecimal) {
+ maxLead = Math.max(maxLead, lead(s));
+ }
+ //maxTrail = Math.max(maxTrail, trail(s));
+ }
+ maxColWidth[column] = maxWidth;
+ if (isDecimal) {
+ maxColLead[column] = maxLead;
+ }
+ //maxColTrail[column] = maxTrail;
+ }
+
+ // format each row according to alignment parameters
+ //StringBuffer total = new StringBuffer();
+ for (int row = 0; row < rows; row++) {
+ alignRow(strings[row], maxColWidth, maxColLead);
+ }
+
+ }
+
+ /** Converts a row into a string. */
+ protected int alignmentCode(String alignment) {
+ //{-1,0,1,2} = {left,centered,right,decimal point}
+ if (alignment.equals(LEFT)) {
+ return -1;
+ } else if (alignment.equals(CENTER)) {
+ return 0;
+ } else if (alignment.equals(RIGHT)) {
+ return 1;
+ } else if (alignment.equals(DECIMAL)) {
+ return 2;
+ } else {
+ throw new IllegalArgumentException("unknown alignment: " + alignment);
+ }
+ }
+
+ /** Modifies the strings the string matrix to be aligned (left,centered,right,decimal). */
+ protected void alignRow(String[] row, int[] maxColWidth, int[] maxColLead) {
+ //int align = alignmentCode(alignment); //{-1,0,1,2} = {left,centered,right,decimal point}
+ StringBuilder s = new StringBuilder();
+
+ int columns = row.length;
+ for (int column = 0; column < columns; column++) {
+ s.setLength(0);
+ String c = row[column];
+ //if (alignment==1) {
+ if (alignment.equals(RIGHT)) {
+ s.append(blanks(maxColWidth[column] - s.length()));
+ s.append(c);
+ }
+ //else if (alignment==2) {
+ else if (alignment.equals(DECIMAL)) {
+ s.append(blanks(maxColLead[column] - lead(c)));
+ s.append(c);
+ s.append(blanks(maxColWidth[column] - s.length()));
+ }
+ //else if (align==0) {
+ else if (alignment.equals(CENTER)) {
+ s.append(blanks((maxColWidth[column] - c.length()) / 2));
+ s.append(c);
+ s.append(blanks(maxColWidth[column] - s.length()));
+
+ }
+ //else if (align<0) {
+ else if (alignment.equals(LEFT)) {
+ s.append(c);
+ s.append(blanks(maxColWidth[column] - s.length()));
+ } else {
+ throw new InternalError();
+ }
+
+ row[column] = s.toString();
+ }
+ }
+
+ /** Returns a String with <tt>length</tt> blanks. */
+ protected String blanks(int length) {
+ if (length < 0) {
+ length = 0;
+ }
+ if (length < blanksCache.length) {
+ return blanksCache[length];
+ }
+
+ StringBuilder buf = new StringBuilder(length);
+ for (int k = 0; k < length; k++) {
+ buf.append(' ');
+ }
+ return buf.toString();
+ }
+
+ /** Converts a given cell to a String; no alignment considered. */
+ protected abstract String form(AbstractMatrix1D matrix, int index, Former formatter);
+
+ /** Returns a string representations of all cells; no alignment considered. */
+ protected abstract String[][] format(AbstractMatrix2D matrix);
+
+ /** Returns a string representations of all cells; no alignment considered. */
+ protected String[] formatRow(AbstractMatrix1D vector) {
+ Former formatter = factory.create(format);
+ int s = vector.size();
+ String[] strings = new String[s];
+ for (int i = 0; i < s; i++) {
+ strings[i] = form(vector, i, formatter);
+ }
+ return strings;
+ }
+
+ /** Returns the number of characters or the number of characters before the decimal point. */
+ protected int lead(String s) {
+ return s.length();
+ }
+
+ /** Returns a String with the given character repeated <tt>length</tt> times. */
+ protected String repeat(char character, int length) {
+ if (character == ' ') {
+ return blanks(length);
+ }
+ if (length < 0) {
+ length = 0;
+ }
+ StringBuilder buf = new StringBuilder(length);
+ for (int k = 0; k < length; k++) {
+ buf.append(character);
+ }
+ return buf.toString();
+ }
+
+ /**
+ * Sets the column alignment (left,center,right,decimal).
+ *
+ * @param alignment the new alignment to be used; must be one of <tt>{LEFT,CENTER,RIGHT,DECIMAL}</tt>.
+ */
+ public void setAlignment(String alignment) {
+ this.alignment = alignment;
+ }
+
+ /**
+ * Sets the string separating any two columns from another.
+ *
+ * @param columnSeparator the new columnSeparator to be used.
+ */
+ public void setColumnSeparator(String columnSeparator) {
+ this.columnSeparator = columnSeparator;
+ }
+
+ /**
+ * Sets the way a <i>single</i> cell value is to be formatted.
+ *
+ * @param format the new format to be used.
+ */
+ public void setFormat(String format) {
+ this.format = format;
+ }
+
+ /**
+ * Sets the minimum number of characters a column may have.
+ *
+ * @param minColumnWidth the new minColumnWidth to be used.
+ */
+ public void setMinColumnWidth(int minColumnWidth) {
+ if (minColumnWidth < 0) {
+ throw new IllegalArgumentException();
+ }
+ this.minColumnWidth = minColumnWidth;
+ }
+
+ /**
+ * Specifies whether a string representation of a matrix is to be preceded with a summary of its shape.
+ *
+ * @param printShape <tt>true</tt> shape summary is printed, otherwise not printed.
+ */
+ public void setPrintShape(boolean printShape) {
+ this.printShape = printShape;
+ }
+
+ /**
+ * Sets the string separating any two rows from another.
+ *
+ * @param rowSeparator the new rowSeparator to be used.
+ */
+ public void setRowSeparator(String rowSeparator) {
+ this.rowSeparator = rowSeparator;
+ }
+
+ /**
+ * Sets the string separating any two slices from another.
+ *
+ * @param sliceSeparator the new sliceSeparator to be used.
+ */
+ public void setSliceSeparator(String sliceSeparator) {
+ this.sliceSeparator = sliceSeparator;
+ }
+
+ /** Cache for faster string processing. */
+ private static void setupBlanksCache() {
+ // Pre-fabricate 40 static strings with 0,1,2,..,39 blanks, for usage within method blanks(length).
+ // Now, we don't need to construct and fill them on demand, and garbage collect them again.
+ // All 40 strings share the identical char[] array, only with different offset and length --> somewhat smaller static memory footprint
+ int size = 40;
+ blanksCache = new String[size];
+ StringBuilder buf = new StringBuilder(size);
+ for (int i = size; --i >= 0;) {
+ buf.append(' ');
+ }
+ String str = buf.toString();
+ for (int i = size; --i >= 0;) {
+ blanksCache[i] = str.substring(0, i);
+ //log.info(i+"-"+blanksCache[i]+"-");
+ }
+ }
+
+ /** Returns a short string representation describing the shape of the matrix. */
+ public static String shape(AbstractMatrix1D matrix) {
+ //return "Matrix1D of size="+matrix.size();
+ //return matrix.size()+" element matrix";
+ //return "matrix("+matrix.size()+")";
+ return matrix.size() + " matrix";
+ }
+
+ /** Returns a short string representation describing the shape of the matrix. */
+ public static String shape(AbstractMatrix2D matrix) {
+ return matrix.rows() + " x " + matrix.columns() + " matrix";
+ }
+
+ /** Returns a short string representation describing the shape of the matrix. */
+ public static String shape(AbstractMatrix3D matrix) {
+ return matrix.slices() + " x " + matrix.rows() + " x " + matrix.columns() + " matrix";
+ }
+
+ /**
+ * Returns a single string representation of the given string matrix.
+ *
+ * @param strings the matrix to be converted to a single string.
+ */
+ protected String toString(String[][] strings) {
+ int rows = strings.length;
+ int columns = strings.length <= 0 ? 0 : strings[0].length;
+
+ StringBuilder total = new StringBuilder();
+ StringBuilder s = new StringBuilder();
+ for (int row = 0; row < rows; row++) {
+ s.setLength(0);
+ for (int column = 0; column < columns; column++) {
+ s.append(strings[row][column]);
+ if (column < columns - 1) {
+ s.append(columnSeparator);
+ }
+ }
+ total.append(s);
+ if (row < rows - 1) {
+ total.append(rowSeparator);
+ }
+ }
+
+ return total.toString();
+ }
+
+ /**
+ * Returns a string representation of the given matrix.
+ *
+ * @param matrix the matrix to convert.
+ */
+ protected String toString(AbstractMatrix2D matrix) {
+ String[][] strings = this.format(matrix);
+ align(strings);
+ StringBuilder total = new StringBuilder(toString(strings));
+ if (printShape) {
+ total.insert(0, shape(matrix) + '\n');
+ }
+ return total.toString();
+ }
+}
Propchange: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractFormatter.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractMatrix.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractMatrix.java?rev=891983&view=auto
==============================================================================
--- lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractMatrix.java (added)
+++ lucene/mahout/trunk/math/src/main/java/org/apache/mahout/math/matrix/impl/AbstractMatrix.java Thu Dec 17 23:22:16 2009
@@ -0,0 +1,59 @@
+/*
+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.math.matrix.impl;
+
+import org.apache.mahout.math.PersistentObject;
+
+/**
+ Abstract base class for arbitrary-dimensional matrices holding objects or primitive data types such as <code>int</code>, <code>float</code>, etc.
+ First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.
+ <p>
+ <b>Note that this implementation is not synchronized.</b>
+
+ @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. */
+@Deprecated
+public abstract class AbstractMatrix extends PersistentObject {
+
+ protected boolean isNoView = true;
+
+ //public static boolean debug = true;
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ protected AbstractMatrix() {
+ }
+
+ /**
+ * Ensures that the receiver can hold at least the specified number of non-zero (non-null) cells without needing to
+ * allocate new internal memory. If necessary, allocates new internal memory and increases the capacity of the
+ * receiver. <p> This default implementation does nothing. Override this method if necessary.
+ *
+ * @param minNonZeros the desired minimum number of non-zero (non-null) cells.
+ */
+ public void ensureCapacity(int minNonZeros) {
+ }
+
+ /** Returns whether the receiver is a view or not. */
+ protected boolean isView() {
+ return !this.isNoView;
+ }
+
+ /** Returns the number of cells. */
+ public abstract int size();
+
+ /**
+ * Releases any superfluous internal memory. An application can use this operation to minimize the storage of the
+ * receiver. <p> This default implementation does nothing. Override this method if necessary.
+ */
+ public void trimToSize() {
+ }
+}