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:36:02 UTC
svn commit: r883973 [1/14] - in
/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix: ./
bitvector/ buffer/ function/ list/ list/adapter/ map/
Author: srowen
Date: Wed Nov 25 03:35:59 2009
New Revision: 883973
URL: http://svn.apache.org/viewvc?rev=883973&view=rev
Log:
MAHOUT-204 -- Drew's author-cleanup patch (in pieces)
Modified:
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Arrays.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Partitioning.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/PersistentObject.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Sorting.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Swapper.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Timer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitMatrix.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitVector.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/QuickBitVector.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2D.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2DConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer3D.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer3DConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBufferConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/IntBuffer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/IntBuffer2D.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/IntBuffer2DConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/IntBuffer3D.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/IntBuffer3DConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/IntBufferConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/ObjectBuffer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/ObjectBufferConsumer.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/ByteComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/CharComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/Double27Function.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/Double9Function.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/DoubleComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/FloatComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/IntComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/LongComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/function/ShortComparator.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractBooleanList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractByteList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractCharList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractCollection.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractDoubleList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractFloatList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractIntList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractLongList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/AbstractShortList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/BooleanArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/ByteArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/CharArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/DistinctNumberList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/DoubleArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/FloatArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/IntArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/LongArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/MinMaxNumberList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/ObjectArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/ShortArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/SimpleLongArrayList.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/adapter/DoubleListAdapter.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/adapter/FloatListAdapter.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/adapter/IntListAdapter.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/adapter/LongListAdapter.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/adapter/ObjectListAdapter.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/list/package.html
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/AbstractDoubleIntMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/AbstractIntDoubleMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/AbstractIntIntMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/AbstractIntObjectMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/AbstractLongObjectMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/AbstractMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/Benchmark.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/HashFunctions.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/OpenDoubleIntHashMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/OpenIntDoubleHashMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/OpenIntIntHashMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/OpenIntObjectHashMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/OpenLongObjectHashMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/PrimeFinder.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/QuickOpenIntIntHashMap.java
lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/map/package.html
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Arrays.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Arrays.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Arrays.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Arrays.java Wed Nov 25 03:35:59 2009
@@ -14,8 +14,6 @@
* @see java.util.Arrays
* @see org.apache.mahout.matrix.Sorting
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 03-Jul-99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
@@ -37,21 +35,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static byte[] ensureCapacity(byte[] array, int minCapacity) {
- int oldCapacity = array.length;
- byte[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new byte[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ byte[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new byte[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -64,21 +62,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static char[] ensureCapacity(char[] array, int minCapacity) {
- int oldCapacity = array.length;
- char[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new char[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ char[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new char[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -91,22 +89,22 @@
* @param minCapacity the desired minimum capacity.
*/
public static double[] ensureCapacity(double[] array, int minCapacity) {
- int oldCapacity = array.length;
- double[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new double[newCapacity];
- //for (int i = oldCapacity; --i >= 0; ) newArray[i] = array[i];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ double[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new double[newCapacity];
+ //for (int i = oldCapacity; --i >= 0; ) newArray[i] = array[i];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -119,21 +117,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static float[] ensureCapacity(float[] array, int minCapacity) {
- int oldCapacity = array.length;
- float[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new float[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ float[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new float[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -146,21 +144,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static int[] ensureCapacity(int[] array, int minCapacity) {
- int oldCapacity = array.length;
- int[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new int[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ int[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new int[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -173,21 +171,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static long[] ensureCapacity(long[] array, int minCapacity) {
- int oldCapacity = array.length;
- long[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new long[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ long[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new long[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -200,21 +198,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static Object[] ensureCapacity(Object[] array, int minCapacity) {
- int oldCapacity = array.length;
- Object[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new Object[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ Object[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new Object[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -227,21 +225,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static short[] ensureCapacity(short[] array, int minCapacity) {
- int oldCapacity = array.length;
- short[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new short[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ short[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new short[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Ensures that a given array can hold up to <tt>minCapacity</tt> elements.
@@ -254,21 +252,21 @@
* @param minCapacity the desired minimum capacity.
*/
public static boolean[] ensureCapacity(boolean[] array, int minCapacity) {
- int oldCapacity = array.length;
- boolean[] newArray;
- if (minCapacity > oldCapacity) {
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity) {
- newCapacity = minCapacity;
- }
-
- newArray = new boolean[newCapacity];
- System.arraycopy(array, 0, newArray, 0, oldCapacity);
- }
- else {
- newArray=array;
- }
- return newArray;
+ int oldCapacity = array.length;
+ boolean[] newArray;
+ if (minCapacity > oldCapacity) {
+ int newCapacity = (oldCapacity * 3)/2 + 1;
+ if (newCapacity < minCapacity) {
+ newCapacity = minCapacity;
+ }
+
+ newArray = new boolean[newCapacity];
+ System.arraycopy(array, 0, newArray, 0, oldCapacity);
+ }
+ else {
+ newArray=array;
+ }
+ return newArray;
}
/**
* Returns a string representation of the specified array. The string
@@ -278,16 +276,16 @@
* @return a string representation of the specified array.
*/
public static String toString(byte[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -297,16 +295,16 @@
* @return a string representation of the specified array.
*/
public static String toString(char[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -316,16 +314,16 @@
* @return a string representation of the specified array.
*/
public static String toString(double[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -335,16 +333,16 @@
* @return a string representation of the specified array.
*/
public static String toString(float[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -354,16 +352,16 @@
* @return a string representation of the specified array.
*/
public static String toString(int[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -373,16 +371,16 @@
* @return a string representation of the specified array.
*/
public static String toString(long[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -392,16 +390,16 @@
* @return a string representation of the specified array.
*/
public static String toString(Object[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -411,16 +409,16 @@
* @return a string representation of the specified array.
*/
public static String toString(short[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Returns a string representation of the specified array. The string
@@ -430,16 +428,16 @@
* @return a string representation of the specified array.
*/
public static String toString(boolean[] array) {
- StringBuffer buf = new StringBuffer();
- buf.append("[");
- int maxIndex = array.length - 1;
- for (int i = 0; i <= maxIndex; i++) {
- buf.append(array[i]);
- if (i < maxIndex)
- buf.append(", ");
- }
- buf.append("]");
- return buf.toString();
+ StringBuffer buf = new StringBuffer();
+ buf.append("[");
+ int maxIndex = array.length - 1;
+ for (int i = 0; i <= maxIndex; i++) {
+ buf.append(array[i]);
+ if (i < maxIndex)
+ buf.append(", ");
+ }
+ buf.append("]");
+ return buf.toString();
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -452,12 +450,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static byte[] trimToCapacity(byte[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- byte oldArray[] = array;
- array = new byte[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ byte oldArray[] = array;
+ array = new byte[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -470,12 +468,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static char[] trimToCapacity(char[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- char oldArray[] = array;
- array = new char[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ char oldArray[] = array;
+ array = new char[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -488,12 +486,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static double[] trimToCapacity(double[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- double oldArray[] = array;
- array = new double[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ double oldArray[] = array;
+ array = new double[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -506,12 +504,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static float[] trimToCapacity(float[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- float oldArray[] = array;
- array = new float[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ float oldArray[] = array;
+ array = new float[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -524,12 +522,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static int[] trimToCapacity(int[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- int oldArray[] = array;
- array = new int[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ int oldArray[] = array;
+ array = new int[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -542,12 +540,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static long[] trimToCapacity(long[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- long oldArray[] = array;
- array = new long[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ long oldArray[] = array;
+ array = new long[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -560,12 +558,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static Object[] trimToCapacity(Object[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- Object oldArray[] = array;
- array = new Object[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ Object oldArray[] = array;
+ array = new Object[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -578,12 +576,12 @@
* @param maxCapacity the desired maximum capacity.
*/
public static short[] trimToCapacity(short[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- short oldArray[] = array;
- array = new short[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ short oldArray[] = array;
+ array = new short[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
/**
* Ensures that the specified array cannot hold more than <tt>maxCapacity</tt> elements.
@@ -596,11 +594,11 @@
* @param maxCapacity the desired maximum capacity.
*/
public static boolean[] trimToCapacity(boolean[] array, int maxCapacity) {
- if (array.length > maxCapacity) {
- boolean oldArray[] = array;
- array = new boolean[maxCapacity];
- System.arraycopy(oldArray, 0, array, 0, maxCapacity);
- }
- return array;
+ if (array.length > maxCapacity) {
+ boolean oldArray[] = array;
+ array = new boolean[maxCapacity];
+ System.arraycopy(oldArray, 0, array, 0, maxCapacity);
+ }
+ return array;
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericPermuting.java Wed Nov 25 03:35:59 2009
@@ -138,55 +138,55 @@
@throws IllegalArgumentException if <tt>p < 1 || N < 0 || p > N!</tt>.
*/
public static int[] permutation(long p, int N) {
- if (p<1) throw new IllegalArgumentException("Permutations are enumerated 1 .. N!");
- if (N<0) throw new IllegalArgumentException("Must satisfy N >= 0");
-
- int[] permutation = new int[N];
-
- if (N > 20) { // factorial(21) would overflow 64-bit long)
- // Simply make a list (0,1,..N-1) and randomize it, seeded with "p".
- // Note that this is perhaps not what you want...
- for (int i=N; --i >= 0; ) permutation[i]=i;
- org.apache.mahout.jet.random.Uniform gen = new org.apache.mahout.jet.random.Uniform(new org.apache.mahout.jet.random.engine.MersenneTwister((int)p));
- for (int i=0; i<N-1; i++) {
- int random = gen.nextIntFromTo(i, N-1);
-
- //swap(i, random)
- int tmp = permutation[random];
- permutation[random]=permutation[i];
- permutation[i]=tmp;
- }
-
- return permutation;
- }
-
- // the normal case - exact enumeration
- if (p > org.apache.mahout.jet.math.Arithmetic.longFactorial(N)) throw new IllegalArgumentException("N too large (a sequence of N elements only has N! permutations).");
-
- int[] tmp = new int[N];
- for (int i=1; i<=N; i++) tmp[i-1]= i;
-
- long io = p-1;
- for (int M = N-1; M>=1; M--) {
- long fac = org.apache.mahout.jet.math.Arithmetic.longFactorial(M);
- int in = ((int) (io / fac)) + 1;
- io = io % fac;
- permutation[N-M-1] = tmp[in-1];
-
- for (int j = in; j <= M; j++) tmp[j-1] = tmp[j];
- }
- if (N>0) permutation[N-1] = tmp[0];
+ if (p<1) throw new IllegalArgumentException("Permutations are enumerated 1 .. N!");
+ if (N<0) throw new IllegalArgumentException("Must satisfy N >= 0");
+
+ int[] permutation = new int[N];
+
+ if (N > 20) { // factorial(21) would overflow 64-bit long)
+ // Simply make a list (0,1,..N-1) and randomize it, seeded with "p".
+ // Note that this is perhaps not what you want...
+ for (int i=N; --i >= 0; ) permutation[i]=i;
+ org.apache.mahout.jet.random.Uniform gen = new org.apache.mahout.jet.random.Uniform(new org.apache.mahout.jet.random.engine.MersenneTwister((int)p));
+ for (int i=0; i<N-1; i++) {
+ int random = gen.nextIntFromTo(i, N-1);
+
+ //swap(i, random)
+ int tmp = permutation[random];
+ permutation[random]=permutation[i];
+ permutation[i]=tmp;
+ }
+
+ return permutation;
+ }
+
+ // the normal case - exact enumeration
+ if (p > org.apache.mahout.jet.math.Arithmetic.longFactorial(N)) throw new IllegalArgumentException("N too large (a sequence of N elements only has N! permutations).");
+
+ int[] tmp = new int[N];
+ for (int i=1; i<=N; i++) tmp[i-1]= i;
+
+ long io = p-1;
+ for (int M = N-1; M>=1; M--) {
+ long fac = org.apache.mahout.jet.math.Arithmetic.longFactorial(M);
+ int in = ((int) (io / fac)) + 1;
+ io = io % fac;
+ permutation[N-M-1] = tmp[in-1];
+
+ for (int j = in; j <= M; j++) tmp[j-1] = tmp[j];
+ }
+ if (N>0) permutation[N-1] = tmp[0];
- for (int i=N; --i >= 0; ) permutation[i] = permutation[i]-1;
- return permutation;
+ for (int i=N; --i >= 0; ) permutation[i] = permutation[i]-1;
+ return permutation;
}
/**
A non-generic variant of reordering, specialized for <tt>int[]</tt>, same semantics.
Quicker than generic reordering. Also for convenience (forget about the Swapper object).
*/
public static void permute(int[] list, int[] indexes) {
- int[] copy = (int[]) list.clone();
- for (int i=list.length; --i >=0; ) list[i] = copy[indexes[i]];
+ int[] copy = (int[]) list.clone();
+ for (int i=list.length; --i >=0; ) list[i] = copy[indexes[i]];
}
/**
Deprecated. Generically reorders arbitrary shaped generic data <tt>g</tt> such that <tt>g[i] == g[indexes[i]]</tt>.
@@ -212,7 +212,7 @@
@param work the working storage, must satisfy <tt>work.length >= indexes.length</tt>; set <tt>work==null</tt> if you don't care about performance.
*/
public static void permute(int[] indexes, org.apache.mahout.matrix.Swapper swapper, int[] work) {
- permute(indexes,swapper,work,null);
+ permute(indexes,swapper,work,null);
}
/**
Generically reorders arbitrary shaped generic data <tt>g</tt> such that <tt>g[i] == g[indexes[i]]</tt>.
@@ -238,39 +238,39 @@
@param work2 some working storage, must satisfy <tt>work2.length >= indexes.length</tt>; set <tt>work2==null</tt> if you don't care about performance.
*/
public static void permute(int[] indexes, org.apache.mahout.matrix.Swapper swapper, int[] work1, int[] work2) {
- // "tracks" and "pos" keeps track of the current indexes of the elements
- // Example: We have a list==[A,B,C,D,E], indexes==[0,4,1,2,3] and swap B and E we need to know that the element formlerly at index 1 is now at index 4, and the one formerly at index 4 is now at index 1.
- // Otherwise we stumble over our own feet and produce nonsense.
- // Initially index i really is at index i, but this will change due to swapping.
-
- // work1, work2 to avoid high frequency memalloc's
- int s = indexes.length;
- int[] tracks = work1;
- int[] pos = work2;
- if (tracks==null || tracks.length<s) tracks = new int[s];
- if (pos==null || pos.length<s) pos = new int[s];
- for (int i=s; --i >= 0; ) {
- tracks[i] = i;
- pos[i] = i;
- }
-
- for (int i=0; i<s; i++) {
- int index = indexes[i];
- int track = tracks[index];
-
- if (i!=track) {
- swapper.swap(i,track);
- tracks[index]=i; tracks[pos[i]]=track;
- int tmp = pos[i]; pos[i]=pos[track]; pos[track]=tmp;
- }
- }
+ // "tracks" and "pos" keeps track of the current indexes of the elements
+ // Example: We have a list==[A,B,C,D,E], indexes==[0,4,1,2,3] and swap B and E we need to know that the element formlerly at index 1 is now at index 4, and the one formerly at index 4 is now at index 1.
+ // Otherwise we stumble over our own feet and produce nonsense.
+ // Initially index i really is at index i, but this will change due to swapping.
+
+ // work1, work2 to avoid high frequency memalloc's
+ int s = indexes.length;
+ int[] tracks = work1;
+ int[] pos = work2;
+ if (tracks==null || tracks.length<s) tracks = new int[s];
+ if (pos==null || pos.length<s) pos = new int[s];
+ for (int i=s; --i >= 0; ) {
+ tracks[i] = i;
+ pos[i] = i;
+ }
+
+ for (int i=0; i<s; i++) {
+ int index = indexes[i];
+ int track = tracks[index];
+
+ if (i!=track) {
+ swapper.swap(i,track);
+ tracks[index]=i; tracks[pos[i]]=track;
+ int tmp = pos[i]; pos[i]=pos[track]; pos[track]=tmp;
+ }
+ }
}
/**
A non-generic variant of reordering, specialized for <tt>Object[]</tt>, same semantics.
Quicker than generic reordering. Also for convenience (forget about the Swapper object).
*/
public static void permute(Object[] list, int[] indexes) {
- Object[] copy = (Object[]) list.clone();
- for (int i=list.length; --i >=0; ) list[i] = copy[indexes[i]];
+ Object[] copy = (Object[]) list.clone();
+ for (int i=list.length; --i >=0; ) list[i] = copy[indexes[i]];
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSorting.java Wed Nov 25 03:35:59 2009
@@ -15,7 +15,7 @@
<ul>
<li><i>Sorting multiple arrays in sync</i>
<li><i>Sorting by multiple sorting criteria</i> (primary, secondary, tertiary,
- ...)
+ ...)
</ul>
<h4>Sorting multiple arrays in sync</h4>
<p>
@@ -27,15 +27,15 @@
<p>How can we achive this? Here are several alternatives. We could ... </p>
<ol>
<li> make a list of Point3D objects, sort the list as desired using a comparison
- function, then copy the results back into X, Y and Z. The classic object-oriented
- way. </li>
+ function, then copy the results back into X, Y and Z. The classic object-oriented
+ way. </li>
<li>make an index list [0,1,2,...,N-1], sort the index list using a comparison function,
- then reorder the elements of X,Y,Z as defined by the index list. Reordering
- cannot be done in-place, so we need to copy X to some temporary array, then
- copy in the right order back from the temporary into X. Same for Y and Z.
+ then reorder the elements of X,Y,Z as defined by the index list. Reordering
+ cannot be done in-place, so we need to copy X to some temporary array, then
+ copy in the right order back from the temporary into X. Same for Y and Z.
</li>
<li> use a generic quicksort or mergesort which, whenever two elements in X are swapped,
- also swaps the corresponding elements in Y and Z. </li>
+ also swaps the corresponding elements in Y and Z. </li>
</ol>
Alternatives 1 and 2 involve quite a lot of copying and allocate significant amounts
of temporary memory. Alternative 3 involves more swapping, more polymorphic message dispatches, no copying and does not need any temporary memory.
@@ -66,10 +66,10 @@
// this one knows how to swap two indexes (a,b)
Swapper swapper = new Swapper() {
public void swap(int a, int b) {
- int t1; double t2, t3;
- t1 = x[a]; x[a] = x[b]; x[b] = t1;
+ int t1; double t2, t3;
+ t1 = x[a]; x[a] = x[b]; x[b] = t1;
t2 = y[a]; y[a] = y[b]; y[b] = t2;
- t3 = z[a]; z[a] = z[b]; z[b] = t3;
+ t3 = z[a]; z[a] = z[b]; z[b] = t3;
}
};
// simple comparison: compare by X and ignore Y,Z<br>
@@ -149,8 +149,8 @@
*/
@Deprecated
public class GenericSorting extends Object {
- private static final int SMALL = 7;
- private static final int MEDIUM = 40;
+ private static final int SMALL = 7;
+ private static final int MEDIUM = 40;
/**
* Makes this class non instantiable, but still let's others inherit from it.
*/
@@ -164,43 +164,43 @@
* second.
*/
private static void inplace_merge(int first, int middle, int last, IntComparator comp, Swapper swapper) {
- if (first >= middle || middle >= last)
- return;
- if (last - first == 2) {
- if (comp.compare(middle, first)<0) {
- swapper.swap(first,middle);
- }
- return;
- }
- int firstCut;
- int secondCut;
- if (middle - first > last - middle) {
- firstCut = first + (middle - first) / 2;
- secondCut = lower_bound(middle, last, firstCut, comp);
- }
- else {
- secondCut = middle + (last - middle) / 2;
- firstCut = upper_bound(first, middle, secondCut, comp);
- }
-
- // rotate(firstCut, middle, secondCut, swapper);
- // is manually inlined for speed (jitter inlining seems to work only for small call depths, even if methods are "static private")
- // speedup = 1.7
- // begin inline
- int first2 = firstCut; int middle2 = middle; int last2 = secondCut;
- if (middle2 != first2 && middle2 != last2) {
- int first1 = first2; int last1 = middle2;
- while (first1 < --last1) swapper.swap(first1++,last1);
- first1 = middle2; last1 = last2;
- while (first1 < --last1) swapper.swap(first1++,last1);
- first1 = first2; last1 = last2;
- while (first1 < --last1) swapper.swap(first1++,last1);
- }
- // end inline
-
- middle = firstCut + (secondCut - middle);
- inplace_merge(first, firstCut, middle, comp, swapper);
- inplace_merge(middle, secondCut, last, comp, swapper);
+ if (first >= middle || middle >= last)
+ return;
+ if (last - first == 2) {
+ if (comp.compare(middle, first)<0) {
+ swapper.swap(first,middle);
+ }
+ return;
+ }
+ int firstCut;
+ int secondCut;
+ if (middle - first > last - middle) {
+ firstCut = first + (middle - first) / 2;
+ secondCut = lower_bound(middle, last, firstCut, comp);
+ }
+ else {
+ secondCut = middle + (last - middle) / 2;
+ firstCut = upper_bound(first, middle, secondCut, comp);
+ }
+
+ // rotate(firstCut, middle, secondCut, swapper);
+ // is manually inlined for speed (jitter inlining seems to work only for small call depths, even if methods are "static private")
+ // speedup = 1.7
+ // begin inline
+ int first2 = firstCut; int middle2 = middle; int last2 = secondCut;
+ if (middle2 != first2 && middle2 != last2) {
+ int first1 = first2; int last1 = middle2;
+ while (first1 < --last1) swapper.swap(first1++,last1);
+ first1 = middle2; last1 = last2;
+ while (first1 < --last1) swapper.swap(first1++,last1);
+ first1 = first2; last1 = last2;
+ while (first1 < --last1) swapper.swap(first1++,last1);
+ }
+ // end inline
+
+ middle = firstCut + (secondCut - middle);
+ inplace_merge(first, firstCut, middle, comp, swapper);
+ inplace_merge(middle, secondCut, last, comp, swapper);
}
/**
* Performs a binary search on an already-sorted range: finds the first
@@ -220,31 +220,31 @@
* @see Sorting#binary_search
*/
private static int lower_bound(int first, int last, int x, IntComparator comp) {
- //if (comp==null) throw new NullPointerException();
- int len = last - first;
- while (len > 0) {
- int half = len / 2;
- int middle = first + half;
- if (comp.compare(middle, x)<0) {
- first = middle + 1;
- len -= half + 1;
- }
- else {
- len = half;
- }
- }
- return first;
+ //if (comp==null) throw new NullPointerException();
+ int len = last - first;
+ while (len > 0) {
+ int half = len / 2;
+ int middle = first + half;
+ if (comp.compare(middle, x)<0) {
+ first = middle + 1;
+ len -= half + 1;
+ }
+ else {
+ len = half;
+ }
+ }
+ return first;
}
/**
* Returns the index of the median of the three indexed chars.
*/
private static int med3(int a, int b, int c, IntComparator comp) {
- int ab = comp.compare(a,b);
- int ac = comp.compare(a,c);
- int bc = comp.compare(b,c);
- return (ab<0 ?
- (bc<0 ? b : ac<0 ? c : a) :
- (bc>0 ? b : ac>0 ? c : a));
+ int ab = comp.compare(a,b);
+ int ac = comp.compare(a,c);
+ int bc = comp.compare(b,c);
+ return (ab<0 ?
+ (bc<0 ? b : ac<0 ? c : a) :
+ (bc>0 ? b : ac>0 ? c : a));
}
/**
* Sorts the specified range of elements according
@@ -272,35 +272,35 @@
* @see Swapper
*/
public static void mergeSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
- /*
- We retain the same method signature as quickSort.
- Given only a comparator and swapper we do not know how to copy and move elements from/to temporary arrays.
- Hence, in contrast to the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary arrays.
- A non-inplace mergesort would perhaps be faster in most cases, but would require non-intuitive delegate objects...
- */
- int length = toIndex - fromIndex;
-
- // Insertion sort on smallest arrays
- if (length < SMALL) {
- for (int i = fromIndex; i < toIndex; i++) {
- for (int j = i; j > fromIndex && (c.compare(j - 1, j) > 0); j--) {
- swapper.swap(j, j - 1);
- }
- }
- return;
- }
-
- // Recursively sort halves
- int mid = (fromIndex + toIndex) / 2;
- mergeSort(fromIndex, mid, c, swapper);
- mergeSort(mid, toIndex, c, swapper);
-
- // If list is already sorted, nothing left to do. This is an
- // optimization that results in faster sorts for nearly ordered lists.
- if (c.compare(mid - 1, mid) <= 0) return;
+ /*
+ We retain the same method signature as quickSort.
+ Given only a comparator and swapper we do not know how to copy and move elements from/to temporary arrays.
+ Hence, in contrast to the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary arrays.
+ A non-inplace mergesort would perhaps be faster in most cases, but would require non-intuitive delegate objects...
+ */
+ int length = toIndex - fromIndex;
+
+ // Insertion sort on smallest arrays
+ if (length < SMALL) {
+ for (int i = fromIndex; i < toIndex; i++) {
+ for (int j = i; j > fromIndex && (c.compare(j - 1, j) > 0); j--) {
+ swapper.swap(j, j - 1);
+ }
+ }
+ return;
+ }
+
+ // Recursively sort halves
+ int mid = (fromIndex + toIndex) / 2;
+ mergeSort(fromIndex, mid, c, swapper);
+ mergeSort(mid, toIndex, c, swapper);
+
+ // If list is already sorted, nothing left to do. This is an
+ // optimization that results in faster sorts for nearly ordered lists.
+ if (c.compare(mid - 1, mid) <= 0) return;
- // Merge sorted halves
- inplace_merge(fromIndex, mid, toIndex, c, swapper);
+ // Merge sorted halves
+ inplace_merge(fromIndex, mid, toIndex, c, swapper);
}
/**
* Sorts the specified range of elements according
@@ -326,72 +326,72 @@
* @see Swapper
*/
public static void quickSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
- quickSort1(fromIndex, toIndex-fromIndex, c, swapper);
+ quickSort1(fromIndex, toIndex-fromIndex, c, swapper);
}
/**
* Sorts the specified sub-array into ascending order.
*/
private static void quickSort1(int off, int len, IntComparator comp, Swapper swapper) {
- // Insertion sort on smallest arrays
- if (len < SMALL) {
- for (int i=off; i<len+off; i++)
- for (int j=i; j>off && (comp.compare(j-1,j)>0); j--) {
- swapper.swap(j, j-1);
- }
- return;
- }
-
- // Choose a partition element, v
- int m = off + len/2; // Small arrays, middle element
- if (len > SMALL) {
- int l = off;
- int n = off + len - 1;
- if (len > MEDIUM) { // Big arrays, pseudomedian of 9
- int s = len/8;
- l = med3(l, l+s, l+2*s, comp);
- m = med3(m-s, m, m+s, comp);
- n = med3(n-2*s, n-s, n, comp);
- }
- m = med3(l, m, n, comp); // Mid-size, med of 3
- }
- //long v = x[m];
-
- // Establish Invariant: v* (<v)* (>v)* v*
- int a = off, b = a, c = off + len - 1, d = c;
- while(true) {
- int comparison;
- while (b <= c && ((comparison=comp.compare(b,m))<=0)) {
- if (comparison == 0) {
- if (a==m) m = b; // moving target; DELTA to JDK !!!
- else if (b==m) m = a; // moving target; DELTA to JDK !!!
- swapper.swap(a++, b);
- }
- b++;
- }
- while (c >= b && ((comparison=comp.compare(c,m))>=0)) {
- if (comparison == 0) {
- if (c==m) m = d; // moving target; DELTA to JDK !!!
- else if (d==m) m = c; // moving target; DELTA to JDK !!!
- swapper.swap(c, d--);
- }
- c--;
- }
- if (b > c) break;
- if (b==m) m = d; // moving target; DELTA to JDK !!!
- else if (c==m) m = c; // moving target; DELTA to JDK !!!
- swapper.swap(b++, c--);
- }
-
- // Swap partition elements back to middle
- int s, n = off + len;
- s = Math.min(a-off, b-a ); vecswap(swapper, off, b-s, s);
- s = Math.min(d-c, n-d-1); vecswap(swapper, b, n-s, s);
-
- // Recursively sort non-partition-elements
- if ((s = b-a) > 1)
- quickSort1(off, s, comp, swapper);
- if ((s = d-c) > 1)
- quickSort1(n-s, s, comp, swapper);
+ // Insertion sort on smallest arrays
+ if (len < SMALL) {
+ for (int i=off; i<len+off; i++)
+ for (int j=i; j>off && (comp.compare(j-1,j)>0); j--) {
+ swapper.swap(j, j-1);
+ }
+ return;
+ }
+
+ // Choose a partition element, v
+ int m = off + len/2; // Small arrays, middle element
+ if (len > SMALL) {
+ int l = off;
+ int n = off + len - 1;
+ if (len > MEDIUM) { // Big arrays, pseudomedian of 9
+ int s = len/8;
+ l = med3(l, l+s, l+2*s, comp);
+ m = med3(m-s, m, m+s, comp);
+ n = med3(n-2*s, n-s, n, comp);
+ }
+ m = med3(l, m, n, comp); // Mid-size, med of 3
+ }
+ //long v = x[m];
+
+ // Establish Invariant: v* (<v)* (>v)* v*
+ int a = off, b = a, c = off + len - 1, d = c;
+ while(true) {
+ int comparison;
+ while (b <= c && ((comparison=comp.compare(b,m))<=0)) {
+ if (comparison == 0) {
+ if (a==m) m = b; // moving target; DELTA to JDK !!!
+ else if (b==m) m = a; // moving target; DELTA to JDK !!!
+ swapper.swap(a++, b);
+ }
+ b++;
+ }
+ while (c >= b && ((comparison=comp.compare(c,m))>=0)) {
+ if (comparison == 0) {
+ if (c==m) m = d; // moving target; DELTA to JDK !!!
+ else if (d==m) m = c; // moving target; DELTA to JDK !!!
+ swapper.swap(c, d--);
+ }
+ c--;
+ }
+ if (b > c) break;
+ if (b==m) m = d; // moving target; DELTA to JDK !!!
+ else if (c==m) m = c; // moving target; DELTA to JDK !!!
+ swapper.swap(b++, c--);
+ }
+
+ // Swap partition elements back to middle
+ int s, n = off + len;
+ s = Math.min(a-off, b-a ); vecswap(swapper, off, b-s, s);
+ s = Math.min(d-c, n-d-1); vecswap(swapper, b, n-s, s);
+
+ // Recursively sort non-partition-elements
+ if ((s = b-a) > 1)
+ quickSort1(off, s, comp, swapper);
+ if ((s = d-c) > 1)
+ quickSort1(n-s, s, comp, swapper);
}
/**
* Reverses a sequence of elements.
@@ -402,10 +402,10 @@
* is invalid.
*/
private static void reverse(int first, int last, Swapper swapper) {
- // no more needed since manually inlined
- while (first < --last) {
- swapper.swap(first++,last);
- }
+ // no more needed since manually inlined
+ while (first < --last) {
+ swapper.swap(first++,last);
+ }
}
/**
* Rotate a range in place: <code>array[middle]</code> is put in
@@ -420,12 +420,12 @@
* @param last One past the end of the range
*/
private static void rotate(int first, int middle, int last, Swapper swapper) {
- // no more needed since manually inlined
- if (middle != first && middle != last) {
- reverse(first, middle, swapper);
- reverse(middle, last, swapper);
- reverse(first, last, swapper);
- }
+ // no more needed since manually inlined
+ if (middle != first && middle != last) {
+ reverse(first, middle, swapper);
+ reverse(middle, last, swapper);
+ reverse(first, last, swapper);
+ }
}
/**
* Performs a binary search on an already-sorted range: finds the last
@@ -445,25 +445,25 @@
* @see Sorting#binary_search
*/
private static int upper_bound(int first, int last, int x, IntComparator comp) {
- //if (comp==null) throw new NullPointerException();
- int len = last - first;
- while (len > 0) {
- int half = len / 2;
- int middle = first + half;
- if (comp.compare(x, middle)<0) {
- len = half;
- }
- else {
- first = middle + 1;
- len -= half + 1;
- }
- }
- return first;
+ //if (comp==null) throw new NullPointerException();
+ int len = last - first;
+ while (len > 0) {
+ int half = len / 2;
+ int middle = first + half;
+ if (comp.compare(x, middle)<0) {
+ len = half;
+ }
+ else {
+ first = middle + 1;
+ len -= half + 1;
+ }
+ }
+ return first;
}
/**
* Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
*/
private static void vecswap(Swapper swapper, int a, int b, int n) {
- for (int i=0; i<n; i++, a++, b++) swapper.swap(a, b);
+ for (int i=0; i<n; i++, a++, b++) swapper.swap(a, b);
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/GenericSortingTest.java Wed Nov 25 03:35:59 2009
@@ -24,134 +24,134 @@
* Just a demo.
*/
public static void demo1() {
- final int[] x;
- final double[] y;
- final double[] z;
-
- x = new int[] {3, 2, 1 };
- y = new double[] {3.0, 2.0, 1.0};
- z = new double[] {6.0, 7.0, 8.0};
-
- Swapper swapper = new Swapper() {
- public void swap(int a, int b) {
- int t1; double t2, t3;
- t1 = x[a]; x[a] = x[b]; x[b] = t1;
- t2 = y[a]; y[a] = y[b]; y[b] = t2;
- t3 = z[a]; z[a] = z[b]; z[b] = t3;
- }
- };
-
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- return x[a]==x[b] ? 0 : (x[a]<x[b] ? -1 : 1);
- }
- };
-
- System.out.println("before:");
- System.out.println("X="+Arrays.toString(x));
- System.out.println("Y="+Arrays.toString(y));
- System.out.println("Z="+Arrays.toString(z));
-
-
- int from = 0;
- int to = x.length;
- GenericSorting.quickSort(from, to, comp, swapper);
-
- System.out.println("after:");
- System.out.println("X="+Arrays.toString(x));
- System.out.println("Y="+Arrays.toString(y));
- System.out.println("Z="+Arrays.toString(z));
- System.out.println("\n\n");
+ final int[] x;
+ final double[] y;
+ final double[] z;
+
+ x = new int[] {3, 2, 1 };
+ y = new double[] {3.0, 2.0, 1.0};
+ z = new double[] {6.0, 7.0, 8.0};
+
+ Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ int t1; double t2, t3;
+ t1 = x[a]; x[a] = x[b]; x[b] = t1;
+ t2 = y[a]; y[a] = y[b]; y[b] = t2;
+ t3 = z[a]; z[a] = z[b]; z[b] = t3;
+ }
+ };
+
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ return x[a]==x[b] ? 0 : (x[a]<x[b] ? -1 : 1);
+ }
+ };
+
+ System.out.println("before:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+
+
+ int from = 0;
+ int to = x.length;
+ GenericSorting.quickSort(from, to, comp, swapper);
+
+ System.out.println("after:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+ System.out.println("\n\n");
}
/**
* Just a demo.
*/
public static void demo2() {
- final int[] x;
- final double[] y;
- final double[] z;
-
- x = new int[] {6, 7, 8, 9 };
- y = new double[] {3.0, 2.0, 1.0, 3.0};
- z = new double[] {5.0, 4.0, 4.0, 1.0};
-
- Swapper swapper = new Swapper() {
- public void swap(int a, int b) {
- int t1; double t2, t3;
- t1 = x[a]; x[a] = x[b]; x[b] = t1;
- t2 = y[a]; y[a] = y[b]; y[b] = t2;
- t3 = z[a]; z[a] = z[b]; z[b] = t3;
- }
- };
-
- IntComparator comp = new IntComparator() {
- public int compare(int a, int b) {
- if (y[a]==y[b]) return z[a]==z[b] ? 0 : (z[a]<z[b] ? -1 : 1);
- return y[a]<y[b] ? -1 : 1;
- }
- };
-
-
- System.out.println("before:");
- System.out.println("X="+Arrays.toString(x));
- System.out.println("Y="+Arrays.toString(y));
- System.out.println("Z="+Arrays.toString(z));
-
-
- int from = 0;
- int to = x.length;
- GenericSorting.quickSort(from, to, comp, swapper);
-
- System.out.println("after:");
- System.out.println("X="+Arrays.toString(x));
- System.out.println("Y="+Arrays.toString(y));
- System.out.println("Z="+Arrays.toString(z));
- System.out.println("\n\n");
+ final int[] x;
+ final double[] y;
+ final double[] z;
+
+ x = new int[] {6, 7, 8, 9 };
+ y = new double[] {3.0, 2.0, 1.0, 3.0};
+ z = new double[] {5.0, 4.0, 4.0, 1.0};
+
+ Swapper swapper = new Swapper() {
+ public void swap(int a, int b) {
+ int t1; double t2, t3;
+ t1 = x[a]; x[a] = x[b]; x[b] = t1;
+ t2 = y[a]; y[a] = y[b]; y[b] = t2;
+ t3 = z[a]; z[a] = z[b]; z[b] = t3;
+ }
+ };
+
+ IntComparator comp = new IntComparator() {
+ public int compare(int a, int b) {
+ if (y[a]==y[b]) return z[a]==z[b] ? 0 : (z[a]<z[b] ? -1 : 1);
+ return y[a]<y[b] ? -1 : 1;
+ }
+ };
+
+
+ System.out.println("before:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+
+
+ int from = 0;
+ int to = x.length;
+ GenericSorting.quickSort(from, to, comp, swapper);
+
+ System.out.println("after:");
+ System.out.println("X="+Arrays.toString(x));
+ System.out.println("Y="+Arrays.toString(y));
+ System.out.println("Z="+Arrays.toString(z));
+ System.out.println("\n\n");
}
/**
* Checks the correctness of the partition method by generating random input parameters and checking whether results are correct.
*/
public static void testRandomly(int runs) {
- org.apache.mahout.jet.random.engine.RandomEngine engine = new org.apache.mahout.jet.random.engine.MersenneTwister();
- org.apache.mahout.jet.random.Uniform gen = new org.apache.mahout.jet.random.Uniform(engine);
-
- for (int run=0; run<runs; run++) {
- int maxSize = 50;
- int maxSplittersSize = 2*maxSize;
-
-
- int size = gen.nextIntFromTo(1,maxSize);
- int from, to;
- if (size==0) {
- from=0; to=-1;
- }
- else {
- from = gen.nextIntFromTo(0,size-1);
- to = gen.nextIntFromTo(Math.min(from,size-1),size-1);
- }
-
- org.apache.mahout.matrix.matrix.DoubleMatrix2D A1 = new org.apache.mahout.matrix.matrix.impl.DenseDoubleMatrix2D(size,size);
- org.apache.mahout.matrix.matrix.DoubleMatrix2D P1 = A1.viewPart(from,from,size-to,size-to);
-
- int intervalFrom = gen.nextIntFromTo(size/2,2*size);
- int intervalTo = gen.nextIntFromTo(intervalFrom,2*size);
-
- for (int i=0; i<size; i++) {
- for (int j=0; j<size; j++) {
- A1.set(i,j,gen.nextIntFromTo(intervalFrom,intervalTo));
- }
- }
-
- org.apache.mahout.matrix.matrix.DoubleMatrix2D A2 = A1.copy();
- org.apache.mahout.matrix.matrix.DoubleMatrix2D P2 = A2.viewPart(from,from,size-to,size-to);
-
- int c = 0;
- org.apache.mahout.matrix.matrix.DoubleMatrix2D S1 = org.apache.mahout.matrix.matrix.doublealgo.Sorting.quickSort.sort(P1,c);
- org.apache.mahout.matrix.matrix.DoubleMatrix2D S2 = org.apache.mahout.matrix.matrix.doublealgo.Sorting.mergeSort.sort(P2,c);
+ org.apache.mahout.jet.random.engine.RandomEngine engine = new org.apache.mahout.jet.random.engine.MersenneTwister();
+ org.apache.mahout.jet.random.Uniform gen = new org.apache.mahout.jet.random.Uniform(engine);
+
+ for (int run=0; run<runs; run++) {
+ int maxSize = 50;
+ int maxSplittersSize = 2*maxSize;
+
+
+ int size = gen.nextIntFromTo(1,maxSize);
+ int from, to;
+ if (size==0) {
+ from=0; to=-1;
+ }
+ else {
+ from = gen.nextIntFromTo(0,size-1);
+ to = gen.nextIntFromTo(Math.min(from,size-1),size-1);
+ }
+
+ org.apache.mahout.matrix.matrix.DoubleMatrix2D A1 = new org.apache.mahout.matrix.matrix.impl.DenseDoubleMatrix2D(size,size);
+ org.apache.mahout.matrix.matrix.DoubleMatrix2D P1 = A1.viewPart(from,from,size-to,size-to);
+
+ int intervalFrom = gen.nextIntFromTo(size/2,2*size);
+ int intervalTo = gen.nextIntFromTo(intervalFrom,2*size);
+
+ for (int i=0; i<size; i++) {
+ for (int j=0; j<size; j++) {
+ A1.set(i,j,gen.nextIntFromTo(intervalFrom,intervalTo));
+ }
+ }
+
+ org.apache.mahout.matrix.matrix.DoubleMatrix2D A2 = A1.copy();
+ org.apache.mahout.matrix.matrix.DoubleMatrix2D P2 = A2.viewPart(from,from,size-to,size-to);
+
+ int c = 0;
+ org.apache.mahout.matrix.matrix.DoubleMatrix2D S1 = org.apache.mahout.matrix.matrix.doublealgo.Sorting.quickSort.sort(P1,c);
+ org.apache.mahout.matrix.matrix.DoubleMatrix2D S2 = org.apache.mahout.matrix.matrix.doublealgo.Sorting.mergeSort.sort(P2,c);
- if (!(S1.viewColumn(c).equals(S2.viewColumn(c)))) throw new InternalError();
- }
+ if (!(S1.viewColumn(c).equals(S2.viewColumn(c)))) throw new InternalError();
+ }
- System.out.println("All tests passed. No bug detected.");
+ System.out.println("All tests passed. No bug detected.");
}
}