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:31:49 UTC
svn commit: r883972 [6/10] - in /lucene/mahout/trunk:
core/src/main/java/org/apache/mahout/fpm/pfpgrowth/
matrix/src/main/java/org/apache/mahout/jet/math/
matrix/src/main/java/org/apache/mahout/jet/random/
matrix/src/main/java/org/apache/mahout/jet/ran...
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister.java Wed Nov 25 03:31:47 2009
@@ -23,19 +23,19 @@
Be aware, however, that there is a non-negligible amount of overhead required to initialize the data
structures used by a MersenneTwister. Code like
<pre>
- double sum = 0.0;
- for (int i=0; i<100000; ++i) {
- RandomElement twister = new MersenneTwister(new java.util.Date());
- sum += twister.raw();
- }
+ double sum = 0.0;
+ for (int i=0; i<100000; ++i) {
+ RandomElement twister = new MersenneTwister(new java.util.Date());
+ sum += twister.raw();
+ }
</pre>
will be wildly inefficient. Consider using
<pre>
- double sum = 0.0;
- RandomElement twister = new MersenneTwister(new java.util.Date());
- for (int i=0; i<100000; ++i) {
- sum += twister.raw();
- }
+ double sum = 0.0;
+ RandomElement twister = new MersenneTwister(new java.util.Date());
+ for (int i=0; i<100000; ++i) {
+ sum += twister.raw();
+ }
</pre>
instead. This allows the cost of constructing the MersenneTwister object
to be borne only once, rather than once for each iteration in the loop.
@@ -65,36 +65,36 @@
<div align="center">
<table width="75%" border="1" cellspacing="0" cellpadding="0">
<tr>
- <td width="2%"> <div align="center">n</div> </td>
- <td width="6%"> <div align="center">1</div> </td>
- <td width="5%"> <div align="center">2</div> </td>
- <td width="5%"> <div align="center">3</div> </td>
- <td width="5%"> <div align="center">4</div> </td>
- <td width="5%"> <div align="center">5</div> </td>
- <td width="5%"> <div align="center">6</div> </td>
- <td width="5%"> <div align="center">7</div> </td>
- <td width="5%"> <div align="center">8</div> </td>
- <td width="5%"> <div align="center">9</div> </td>
- <td width="5%"> <div align="center">10</div> </td>
- <td width="5%"> <div align="center">11</div> </td>
- <td width="10%"> <div align="center">12 .. 16</div> </td>
- <td width="10%"> <div align="center">17 .. 32</div> </td>
+ <td width="2%"> <div align="center">n</div> </td>
+ <td width="6%"> <div align="center">1</div> </td>
+ <td width="5%"> <div align="center">2</div> </td>
+ <td width="5%"> <div align="center">3</div> </td>
+ <td width="5%"> <div align="center">4</div> </td>
+ <td width="5%"> <div align="center">5</div> </td>
+ <td width="5%"> <div align="center">6</div> </td>
+ <td width="5%"> <div align="center">7</div> </td>
+ <td width="5%"> <div align="center">8</div> </td>
+ <td width="5%"> <div align="center">9</div> </td>
+ <td width="5%"> <div align="center">10</div> </td>
+ <td width="5%"> <div align="center">11</div> </td>
+ <td width="10%"> <div align="center">12 .. 16</div> </td>
+ <td width="10%"> <div align="center">17 .. 32</div> </td>
</tr>
<tr>
- <td width="2%"> <div align="center">k</div> </td>
- <td width="6%"> <div align="center">19937</div> </td>
- <td width="5%"> <div align="center">9968</div> </td>
- <td width="5%"> <div align="center">6240</div> </td>
- <td width="5%"> <div align="center">4984</div> </td>
- <td width="5%"> <div align="center">3738</div> </td>
- <td width="5%"> <div align="center">3115</div> </td>
- <td width="5%"> <div align="center">2493</div> </td>
- <td width="5%"> <div align="center">2492</div> </td>
- <td width="5%"> <div align="center">1869</div> </td>
- <td width="5%"> <div align="center">1869</div> </td>
- <td width="5%"> <div align="center">1248</div> </td>
- <td width="10%"> <div align="center">1246</div> </td>
- <td width="10%"> <div align="center">623</div> </td>
+ <td width="2%"> <div align="center">k</div> </td>
+ <td width="6%"> <div align="center">19937</div> </td>
+ <td width="5%"> <div align="center">9968</div> </td>
+ <td width="5%"> <div align="center">6240</div> </td>
+ <td width="5%"> <div align="center">4984</div> </td>
+ <td width="5%"> <div align="center">3738</div> </td>
+ <td width="5%"> <div align="center">3115</div> </td>
+ <td width="5%"> <div align="center">2493</div> </td>
+ <td width="5%"> <div align="center">2492</div> </td>
+ <td width="5%"> <div align="center">1869</div> </td>
+ <td width="5%"> <div align="center">1869</div> </td>
+ <td width="5%"> <div align="center">1248</div> </td>
+ <td width="10%"> <div align="center">1246</div> </td>
+ <td width="10%"> <div align="center">623</div> </td>
</tr>
</table>
</div>
@@ -115,39 +115,39 @@
*/
@Deprecated
public class MersenneTwister extends RandomEngine {
- private int mti;
- private int[] mt = new int[N]; /* set initial seeds: N = 624 words */
+ private int mti;
+ private int[] mt = new int[N]; /* set initial seeds: N = 624 words */
- /* Period parameters */
- private static final int N=624;
- private static final int M=397;
- private static final int MATRIX_A=0x9908b0df; /* constant vector a */
- private static final int UPPER_MASK=0x80000000; /* most significant w-r bits */
- private static final int LOWER_MASK=0x7fffffff; /* least significant r bits */
-
- /* for tempering */
- private static final int TEMPERING_MASK_B=0x9d2c5680;
- private static final int TEMPERING_MASK_C=0xefc60000;
-
- private static final int mag0 = 0x0;
- private static final int mag1 = MATRIX_A;
- //private static final int[] mag01=new int[] {0x0, MATRIX_A};
- /* mag01[x] = x * MATRIX_A for x=0,1 */
+ /* Period parameters */
+ private static final int N=624;
+ private static final int M=397;
+ private static final int MATRIX_A=0x9908b0df; /* constant vector a */
+ private static final int UPPER_MASK=0x80000000; /* most significant w-r bits */
+ private static final int LOWER_MASK=0x7fffffff; /* least significant r bits */
+
+ /* for tempering */
+ private static final int TEMPERING_MASK_B=0x9d2c5680;
+ private static final int TEMPERING_MASK_C=0xefc60000;
+
+ private static final int mag0 = 0x0;
+ private static final int mag1 = MATRIX_A;
+ //private static final int[] mag01=new int[] {0x0, MATRIX_A};
+ /* mag01[x] = x * MATRIX_A for x=0,1 */
- public static final int DEFAULT_SEED = 4357;
+ public static final int DEFAULT_SEED = 4357;
/**
* Constructs and returns a random number generator with a default seed, which is a <b>constant</b>.
* Thus using this constructor will yield generators that always produce exactly the same sequence.
* This method is mainly intended to ease testing and debugging.
*/
public MersenneTwister() {
- this(DEFAULT_SEED);
+ this(DEFAULT_SEED);
}
/**
* Constructs and returns a random number generator with the given seed.
*/
public MersenneTwister(int seed) {
- setSeed(seed);
+ setSeed(seed);
}
/**
* Constructs and returns a random number generator seeded with the given date.
@@ -155,7 +155,7 @@
* @param d typically <tt>new java.util.Date()</tt>
*/
public MersenneTwister(Date d) {
- this((int)d.getTime());
+ this((int)d.getTime());
}
/**
* Returns a copy of the receiver; the copy will produce identical sequences.
@@ -164,104 +164,104 @@
* @return a copy of the receiver.
*/
public Object clone() {
- MersenneTwister clone = (MersenneTwister) super.clone();
- clone.mt = (int[]) this.mt.clone();
- return clone;
+ MersenneTwister clone = (MersenneTwister) super.clone();
+ clone.mt = (int[]) this.mt.clone();
+ return clone;
}
/**
* Generates N words at one time.
*/
protected void nextBlock() {
- /*
- // ******************** OPTIMIZED **********************
- // only 5-10% faster ?
- int y;
-
- int kk;
- int[] cache = mt; // cached for speed
- int kkM;
- int limit = N-M;
- for (kk=0,kkM=kk+M; kk<limit; kk++,kkM++) {
- y = (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK);
- cache[kk] = cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
- }
- limit = N-1;
- for (kkM=kk+(M-N); kk<limit; kk++,kkM++) {
- y = (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK);
- cache[kk] = cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
- }
- y = (cache[N-1]&UPPER_MASK)|(cache[0]&LOWER_MASK);
- cache[N-1] = cache[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
-
- this.mt = cache;
- this.mti = 0;
- */
-
-
-
- // ******************** UNOPTIMIZED **********************
- int y;
-
- int kk;
-
- for (kk=0;kk<N-M;kk++) {
- y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
- mt[kk] = mt[kk+M] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
- }
- for (;kk<N-1;kk++) {
- y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
- mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
- }
- y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
- mt[N-1] = mt[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ /*
+ // ******************** OPTIMIZED **********************
+ // only 5-10% faster ?
+ int y;
+
+ int kk;
+ int[] cache = mt; // cached for speed
+ int kkM;
+ int limit = N-M;
+ for (kk=0,kkM=kk+M; kk<limit; kk++,kkM++) {
+ y = (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK);
+ cache[kk] = cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ }
+ limit = N-1;
+ for (kkM=kk+(M-N); kk<limit; kk++,kkM++) {
+ y = (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK);
+ cache[kk] = cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ }
+ y = (cache[N-1]&UPPER_MASK)|(cache[0]&LOWER_MASK);
+ cache[N-1] = cache[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+
+ this.mt = cache;
+ this.mti = 0;
+ */
+
- this.mti = 0;
-
+
+ // ******************** UNOPTIMIZED **********************
+ int y;
+
+ int kk;
+
+ for (kk=0;kk<N-M;kk++) {
+ y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+ mt[kk] = mt[kk+M] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ }
+ for (;kk<N-1;kk++) {
+ y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+ mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+ }
+ y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
+ mt[N-1] = mt[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
+
+ this.mti = 0;
+
}
/**
* Returns a 32 bit uniformly distributed random number in the closed interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including <tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>).
*/
public int nextInt() {
- /* Each single bit including the sign bit will be random */
- if (mti == N) nextBlock(); // generate N ints at one time
+ /* Each single bit including the sign bit will be random */
+ if (mti == N) nextBlock(); // generate N ints at one time
- int y = mt[mti++];
- y ^= y >>> 11; // y ^= TEMPERING_SHIFT_U(y );
- y ^= (y << 7) & TEMPERING_MASK_B; // y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
- y ^= (y << 15) & TEMPERING_MASK_C; // y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
- // y &= 0xffffffff; //you may delete this line if word size = 32
- y ^= y >>> 18; // y ^= TEMPERING_SHIFT_L(y);
+ int y = mt[mti++];
+ y ^= y >>> 11; // y ^= TEMPERING_SHIFT_U(y );
+ y ^= (y << 7) & TEMPERING_MASK_B; // y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
+ y ^= (y << 15) & TEMPERING_MASK_C; // y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
+ // y &= 0xffffffff; //you may delete this line if word size = 32
+ y ^= y >>> 18; // y ^= TEMPERING_SHIFT_L(y);
- return y;
+ return y;
}
/**
* Sets the receiver's seed.
* This method resets the receiver's entire internal state.
*/
protected void setSeed(int seed) {
- mt[0] = seed & 0xffffffff;
- for (int i = 1; i < N; i++) {
- mt[i] = (1812433253 * (mt[i-1] ^ (mt[i-1] >> 30)) + i);
- /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
- /* In the previous versions, MSBs of the seed affect */
- /* only MSBs of the array mt[]. */
- /* 2002/01/09 modified by Makoto Matsumoto */
- mt[i] &= 0xffffffff;
- /* for >32 bit machines */
- }
- //System.out.println("init done");
- mti = N;
-
- /*
- old version was:
- for (int i = 0; i < N; i++) {
- mt[i] = seed & 0xffff0000;
- seed = 69069 * seed + 1;
- mt[i] |= (seed & 0xffff0000) >>> 16;
- seed = 69069 * seed + 1;
- }
- //System.out.println("init done");
- mti = N;
- */
+ mt[0] = seed & 0xffffffff;
+ for (int i = 1; i < N; i++) {
+ mt[i] = (1812433253 * (mt[i-1] ^ (mt[i-1] >> 30)) + i);
+ /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+ /* In the previous versions, MSBs of the seed affect */
+ /* only MSBs of the array mt[]. */
+ /* 2002/01/09 modified by Makoto Matsumoto */
+ mt[i] &= 0xffffffff;
+ /* for >32 bit machines */
+ }
+ //System.out.println("init done");
+ mti = N;
+
+ /*
+ old version was:
+ for (int i = 0; i < N; i++) {
+ mt[i] = seed & 0xffff0000;
+ seed = 69069 * seed + 1;
+ mt[i] |= (seed & 0xffff0000) >>> 16;
+ seed = 69069 * seed + 1;
+ }
+ //System.out.println("init done");
+ mti = N;
+ */
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister64.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister64.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister64.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/MersenneTwister64.java Wed Nov 25 03:31:47 2009
@@ -12,8 +12,6 @@
/**
* Same as <tt>MersenneTwister</tt> except that method <tt>raw()</tt> returns 64 bit random numbers instead of 32 bit random numbers.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
* @see MersenneTwister
*/
/**
@@ -25,14 +23,14 @@
* Constructs and returns a random number generator with a default seed, which is a <b>constant</b>.
*/
public MersenneTwister64() {
- super();
+ super();
}
/**
* Constructs and returns a random number generator with the given seed.
* @param seed should not be 0, in such a case <tt>MersenneTwister64.DEFAULT_SEED</tt> is silently substituted.
*/
public MersenneTwister64(int seed) {
- super(seed);
+ super(seed);
}
/**
* Constructs and returns a random number generator seeded with the given date.
@@ -40,12 +38,12 @@
* @param d typically <tt>new java.util.Date()</tt>
*/
public MersenneTwister64(Date d) {
- super(d);
+ super(d);
}
/**
* Returns a 64 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
*/
public double raw() {
- return nextDouble();
+ return nextDouble();
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomEngine.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomEngine.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomEngine.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomEngine.java Wed Nov 25 03:31:47 2009
@@ -26,8 +26,6 @@
* <p>
* Note that this implementation is <b>not synchronized</b>.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
* @see MersenneTwister
* @see MersenneTwister64
* @see java.util.Random
@@ -47,65 +45,65 @@
This has the effect that random engines can now be used as function objects, returning a random number upon function evaluation.
*/
public double apply(double dummy) {
- return raw();
+ return raw();
}
/**
Equivalent to <tt>nextInt()</tt>.
This has the effect that random engines can now be used as function objects, returning a random number upon function evaluation.
*/
public int apply(int dummy) {
- return nextInt();
+ return nextInt();
}
/**
* Constructs and returns a new uniform random number engine seeded with the current time.
* Currently this is {@link org.apache.mahout.jet.random.engine.MersenneTwister}.
*/
public static RandomEngine makeDefault() {
- return new org.apache.mahout.jet.random.engine.MersenneTwister((int) System.currentTimeMillis());
+ return new org.apache.mahout.jet.random.engine.MersenneTwister((int) System.currentTimeMillis());
}
/**
* Returns a 64 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
*/
public double nextDouble() {
- double nextDouble;
-
- do {
- // -9.223372036854776E18 == (double) Long.MIN_VALUE
- // 5.421010862427522E-20 == 1 / Math.pow(2,64) == 1 / ((double) Long.MAX_VALUE - (double) Long.MIN_VALUE);
- nextDouble = ((double) nextLong() - -9.223372036854776E18) * 5.421010862427522E-20;
- }
- // catch loss of precision of long --> double conversion
- while (! (nextDouble>0.0 && nextDouble<1.0));
-
- // --> in (0.0,1.0)
- return nextDouble;
+ double nextDouble;
+
+ do {
+ // -9.223372036854776E18 == (double) Long.MIN_VALUE
+ // 5.421010862427522E-20 == 1 / Math.pow(2,64) == 1 / ((double) Long.MAX_VALUE - (double) Long.MIN_VALUE);
+ nextDouble = ((double) nextLong() - -9.223372036854776E18) * 5.421010862427522E-20;
+ }
+ // catch loss of precision of long --> double conversion
+ while (! (nextDouble>0.0 && nextDouble<1.0));
+
+ // --> in (0.0,1.0)
+ return nextDouble;
- /*
- nextLong == Long.MAX_VALUE --> 1.0
- nextLong == Long.MIN_VALUE --> 0.0
- nextLong == Long.MAX_VALUE-1 --> 1.0
- nextLong == Long.MAX_VALUE-100000L --> 0.9999999999999946
- nextLong == Long.MIN_VALUE+1 --> 0.0
- nextLong == Long.MIN_VALUE-100000L --> 0.9999999999999946
- nextLong == 1L --> 0.5
- nextLong == -1L --> 0.5
- nextLong == 2L --> 0.5
- nextLong == -2L --> 0.5
- nextLong == 2L+100000L --> 0.5000000000000054
- nextLong == -2L-100000L --> 0.49999999999999456
- */
+ /*
+ nextLong == Long.MAX_VALUE --> 1.0
+ nextLong == Long.MIN_VALUE --> 0.0
+ nextLong == Long.MAX_VALUE-1 --> 1.0
+ nextLong == Long.MAX_VALUE-100000L --> 0.9999999999999946
+ nextLong == Long.MIN_VALUE+1 --> 0.0
+ nextLong == Long.MIN_VALUE-100000L --> 0.9999999999999946
+ nextLong == 1L --> 0.5
+ nextLong == -1L --> 0.5
+ nextLong == 2L --> 0.5
+ nextLong == -2L --> 0.5
+ nextLong == 2L+100000L --> 0.5000000000000054
+ nextLong == -2L-100000L --> 0.49999999999999456
+ */
}
/**
* Returns a 32 bit uniformly distributed random number in the open unit interval <code>(0.0f,1.0f)</code> (excluding 0.0f and 1.0f).
*/
public float nextFloat() {
- // catch loss of precision of double --> float conversion
- float nextFloat;
- do { nextFloat = (float) raw(); }
- while (nextFloat>=1.0f);
-
- // --> in (0.0f,1.0f)
- return nextFloat;
+ // catch loss of precision of double --> float conversion
+ float nextFloat;
+ do { nextFloat = (float) raw(); }
+ while (nextFloat>=1.0f);
+
+ // --> in (0.0f,1.0f)
+ return nextFloat;
}
/**
* Returns a 32 bit uniformly distributed random number in the closed interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including <tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>);
@@ -115,32 +113,32 @@
* Returns a 64 bit uniformly distributed random number in the closed interval <tt>[Long.MIN_VALUE,Long.MAX_VALUE]</tt> (including <tt>Long.MIN_VALUE</tt> and <tt>Long.MAX_VALUE</tt>).
*/
public long nextLong() {
- // concatenate two 32-bit strings into one 64-bit string
- return ((nextInt() & 0xFFFFFFFFL) << 32)
- | ((nextInt() & 0xFFFFFFFFL));
+ // concatenate two 32-bit strings into one 64-bit string
+ return ((nextInt() & 0xFFFFFFFFL) << 32)
+ | ((nextInt() & 0xFFFFFFFFL));
}
/**
* Returns a 32 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
*/
public double raw() {
- int nextInt;
- do { // accept anything but zero
- nextInt = nextInt(); // in [Integer.MIN_VALUE,Integer.MAX_VALUE]-interval
- } while (nextInt==0);
+ int nextInt;
+ do { // accept anything but zero
+ nextInt = nextInt(); // in [Integer.MIN_VALUE,Integer.MAX_VALUE]-interval
+ } while (nextInt==0);
- // transform to (0.0,1.0)-interval
- // 2.3283064365386963E-10 == 1.0 / Math.pow(2,32)
- return (double) (nextInt & 0xFFFFFFFFL) * 2.3283064365386963E-10;
-
- /*
- nextInt == Integer.MAX_VALUE --> 0.49999999976716936
- nextInt == Integer.MIN_VALUE --> 0.5
- nextInt == Integer.MAX_VALUE-1 --> 0.4999999995343387
- nextInt == Integer.MIN_VALUE+1 --> 0.5000000002328306
- nextInt == 1 --> 2.3283064365386963E-10
- nextInt == -1 --> 0.9999999997671694
- nextInt == 2 --> 4.6566128730773926E-10
- nextInt == -2 --> 0.9999999995343387
- */
+ // transform to (0.0,1.0)-interval
+ // 2.3283064365386963E-10 == 1.0 / Math.pow(2,32)
+ return (double) (nextInt & 0xFFFFFFFFL) * 2.3283064365386963E-10;
+
+ /*
+ nextInt == Integer.MAX_VALUE --> 0.49999999976716936
+ nextInt == Integer.MIN_VALUE --> 0.5
+ nextInt == Integer.MAX_VALUE-1 --> 0.4999999995343387
+ nextInt == Integer.MIN_VALUE+1 --> 0.5000000002328306
+ nextInt == 1 --> 2.3283064365386963E-10
+ nextInt == -1 --> 0.9999999997671694
+ nextInt == 2 --> 4.6566128730773926E-10
+ nextInt == -2 --> 0.9999999995343387
+ */
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomGenerator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomGenerator.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomGenerator.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomGenerator.java Wed Nov 25 03:31:47 2009
@@ -17,28 +17,28 @@
@Deprecated
public interface RandomGenerator {
- /**
- * Returns a 32 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
- */
- public double raw();
+ /**
+ * Returns a 32 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
+ */
+ public double raw();
- /**
- * Returns a 64 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
- */
- public double nextDouble();
-
- /**
- * Returns a 32 bit uniformly distributed random number in the closed interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including <tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>);
- */
- public int nextInt();
-
- /**
- * Returns a 64 bit uniformly distributed random number in the closed interval <tt>[Long.MIN_VALUE,Long.MAX_VALUE]</tt> (including <tt>Long.MIN_VALUE</tt> and <tt>Long.MAX_VALUE</tt>).
- */
- public long nextLong();
+ /**
+ * Returns a 64 bit uniformly distributed random number in the open unit interval <code>(0.0,1.0)</code> (excluding 0.0 and 1.0).
+ */
+ public double nextDouble();
+
+ /**
+ * Returns a 32 bit uniformly distributed random number in the closed interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including <tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>);
+ */
+ public int nextInt();
+
+ /**
+ * Returns a 64 bit uniformly distributed random number in the closed interval <tt>[Long.MIN_VALUE,Long.MAX_VALUE]</tt> (including <tt>Long.MIN_VALUE</tt> and <tt>Long.MAX_VALUE</tt>).
+ */
+ public long nextLong();
- /**
- * Returns a 32 bit uniformly distributed random number in the open unit interval <code>(0.0f,1.0f)</code> (excluding 0.0f and 1.0f).
- */
- public float nextFloat();
+ /**
+ * Returns a 32 bit uniformly distributed random number in the open unit interval <code>(0.0f,1.0f)</code> (excluding 0.0f and 1.0f).
+ */
+ public float nextFloat();
}
\ No newline at end of file
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedGenerator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedGenerator.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedGenerator.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedGenerator.java Wed Nov 25 03:31:47 2009
@@ -20,21 +20,19 @@
* Each generated sequence of seeds has a period of 10<sup>9</sup> numbers.
* Internally uses {@link RandomSeedTable}.
*
- * @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 class RandomSeedGenerator extends org.apache.mahout.matrix.PersistentObject {
- protected int row;
- protected int column;
+ protected int row;
+ protected int column;
/**
* Constructs and returns a new seed generator.
*/
public RandomSeedGenerator() {
- this(0,0);
+ this(0,0);
}
/**
* Constructs and returns a new seed generator; you normally won't need to use this method.
@@ -48,35 +46,35 @@
* @param column should be in <tt>[0,RandomSeedTable.COLUMNS - 1]</tt>.
*/
public RandomSeedGenerator(int row, int column) {
- this.row = row;
- this.column = column;
+ this.row = row;
+ this.column = column;
}
/**
* Prints the generated seeds for the given input parameters.
*/
public static void main(String args[]) {
- int row = Integer.parseInt(args[0]);
- int column = Integer.parseInt(args[1]);
- int size = Integer.parseInt(args[2]);
- new RandomSeedGenerator(row,column).print(size);
+ int row = Integer.parseInt(args[0]);
+ int column = Integer.parseInt(args[1]);
+ int size = Integer.parseInt(args[2]);
+ new RandomSeedGenerator(row,column).print(size);
}
/**
* Returns the next seed.
*/
public int nextSeed() {
- return RandomSeedTable.getSeedAtRowColumn(row++, column);
+ return RandomSeedTable.getSeedAtRowColumn(row++, column);
}
/**
* Prints the next <tt>size</tt> generated seeds.
*/
public void print(int size) {
- System.out.println("Generating "+size+" random seeds...");
- RandomSeedGenerator copy = (RandomSeedGenerator) this.clone();
- for (int i=0; i<size; i++) {
- int seed = copy.nextSeed();
- System.out.println(seed);
- }
+ System.out.println("Generating "+size+" random seeds...");
+ RandomSeedGenerator copy = (RandomSeedGenerator) this.clone();
+ for (int i=0; i<size; i++) {
+ int seed = copy.nextSeed();
+ System.out.println(seed);
+ }
- System.out.println("\ndone.");
+ System.out.println("\ndone.");
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedTable.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedTable.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedTable.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/engine/RandomSeedTable.java Wed Nov 25 03:31:47 2009
@@ -17,242 +17,240 @@
* Geant4, in turn, took the table from the original FORTRAN77 implementation of the HEP CERN Library routine RECUSQ.
* Each sequence has a period of 10**9 numbers.
*
- * @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 class RandomSeedTable {
- /**
- * The number of columns of the matrix (currently COLUMNS = 2).
- */
- public static final int COLUMNS = 2;
+ /**
+ * The number of columns of the matrix (currently COLUMNS = 2).
+ */
+ public static final int COLUMNS = 2;
- // a m*n matrix, just stored as one-dim array
- // 215 * 2 entries
- private static final int[] seeds = new int[] {
- 9876, 54321,
- 1299961164, 253987020,
- 669708517, 2079157264,
- 190904760, 417696270,
- 1289741558, 1376336092,
- 1803730167, 324952955,
- 489854550, 582847132,
- 1348037628, 1661577989,
- 350557787, 1155446919,
- 591502945, 634133404,
- 1901084678, 862916278,
- 1988640932, 1785523494,
- 1873836227, 508007031,
- 1146416592, 967585720,
- 1837193353, 1522927634,
- 38219936, 921609208,
- 349152748, 112892610,
- 744459040, 1735807920,
- 1983990104, 728277902,
- 309164507, 2126677523,
- 362993787, 1897782044,
- 556776976, 462072869,
- 1584900822, 2019394912,
- 1249892722, 791083656,
- 1686600998, 1983731097,
- 1127381380, 198976625,
- 1999420861, 1810452455,
- 1972906041, 664182577,
- 84636481, 1291886301,
- 1186362995, 954388413,
- 2141621785, 61738584,
- 1969581251, 1557880415,
- 1150606439, 136325185,
- 95187861, 1592224108,
- 940517655, 1629971798,
- 215350428, 922659102,
- 786161212, 1121345074,
- 1450830056, 1922787776,
- 1696578057, 2025150487,
- 1803414346, 1851324780,
- 1017898585, 1452594263,
- 1184497978, 82122239,
- 633338765, 1829684974,
- 430889421, 230039326,
- 492544653, 76320266,
- 389386975, 1314148944,
- 1720322786, 709120323,
- 1868768216, 1992898523,
- 443210610, 811117710,
- 1191938868, 1548484733,
- 616890172, 159787986,
- 935835339, 1231440405,
- 1058009367, 1527613300,
- 1463148129, 1970575097,
- 1795336935, 434768675,
- 274019517, 605098487,
- 483689317, 217146977,
- 2070804364, 340596558,
- 930226308, 1602100969,
- 989324440, 801809442,
- 410606853, 1893139948,
- 1583588576, 1219225407,
- 2102034391, 1394921405,
- 2005037790, 2031006861,
- 1244218766, 923231061,
- 49312790, 775496649,
- 721012176, 321339902,
- 1719909107, 1865748178,
- 1156177430, 1257110891,
- 307561322, 1918244397,
- 906041433, 360476981,
- 1591375755, 268492659,
- 461522398, 227343256,
- 2145930725, 2020665454,
- 1938419274, 1331283701,
- 174405412, 524140103,
- 494343653, 18063908,
- 1025534808, 181709577,
- 2048959776, 1913665637,
- 950636517, 794796256,
- 1828843197, 1335757744,
- 211109723, 983900607,
- 825474095, 1046009991,
- 374915657, 381856628,
- 1241296328, 698149463,
- 1260624655, 1024538273,
- 900676210, 1628865823,
- 697951025, 500570753,
- 1007920268, 1708398558,
- 264596520, 624727803,
- 1977924811, 674673241,
- 1440257718, 271184151,
- 1928778847, 993535203,
- 1307807366, 1801502463,
- 1498732610, 300876954,
- 1617712402, 1574250679,
- 1261800762, 1556667280,
- 949929273, 560721070,
- 1766170474, 1953522912,
- 1849939248, 19435166,
- 887262858, 1219627824,
- 483086133, 603728993,
- 1330541052, 1582596025,
- 1850591475, 723593133,
- 1431775678, 1558439000,
- 922493739, 1356554404,
- 1058517206, 948567762,
- 709067283, 1350890215,
- 1044787723, 2144304941,
- 999707003, 513837520,
- 2140038663, 1850568788,
- 1803100150, 127574047,
- 867445693, 1149173981,
- 408583729, 914837991,
- 1166715497, 602315845,
- 430738528, 1743308384,
- 1388022681, 1760110496,
- 1664028066, 654300326,
- 1767741172, 1338181197,
- 1625723550, 1742482745,
- 464486085, 1507852127,
- 754082421, 1187454014,
- 1315342834, 425995190,
- 960416608, 2004255418,
- 1262630671, 671761697,
- 59809238, 103525918,
- 1205644919, 2107823293,
- 1615183160, 1152411412,
- 1024474681, 2118672937,
- 1703877649, 1235091369,
- 1821417852, 1098463802,
- 1738806466, 1529062843,
- 620780646, 1654833544,
- 1070174101, 795158254,
- 658537995, 1693620426,
- 2055317555, 508053916,
- 1647371686, 1282395762,
- 29067379, 409683067,
- 1763495989, 1917939635,
- 1602690753, 810926582,
- 885787576, 513818500,
- 1853512561, 1195205756,
- 1798585498, 1970460256,
- 1819261032, 1306536501,
- 1133245275, 37901,
- 689459799, 1334389069,
- 1730609912, 1854586207,
- 1556832175, 1228729041,
- 251375753, 683687209,
- 2083946182, 1763106152,
- 2142981854, 1365385561,
- 763711891, 1735754548,
- 1581256466, 173689858,
- 2121337132, 1247108250,
- 1004003636, 891894307,
- 569816524, 358675254,
- 626626425, 116062841,
- 632086003, 861268491,
- 1008211580, 779404957,
- 1134217766, 1766838261,
- 1423829292, 1706666192,
- 942037869, 1549358884,
- 1959429535, 480779114,
- 778311037, 1940360875,
- 1531372185, 2009078158,
- 241935492, 1050047003,
- 272453504, 1870883868,
- 390441332, 1057903098,
- 1230238834, 1548117688,
- 1242956379, 1217296445,
- 515648357, 1675011378,
- 364477932, 355212934,
- 2096008713, 1570161804,
- 1409752526, 214033983,
- 1288158292, 1760636178,
- 407562666, 1265144848,
- 1071056491, 1582316946,
- 1014143949, 911406955,
- 203080461, 809380052,
- 125647866, 1705464126,
- 2015685843, 599230667,
- 1425476020, 668203729,
- 1673735652, 567931803,
- 1714199325, 181737617,
- 1389137652, 678147926,
- 288547803, 435433694,
- 200159281, 654399753,
- 1580828223, 1298308945,
- 1832286107, 169991953,
- 182557704, 1046541065,
- 1688025575, 1248944426,
- 1508287706, 1220577001,
- 36721212, 1377275347,
- 1968679856, 1675229747,
- 279109231, 1835333261,
- 1358617667, 1416978076,
- 740626186, 2103913602,
- 1882655908, 251341858,
- 648016670, 1459615287,
- 780255321, 154906988,
- 857296483, 203375965,
- 1631676846, 681204578,
- 1906971307, 1623728832,
- 1541899600, 1168449797,
- 1267051693, 1020078717,
- 1998673940, 1298394942,
- 1914117058, 1381290704,
- 426068513, 1381618498,
- 139365577, 1598767734,
- 2129910384, 952266588,
- 661788054, 19661356,
- 1104640222, 240506063,
- 356133630, 1676634527,
- 242242374, 1863206182,
- 957935844, 1490681416 };
+ // a m*n matrix, just stored as one-dim array
+ // 215 * 2 entries
+ private static final int[] seeds = new int[] {
+ 9876, 54321,
+ 1299961164, 253987020,
+ 669708517, 2079157264,
+ 190904760, 417696270,
+ 1289741558, 1376336092,
+ 1803730167, 324952955,
+ 489854550, 582847132,
+ 1348037628, 1661577989,
+ 350557787, 1155446919,
+ 591502945, 634133404,
+ 1901084678, 862916278,
+ 1988640932, 1785523494,
+ 1873836227, 508007031,
+ 1146416592, 967585720,
+ 1837193353, 1522927634,
+ 38219936, 921609208,
+ 349152748, 112892610,
+ 744459040, 1735807920,
+ 1983990104, 728277902,
+ 309164507, 2126677523,
+ 362993787, 1897782044,
+ 556776976, 462072869,
+ 1584900822, 2019394912,
+ 1249892722, 791083656,
+ 1686600998, 1983731097,
+ 1127381380, 198976625,
+ 1999420861, 1810452455,
+ 1972906041, 664182577,
+ 84636481, 1291886301,
+ 1186362995, 954388413,
+ 2141621785, 61738584,
+ 1969581251, 1557880415,
+ 1150606439, 136325185,
+ 95187861, 1592224108,
+ 940517655, 1629971798,
+ 215350428, 922659102,
+ 786161212, 1121345074,
+ 1450830056, 1922787776,
+ 1696578057, 2025150487,
+ 1803414346, 1851324780,
+ 1017898585, 1452594263,
+ 1184497978, 82122239,
+ 633338765, 1829684974,
+ 430889421, 230039326,
+ 492544653, 76320266,
+ 389386975, 1314148944,
+ 1720322786, 709120323,
+ 1868768216, 1992898523,
+ 443210610, 811117710,
+ 1191938868, 1548484733,
+ 616890172, 159787986,
+ 935835339, 1231440405,
+ 1058009367, 1527613300,
+ 1463148129, 1970575097,
+ 1795336935, 434768675,
+ 274019517, 605098487,
+ 483689317, 217146977,
+ 2070804364, 340596558,
+ 930226308, 1602100969,
+ 989324440, 801809442,
+ 410606853, 1893139948,
+ 1583588576, 1219225407,
+ 2102034391, 1394921405,
+ 2005037790, 2031006861,
+ 1244218766, 923231061,
+ 49312790, 775496649,
+ 721012176, 321339902,
+ 1719909107, 1865748178,
+ 1156177430, 1257110891,
+ 307561322, 1918244397,
+ 906041433, 360476981,
+ 1591375755, 268492659,
+ 461522398, 227343256,
+ 2145930725, 2020665454,
+ 1938419274, 1331283701,
+ 174405412, 524140103,
+ 494343653, 18063908,
+ 1025534808, 181709577,
+ 2048959776, 1913665637,
+ 950636517, 794796256,
+ 1828843197, 1335757744,
+ 211109723, 983900607,
+ 825474095, 1046009991,
+ 374915657, 381856628,
+ 1241296328, 698149463,
+ 1260624655, 1024538273,
+ 900676210, 1628865823,
+ 697951025, 500570753,
+ 1007920268, 1708398558,
+ 264596520, 624727803,
+ 1977924811, 674673241,
+ 1440257718, 271184151,
+ 1928778847, 993535203,
+ 1307807366, 1801502463,
+ 1498732610, 300876954,
+ 1617712402, 1574250679,
+ 1261800762, 1556667280,
+ 949929273, 560721070,
+ 1766170474, 1953522912,
+ 1849939248, 19435166,
+ 887262858, 1219627824,
+ 483086133, 603728993,
+ 1330541052, 1582596025,
+ 1850591475, 723593133,
+ 1431775678, 1558439000,
+ 922493739, 1356554404,
+ 1058517206, 948567762,
+ 709067283, 1350890215,
+ 1044787723, 2144304941,
+ 999707003, 513837520,
+ 2140038663, 1850568788,
+ 1803100150, 127574047,
+ 867445693, 1149173981,
+ 408583729, 914837991,
+ 1166715497, 602315845,
+ 430738528, 1743308384,
+ 1388022681, 1760110496,
+ 1664028066, 654300326,
+ 1767741172, 1338181197,
+ 1625723550, 1742482745,
+ 464486085, 1507852127,
+ 754082421, 1187454014,
+ 1315342834, 425995190,
+ 960416608, 2004255418,
+ 1262630671, 671761697,
+ 59809238, 103525918,
+ 1205644919, 2107823293,
+ 1615183160, 1152411412,
+ 1024474681, 2118672937,
+ 1703877649, 1235091369,
+ 1821417852, 1098463802,
+ 1738806466, 1529062843,
+ 620780646, 1654833544,
+ 1070174101, 795158254,
+ 658537995, 1693620426,
+ 2055317555, 508053916,
+ 1647371686, 1282395762,
+ 29067379, 409683067,
+ 1763495989, 1917939635,
+ 1602690753, 810926582,
+ 885787576, 513818500,
+ 1853512561, 1195205756,
+ 1798585498, 1970460256,
+ 1819261032, 1306536501,
+ 1133245275, 37901,
+ 689459799, 1334389069,
+ 1730609912, 1854586207,
+ 1556832175, 1228729041,
+ 251375753, 683687209,
+ 2083946182, 1763106152,
+ 2142981854, 1365385561,
+ 763711891, 1735754548,
+ 1581256466, 173689858,
+ 2121337132, 1247108250,
+ 1004003636, 891894307,
+ 569816524, 358675254,
+ 626626425, 116062841,
+ 632086003, 861268491,
+ 1008211580, 779404957,
+ 1134217766, 1766838261,
+ 1423829292, 1706666192,
+ 942037869, 1549358884,
+ 1959429535, 480779114,
+ 778311037, 1940360875,
+ 1531372185, 2009078158,
+ 241935492, 1050047003,
+ 272453504, 1870883868,
+ 390441332, 1057903098,
+ 1230238834, 1548117688,
+ 1242956379, 1217296445,
+ 515648357, 1675011378,
+ 364477932, 355212934,
+ 2096008713, 1570161804,
+ 1409752526, 214033983,
+ 1288158292, 1760636178,
+ 407562666, 1265144848,
+ 1071056491, 1582316946,
+ 1014143949, 911406955,
+ 203080461, 809380052,
+ 125647866, 1705464126,
+ 2015685843, 599230667,
+ 1425476020, 668203729,
+ 1673735652, 567931803,
+ 1714199325, 181737617,
+ 1389137652, 678147926,
+ 288547803, 435433694,
+ 200159281, 654399753,
+ 1580828223, 1298308945,
+ 1832286107, 169991953,
+ 182557704, 1046541065,
+ 1688025575, 1248944426,
+ 1508287706, 1220577001,
+ 36721212, 1377275347,
+ 1968679856, 1675229747,
+ 279109231, 1835333261,
+ 1358617667, 1416978076,
+ 740626186, 2103913602,
+ 1882655908, 251341858,
+ 648016670, 1459615287,
+ 780255321, 154906988,
+ 857296483, 203375965,
+ 1631676846, 681204578,
+ 1906971307, 1623728832,
+ 1541899600, 1168449797,
+ 1267051693, 1020078717,
+ 1998673940, 1298394942,
+ 1914117058, 1381290704,
+ 426068513, 1381618498,
+ 139365577, 1598767734,
+ 2129910384, 952266588,
+ 661788054, 19661356,
+ 1104640222, 240506063,
+ 356133630, 1676634527,
+ 242242374, 1863206182,
+ 957935844, 1490681416 };
/**
* Makes this class non instantiable, but still let's others inherit from it.
*/
protected RandomSeedTable() {
- throw new RuntimeException("Non instantiable");
+ throw new RuntimeException("Non instantiable");
}
/**
* Returns a deterministic seed from a (seemingly gigantic) matrix of predefined seeds.
@@ -261,27 +259,27 @@
* @return the seed at the indicated matrix position.
*/
public static int getSeedAtRowColumn(int row, int column) {
- // the table is limited; let's snap the unbounded input parameters to the table's actual size.
- int rows = rows();
-
- int theRow = Math.abs(row % rows);
- int theColumn = Math.abs(column % COLUMNS);
-
- int seed = seeds[theRow*COLUMNS + theColumn];
-
- // "randomize" the seed (in some ways comparable to hash functions)
- int cycle = Math.abs(row / rows);
- int mask = (( cycle & 0x000007ff ) << 20 ); // cycle==0 --> mask = 0
- seed = seed ^ mask; // cycle==0 --> seed stays unaffected
- // now, each sequence has a period of 10**9 numbers.
-
- return seed;
+ // the table is limited; let's snap the unbounded input parameters to the table's actual size.
+ int rows = rows();
+
+ int theRow = Math.abs(row % rows);
+ int theColumn = Math.abs(column % COLUMNS);
+
+ int seed = seeds[theRow*COLUMNS + theColumn];
+
+ // "randomize" the seed (in some ways comparable to hash functions)
+ int cycle = Math.abs(row / rows);
+ int mask = (( cycle & 0x000007ff ) << 20 ); // cycle==0 --> mask = 0
+ seed = seed ^ mask; // cycle==0 --> seed stays unaffected
+ // now, each sequence has a period of 10**9 numbers.
+
+ return seed;
}
/**
* Not yet commented.
* @return int
*/
private static int rows() {
- return seeds.length/COLUMNS;
+ return seeds.length/COLUMNS;
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/package.html
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/package.html?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/package.html (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/package.html Wed Nov 25 03:31:47 2009
@@ -15,14 +15,14 @@
double lambda = 1 / (variance / mean);
// for tests and debugging use a random engine with CONSTANT seed --> deterministic and reproducible results
-cern.jet.random.engine.RandomEngine engine = new cern.jet.random.engine.MersenneTwister();
+org.apache.mahout.jet.random.engine.RandomEngine engine = new org.apache.mahout.jet.random.engine.MersenneTwister();
// your favourite distribution goes here
-cern.jet.random.AbstractDistribution dist = new cern.jet.random.Gamma(alpha,lambda,engine);
+org.apache.mahout.jet.random.AbstractDistribution dist = new org.apache.mahout.jet.random.Gamma(alpha,lambda,engine);
// collect random numbers and print statistics
int size = 100000;
-cern.colt.list.DoubleArrayList numbers = new cern.colt.list.DoubleArrayList(size);
+org.apache.mahout.matrix.list.DoubleArrayList numbers = new org.apache.mahout.matrix.list.DoubleArrayList(size);
for (int i=0; i < size; i++) numbers.add(dist.nextDouble());
hep.aida.bin.DynamicBin1D bin = new hep.aida.bin.DynamicBin1D();
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSampler.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSampler.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSampler.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSampler.java Wed Nov 25 03:31:47 2009
@@ -103,8 +103,6 @@
* Paper available <A HREF="http://www.cs.duke.edu/~jsv"> here</A>.
*
* @see RandomSamplingAssistant
- * @author wolfgang.hoschek@cern.ch
- * @version 1.1 05/26/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
@@ -112,11 +110,11 @@
@Deprecated
public class RandomSampler extends org.apache.mahout.matrix.PersistentObject {
//public class RandomSampler extends Object implements java.io.Serializable {
- long my_n;
- long my_N;
- long my_low;
- RandomEngine my_RandomGenerator;
- //static long negalphainv; // just to determine once and for all the best value for negalphainv
+ long my_n;
+ long my_N;
+ long my_low;
+ RandomEngine my_RandomGenerator;
+ //static long negalphainv; // just to determine once and for all the best value for negalphainv
/**
* Constructs a random sampler that computes and delivers sorted random sets in blocks.
* A set block can be retrieved with method <tt>nextBlock</tt>.
@@ -128,35 +126,35 @@
* @param randomGenerator a random number generator. Set this parameter to <tt>null</tt> to use the default random number generator.
*/
public RandomSampler(long n, long N, long low, RandomEngine randomGenerator) {
- if (n<0) throw new IllegalArgumentException("n must be >= 0");
- if (n>N) throw new IllegalArgumentException("n must by <= N");
- this.my_n=n;
- this.my_N=N;
- this.my_low=low;
+ if (n<0) throw new IllegalArgumentException("n must be >= 0");
+ if (n>N) throw new IllegalArgumentException("n must by <= N");
+ this.my_n=n;
+ this.my_N=N;
+ this.my_low=low;
- if (randomGenerator==null) randomGenerator = org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator();
- this.my_RandomGenerator=randomGenerator;
+ if (randomGenerator==null) randomGenerator = org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator();
+ this.my_RandomGenerator=randomGenerator;
}
/**
* Returns a deep copy of the receiver.
*/
public Object clone() {
- RandomSampler copy = (RandomSampler) super.clone();
- copy.my_RandomGenerator = (RandomEngine) this.my_RandomGenerator.clone();
- return copy;
+ RandomSampler copy = (RandomSampler) super.clone();
+ copy.my_RandomGenerator = (RandomEngine) this.my_RandomGenerator.clone();
+ return copy;
}
/**
* Tests this class.
*/
public static void main(String args[]) {
- long n = Long.parseLong(args[0]);
- long N = Long.parseLong(args[1]);
- long low = Long.parseLong(args[2]);
- int chunkSize = Integer.parseInt(args[3]);
- int times = Integer.parseInt(args[4]);
+ long n = Long.parseLong(args[0]);
+ long N = Long.parseLong(args[1]);
+ long low = Long.parseLong(args[2]);
+ int chunkSize = Integer.parseInt(args[3]);
+ int times = Integer.parseInt(args[4]);
- test(n,N,low,chunkSize,times);
- //testNegAlphaInv(args);
+ test(n,N,low,chunkSize,times);
+ //testNegAlphaInv(args);
}
/**
* Computes the next <tt>count</tt> random numbers of the sorted random set specified on instance construction
@@ -170,17 +168,17 @@
* @param fromIndex the first index within <tt>values</tt> to be filled with numbers (inclusive).
*/
public void nextBlock(int count, long[] values, int fromIndex) {
- if (count > my_n) throw new IllegalArgumentException("Random sample exhausted.");
- if (count < 0) throw new IllegalArgumentException("Negative count.");
+ if (count > my_n) throw new IllegalArgumentException("Random sample exhausted.");
+ if (count < 0) throw new IllegalArgumentException("Negative count.");
- if (count==0) return; //nothing to do
+ if (count==0) return; //nothing to do
- sample(my_n,my_N,count,my_low,values,fromIndex,my_RandomGenerator);
-
- long lastSample=values[fromIndex+count-1];
- my_n -= count;
- my_N = my_N - lastSample - 1 + my_low ;
- my_low = lastSample+1;
+ sample(my_n,my_N,count,my_low,values,fromIndex,my_RandomGenerator);
+
+ long lastSample=values[fromIndex+count-1];
+ my_n -= count;
+ my_N = my_N - lastSample - 1 + my_low ;
+ my_low = lastSample+1;
}
/**
* Efficiently computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>.
@@ -200,96 +198,96 @@
* @param randomGenerator a random number generator.
*/
protected static void rejectMethodD(long n, long N, int count, long low, long[] values, int fromIndex, RandomEngine randomGenerator) {
- /* This algorithm is applicable if a large percentage (90%..100%) of N shall be sampled.
- In such cases it is more efficient than sampleMethodA() and sampleMethodD().
- The idea is that it is more efficient to express
- sample(n,N,count) in terms of reject(N-n,N,count)
- and then invert the result.
- For example, sampling 99% turns into sampling 1% plus inversion.
-
- This algorithm is the same as method sampleMethodD(...) with the exception that sampled elements are rejected, and not sampled elements included in the result set.
- */
- n = N-n; // IMPORTANT !!!
-
- double nreal, Nreal, ninv, nmin1inv, U, X, Vprime, y1, y2, top, bottom, negSreal, qu1real;
- long qu1, t, limit;
- //long threshold;
- long S;
- long chosen = -1+low;
-
- long negalphainv = -13; //tuning paramter, determines when to switch from method D to method A. Dependent on programming language, platform, etc.
-
- nreal = n; ninv = 1.0/nreal; Nreal = N;
- Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
- qu1 = -n + 1 + N; qu1real = -nreal + 1.0 + Nreal;
- //threshold = -negalphainv * n;
-
- while (n>1 && count>0) { //&& threshold<N) {
- nmin1inv = 1.0/(-1.0 + nreal);
- for (;;) {
- for (;;) { // step D2: generate U and X
- X = Nreal * (-Vprime + 1.0); S = (long) X;
- if (S<qu1) break;
- Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
- }
- U = randomGenerator.raw(); negSreal = -S;
-
- //step D3: Accept?
- y1 = Math.exp(Math.log(U*Nreal/qu1real) * nmin1inv);
- Vprime = y1*(-X/Nreal + 1.0) * (qu1real/(negSreal + qu1real));
- if (Vprime <= 1.0) break; //break inner loop
-
- //step D4: Accept?
- y2 = 1.0; top = -1.0 + Nreal;
- if (n-1>S) {
- bottom = -nreal + Nreal; limit = -S+N;
- }
- else {
- bottom = -1.0 + negSreal + Nreal; limit=qu1;
- }
- for (t=N-1; t>=limit; t--) {
- y2 = (y2*top)/bottom;
- top--;
- bottom--;
- }
- if (Nreal/(-X+Nreal) >= y1*Math.exp(Math.log(y2)*nmin1inv)) {
- // accept !
- Vprime = Math.exp(Math.log(randomGenerator.raw())*nmin1inv);
- break; //break inner loop
- }
- Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
- } //end for
-
- //step D5: reject the (S+1)st record !
- int iter = count; //int iter = (int) (Math.min(S,count));
- if (S<iter) iter=(int)S;
-
- count -= iter;
- for (; --iter >= 0 ;) values[fromIndex++] = ++chosen;
- chosen++;
-
- N -= S+1; Nreal=negSreal+(-1.0+Nreal);
- n--; nreal--; ninv = nmin1inv;
- qu1 = -S+qu1; qu1real = negSreal+qu1real;
- //threshold += negalphainv;
- } //end while
-
-
- if (count>0) { //special case n==1
- //reject the (S+1)st record !
- S = (long) (N*Vprime);
-
- int iter = count; //int iter = (int) (Math.min(S,count));
- if (S<iter) iter=(int)S;
-
- count -= iter;
- for (; --iter >= 0 ;) values[fromIndex++] = ++chosen;
-
- chosen++;
-
- // fill the rest
- for (; --count >= 0; ) values[fromIndex++] = ++chosen;
- }
+ /* This algorithm is applicable if a large percentage (90%..100%) of N shall be sampled.
+ In such cases it is more efficient than sampleMethodA() and sampleMethodD().
+ The idea is that it is more efficient to express
+ sample(n,N,count) in terms of reject(N-n,N,count)
+ and then invert the result.
+ For example, sampling 99% turns into sampling 1% plus inversion.
+
+ This algorithm is the same as method sampleMethodD(...) with the exception that sampled elements are rejected, and not sampled elements included in the result set.
+ */
+ n = N-n; // IMPORTANT !!!
+
+ double nreal, Nreal, ninv, nmin1inv, U, X, Vprime, y1, y2, top, bottom, negSreal, qu1real;
+ long qu1, t, limit;
+ //long threshold;
+ long S;
+ long chosen = -1+low;
+
+ long negalphainv = -13; //tuning paramter, determines when to switch from method D to method A. Dependent on programming language, platform, etc.
+
+ nreal = n; ninv = 1.0/nreal; Nreal = N;
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
+ qu1 = -n + 1 + N; qu1real = -nreal + 1.0 + Nreal;
+ //threshold = -negalphainv * n;
+
+ while (n>1 && count>0) { //&& threshold<N) {
+ nmin1inv = 1.0/(-1.0 + nreal);
+ for (;;) {
+ for (;;) { // step D2: generate U and X
+ X = Nreal * (-Vprime + 1.0); S = (long) X;
+ if (S<qu1) break;
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
+ }
+ U = randomGenerator.raw(); negSreal = -S;
+
+ //step D3: Accept?
+ y1 = Math.exp(Math.log(U*Nreal/qu1real) * nmin1inv);
+ Vprime = y1*(-X/Nreal + 1.0) * (qu1real/(negSreal + qu1real));
+ if (Vprime <= 1.0) break; //break inner loop
+
+ //step D4: Accept?
+ y2 = 1.0; top = -1.0 + Nreal;
+ if (n-1>S) {
+ bottom = -nreal + Nreal; limit = -S+N;
+ }
+ else {
+ bottom = -1.0 + negSreal + Nreal; limit=qu1;
+ }
+ for (t=N-1; t>=limit; t--) {
+ y2 = (y2*top)/bottom;
+ top--;
+ bottom--;
+ }
+ if (Nreal/(-X+Nreal) >= y1*Math.exp(Math.log(y2)*nmin1inv)) {
+ // accept !
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*nmin1inv);
+ break; //break inner loop
+ }
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
+ } //end for
+
+ //step D5: reject the (S+1)st record !
+ int iter = count; //int iter = (int) (Math.min(S,count));
+ if (S<iter) iter=(int)S;
+
+ count -= iter;
+ for (; --iter >= 0 ;) values[fromIndex++] = ++chosen;
+ chosen++;
+
+ N -= S+1; Nreal=negSreal+(-1.0+Nreal);
+ n--; nreal--; ninv = nmin1inv;
+ qu1 = -S+qu1; qu1real = negSreal+qu1real;
+ //threshold += negalphainv;
+ } //end while
+
+
+ if (count>0) { //special case n==1
+ //reject the (S+1)st record !
+ S = (long) (N*Vprime);
+
+ int iter = count; //int iter = (int) (Math.min(S,count));
+ if (S<iter) iter=(int)S;
+
+ count -= iter;
+ for (; --iter >= 0 ;) values[fromIndex++] = ++chosen;
+
+ chosen++;
+
+ // fill the rest
+ for (; --count >= 0; ) values[fromIndex++] = ++chosen;
+ }
}
/**
* Efficiently computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>.
@@ -313,25 +311,25 @@
* @param randomGenerator a random number generator. Set this parameter to <tt>null</tt> to use the default random number generator.
*/
public static void sample(long n, long N, int count, long low, long[] values, int fromIndex, RandomEngine randomGenerator) {
- if (n<=0 || count<=0) return;
- if (count>n) throw new IllegalArgumentException("count must not be greater than n");
- if (randomGenerator==null) randomGenerator = org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator();
-
- if (count==N) { // rare case treated quickly
- long val = low;
- int limit= fromIndex+count;
- for (int i=fromIndex; i<limit; ) values[i++] = val++;
- return;
- }
-
- if (n<N*0.95) { // || Math.min(count,N-n)>maxTmpMemoryAllowed) {
- sampleMethodD(n,N,count,low,values,fromIndex,randomGenerator);
- }
- else { // More than 95% of all numbers shall be sampled.
- rejectMethodD(n,N,count,low,values,fromIndex,randomGenerator);
- }
-
-
+ if (n<=0 || count<=0) return;
+ if (count>n) throw new IllegalArgumentException("count must not be greater than n");
+ if (randomGenerator==null) randomGenerator = org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator();
+
+ if (count==N) { // rare case treated quickly
+ long val = low;
+ int limit= fromIndex+count;
+ for (int i=fromIndex; i<limit; ) values[i++] = val++;
+ return;
+ }
+
+ if (n<N*0.95) { // || Math.min(count,N-n)>maxTmpMemoryAllowed) {
+ sampleMethodD(n,N,count,low,values,fromIndex,randomGenerator);
+ }
+ else { // More than 95% of all numbers shall be sampled.
+ rejectMethodD(n,N,count,low,values,fromIndex,randomGenerator);
+ }
+
+
}
/**
* Computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>.
@@ -351,35 +349,35 @@
* @param randomGenerator a random number generator.
*/
protected static void sampleMethodA(long n, long N, int count, long low, long[] values, int fromIndex, RandomEngine randomGenerator) {
- double V, quot, Nreal, top;
- long S;
- long chosen = -1+low;
-
- top = N-n;
- Nreal = N;
- while (n>=2 && count>0) {
- V = randomGenerator.raw();
- S = 0;
- quot = top/Nreal;
- while (quot > V) {
- S++;
- top--;
- Nreal--;
- quot = (quot*top)/Nreal;
- }
- chosen += S+1;
- values[fromIndex++]=chosen;
- count--;
- Nreal--;
- n--;
- }
-
- if (count>0) {
- // special case n==1
- S = (long) (Math.round(Nreal) * randomGenerator.raw());
- chosen += S+1;
- values[fromIndex]=chosen;
- }
+ double V, quot, Nreal, top;
+ long S;
+ long chosen = -1+low;
+
+ top = N-n;
+ Nreal = N;
+ while (n>=2 && count>0) {
+ V = randomGenerator.raw();
+ S = 0;
+ quot = top/Nreal;
+ while (quot > V) {
+ S++;
+ top--;
+ Nreal--;
+ quot = (quot*top)/Nreal;
+ }
+ chosen += S+1;
+ values[fromIndex++]=chosen;
+ count--;
+ Nreal--;
+ n--;
+ }
+
+ if (count>0) {
+ // special case n==1
+ S = (long) (Math.round(Nreal) * randomGenerator.raw());
+ chosen += S+1;
+ values[fromIndex]=chosen;
+ }
}
/**
* Efficiently computes a sorted random set of <tt>count</tt> elements from the interval <tt>[low,low+N-1]</tt>.
@@ -399,162 +397,162 @@
* @param randomGenerator a random number generator.
*/
protected static void sampleMethodD(long n, long N, int count, long low, long[] values, int fromIndex, RandomEngine randomGenerator) {
- double nreal, Nreal, ninv, nmin1inv, U, X, Vprime, y1, y2, top, bottom, negSreal, qu1real;
- long qu1, threshold, t, limit;
- long S;
- long chosen = -1+low;
-
- long negalphainv = -13; //tuning paramter, determines when to switch from method D to method A. Dependent on programming language, platform, etc.
-
- nreal = n; ninv = 1.0/nreal; Nreal = N;
- Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
- qu1 = -n + 1 + N; qu1real = -nreal + 1.0 + Nreal;
- threshold = -negalphainv * n;
-
- while (n>1 && count>0 && threshold<N) {
- nmin1inv = 1.0/(-1.0 + nreal);
- for (;;) {
- for (;;) { // step D2: generate U and X
- X = Nreal * (-Vprime + 1.0); S = (long) X;
- if (S<qu1) break;
- Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
- }
- U = randomGenerator.raw(); negSreal = -S;
-
- //step D3: Accept?
- y1 = Math.exp(Math.log(U*Nreal/qu1real) * nmin1inv);
- Vprime = y1*(-X/Nreal + 1.0) * (qu1real/(negSreal + qu1real));
- if (Vprime <= 1.0) break; //break inner loop
-
- //step D4: Accept?
- y2 = 1.0; top = -1.0 + Nreal;
- if (n-1>S) {
- bottom = -nreal + Nreal; limit = -S+N;
- }
- else {
- bottom = -1.0 + negSreal + Nreal; limit=qu1;
- }
- for (t=N-1; t>=limit; t--) {
- y2 = (y2*top)/bottom;
- top--;
- bottom--;
- }
- if (Nreal/(-X+Nreal) >= y1*Math.exp(Math.log(y2)*nmin1inv)) {
- // accept !
- Vprime = Math.exp(Math.log(randomGenerator.raw())*nmin1inv);
- break; //break inner loop
- }
- Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
- } //end for
-
- //step D5: select the (S+1)st record !
- chosen += S+1;
- values[fromIndex++] = chosen;
- /*
- // invert
- for (int iter=0; iter<S && count > 0; iter++) {
- values[fromIndex++] = ++chosen;
- count--;
- }
- chosen++;
- */
- count--;
-
- N -= S+1; Nreal=negSreal+(-1.0+Nreal);
- n--; nreal--; ninv = nmin1inv;
- qu1 = -S+qu1; qu1real = negSreal+qu1real;
- threshold += negalphainv;
- } //end while
-
-
- if (count>0) {
- if (n>1) { //faster to use method A to finish the sampling
- sampleMethodA(n,N,count,chosen+1,values,fromIndex,randomGenerator);
- }
- else {
- //special case n==1
- S = (long) (N*Vprime);
- chosen += S+1;
- values[fromIndex++] = chosen;
- }
- }
+ double nreal, Nreal, ninv, nmin1inv, U, X, Vprime, y1, y2, top, bottom, negSreal, qu1real;
+ long qu1, threshold, t, limit;
+ long S;
+ long chosen = -1+low;
+
+ long negalphainv = -13; //tuning paramter, determines when to switch from method D to method A. Dependent on programming language, platform, etc.
+
+ nreal = n; ninv = 1.0/nreal; Nreal = N;
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
+ qu1 = -n + 1 + N; qu1real = -nreal + 1.0 + Nreal;
+ threshold = -negalphainv * n;
+
+ while (n>1 && count>0 && threshold<N) {
+ nmin1inv = 1.0/(-1.0 + nreal);
+ for (;;) {
+ for (;;) { // step D2: generate U and X
+ X = Nreal * (-Vprime + 1.0); S = (long) X;
+ if (S<qu1) break;
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
+ }
+ U = randomGenerator.raw(); negSreal = -S;
+
+ //step D3: Accept?
+ y1 = Math.exp(Math.log(U*Nreal/qu1real) * nmin1inv);
+ Vprime = y1*(-X/Nreal + 1.0) * (qu1real/(negSreal + qu1real));
+ if (Vprime <= 1.0) break; //break inner loop
+
+ //step D4: Accept?
+ y2 = 1.0; top = -1.0 + Nreal;
+ if (n-1>S) {
+ bottom = -nreal + Nreal; limit = -S+N;
+ }
+ else {
+ bottom = -1.0 + negSreal + Nreal; limit=qu1;
+ }
+ for (t=N-1; t>=limit; t--) {
+ y2 = (y2*top)/bottom;
+ top--;
+ bottom--;
+ }
+ if (Nreal/(-X+Nreal) >= y1*Math.exp(Math.log(y2)*nmin1inv)) {
+ // accept !
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*nmin1inv);
+ break; //break inner loop
+ }
+ Vprime = Math.exp(Math.log(randomGenerator.raw())*ninv);
+ } //end for
+
+ //step D5: select the (S+1)st record !
+ chosen += S+1;
+ values[fromIndex++] = chosen;
+ /*
+ // invert
+ for (int iter=0; iter<S && count > 0; iter++) {
+ values[fromIndex++] = ++chosen;
+ count--;
+ }
+ chosen++;
+ */
+ count--;
+
+ N -= S+1; Nreal=negSreal+(-1.0+Nreal);
+ n--; nreal--; ninv = nmin1inv;
+ qu1 = -S+qu1; qu1real = negSreal+qu1real;
+ threshold += negalphainv;
+ } //end while
+
+
+ if (count>0) {
+ if (n>1) { //faster to use method A to finish the sampling
+ sampleMethodA(n,N,count,chosen+1,values,fromIndex,randomGenerator);
+ }
+ else {
+ //special case n==1
+ S = (long) (N*Vprime);
+ chosen += S+1;
+ values[fromIndex++] = chosen;
+ }
+ }
}
/**
* Tests the methods of this class.
* To do benchmarking, comment the lines printing stuff to the console.
*/
public static void test(long n, long N, long low, int chunkSize, int times) {
- long[] values = new long[chunkSize];
- long chunks = n/chunkSize;
-
- org.apache.mahout.matrix.Timer timer = new org.apache.mahout.matrix.Timer().start();
- for (long t=times; --t >=0;) {
- RandomSampler sampler = new RandomSampler(n,N,low, org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator());
- for (long i=0; i<chunks; i++) {
- sampler.nextBlock(chunkSize,values,0);
-
- /*
- Log.print("Chunk #"+i+" = [");
- for (int j=0; j<chunkSize-1; j++) Log.print(values[j]+", ");
- Log.print(String.valueOf(values[chunkSize-1]));
- Log.println("]");
- */
-
- }
-
- int toDo=(int) (n-chunkSize*chunks);
- if (toDo > 0) { // sample remaining part, if necessary
- sampler.nextBlock(toDo,values,0);
-
- /*
- Log.print("Chunk #"+chunks+" = [");
- for (int j=0; j<toDo-1; j++) Log.print(values[j]+", ");
- Log.print(String.valueOf(values[toDo-1]));
- Log.println("]");
- */
-
-
- }
- }
- timer.stop();
- System.out.println("single run took "+timer.elapsedTime()/times);
- System.out.println("Good bye.\n");
+ long[] values = new long[chunkSize];
+ long chunks = n/chunkSize;
+
+ org.apache.mahout.matrix.Timer timer = new org.apache.mahout.matrix.Timer().start();
+ for (long t=times; --t >=0;) {
+ RandomSampler sampler = new RandomSampler(n,N,low, org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator());
+ for (long i=0; i<chunks; i++) {
+ sampler.nextBlock(chunkSize,values,0);
+
+ /*
+ Log.print("Chunk #"+i+" = [");
+ for (int j=0; j<chunkSize-1; j++) Log.print(values[j]+", ");
+ Log.print(String.valueOf(values[chunkSize-1]));
+ Log.println("]");
+ */
+
+ }
+
+ int toDo=(int) (n-chunkSize*chunks);
+ if (toDo > 0) { // sample remaining part, if necessary
+ sampler.nextBlock(toDo,values,0);
+
+ /*
+ Log.print("Chunk #"+chunks+" = [");
+ for (int j=0; j<toDo-1; j++) Log.print(values[j]+", ");
+ Log.print(String.valueOf(values[toDo-1]));
+ Log.println("]");
+ */
+
+
+ }
+ }
+ timer.stop();
+ System.out.println("single run took "+timer.elapsedTime()/times);
+ System.out.println("Good bye.\n");
}
/**
* Tests different values for negaalphainv.
* Result: J.S. Vitter's recommendation for negalphainv=-13 is also good in the JDK 1.2 environment.
*/
protected static void testNegAlphaInv(String args[]) {
- /*
- long N = Long.parseLong(args[0]);
- int chunkSize = Integer.parseInt(args[1]);
+ /*
+ long N = Long.parseLong(args[0]);
+ int chunkSize = Integer.parseInt(args[1]);
- long[] alphas = {-104, -52, -26, -13, -8, -4, -2};
- for (int i=0; i<alphas.length; i++) {
- negalphainv = alphas[i];
- System.out.println("\n\nnegalphainv="+negalphainv);
+ long[] alphas = {-104, -52, -26, -13, -8, -4, -2};
+ for (int i=0; i<alphas.length; i++) {
+ negalphainv = alphas[i];
+ System.out.println("\n\nnegalphainv="+negalphainv);
- System.out.print(" n="+N/80+" --> ");
- test(N/80,N,0,chunkSize);
+ System.out.print(" n="+N/80+" --> ");
+ test(N/80,N,0,chunkSize);
- System.out.print(" n="+N/40+" --> ");
- test(N/40,N,0,chunkSize);
+ System.out.print(" n="+N/40+" --> ");
+ test(N/40,N,0,chunkSize);
- System.out.print(" n="+N/20+" --> ");
- test(N/20,N,0,chunkSize);
+ System.out.print(" n="+N/20+" --> ");
+ test(N/20,N,0,chunkSize);
- System.out.print(" n="+N/10+" --> ");
- test(N/10,N,0,chunkSize);
+ System.out.print(" n="+N/10+" --> ");
+ test(N/10,N,0,chunkSize);
- System.out.print(" n="+N/5+" --> ");
- test(N/5,N,0,chunkSize);
+ System.out.print(" n="+N/5+" --> ");
+ test(N/5,N,0,chunkSize);
- System.out.print(" n="+N/2+" --> ");
- test(N/2,N,0,chunkSize);
+ System.out.print(" n="+N/2+" --> ");
+ test(N/2,N,0,chunkSize);
- System.out.print(" n="+(N-3)+" --> ");
- test(N-3,N,0,chunkSize);
- }
- */
+ System.out.print(" n="+(N-3)+" --> ");
+ test(N-3,N,0,chunkSize);
+ }
+ */
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSamplingAssistant.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSamplingAssistant.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSamplingAssistant.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/RandomSamplingAssistant.java Wed Nov 25 03:31:47 2009
@@ -18,8 +18,6 @@
* This class is a convenience adapter for <tt>RandomSampler</tt> using blocks.
*
* @see RandomSampler
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 02/05/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
@@ -27,14 +25,14 @@
@Deprecated
public class RandomSamplingAssistant extends org.apache.mahout.matrix.PersistentObject {
//public class RandomSamplingAssistant extends Object implements java.io.Serializable {
- protected RandomSampler sampler;
- protected long[] buffer;
- protected int bufferPosition;
+ protected RandomSampler sampler;
+ protected long[] buffer;
+ protected int bufferPosition;
- protected long skip;
- protected long n;
+ protected long skip;
+ protected long n;
- static final int MAX_BUFFER_SIZE = 200;
+ static final int MAX_BUFFER_SIZE = 200;
/**
* Constructs a random sampler that samples <tt>n</tt> random elements from an input sequence of <tt>N</tt> elements.
*
@@ -43,129 +41,129 @@
* @param randomGenerator a random number generator. Set this parameter to <tt>null</tt> to use the default random number generator.
*/
public RandomSamplingAssistant(long n, long N, RandomEngine randomGenerator) {
- this.n = n;
- this.sampler = new RandomSampler(n, N, 0, randomGenerator);
- this.buffer = new long[(int)Math.min(n,MAX_BUFFER_SIZE)];
- if (n>0) this.buffer[0] = -1; // start with the right offset
-
- fetchNextBlock();
+ this.n = n;
+ this.sampler = new RandomSampler(n, N, 0, randomGenerator);
+ this.buffer = new long[(int)Math.min(n,MAX_BUFFER_SIZE)];
+ if (n>0) this.buffer[0] = -1; // start with the right offset
+
+ fetchNextBlock();
}
/**
* Returns a deep copy of the receiver.
*/
public Object clone() {
- RandomSamplingAssistant copy = (RandomSamplingAssistant) super.clone();
- copy.sampler = (RandomSampler) this.sampler.clone();
- return copy;
+ RandomSamplingAssistant copy = (RandomSamplingAssistant) super.clone();
+ copy.sampler = (RandomSampler) this.sampler.clone();
+ return copy;
}
/**
* Not yet commented.
*/
protected void fetchNextBlock() {
- if (n>0) {
- long last = buffer[bufferPosition];
- sampler.nextBlock((int)Math.min(n,MAX_BUFFER_SIZE), buffer, 0);
- skip = buffer[0] - last - 1;
- bufferPosition=0;
- }
+ if (n>0) {
+ long last = buffer[bufferPosition];
+ sampler.nextBlock((int)Math.min(n,MAX_BUFFER_SIZE), buffer, 0);
+ skip = buffer[0] - last - 1;
+ bufferPosition=0;
+ }
}
/**
* Returns the used random generator.
*/
public RandomEngine getRandomGenerator() {
- return this.sampler.my_RandomGenerator;
+ return this.sampler.my_RandomGenerator;
}
/**
* Tests random sampling.
*/
public static void main(String args[]) {
- long n = Long.parseLong(args[0]);
- long N = Long.parseLong(args[1]);
- //test(n,N);
- testArraySampling((int)n,(int)N);
+ long n = Long.parseLong(args[0]);
+ long N = Long.parseLong(args[1]);
+ //test(n,N);
+ testArraySampling((int)n,(int)N);
}
/**
* Just shows how this class can be used; samples n elements from and int[] array.
*/
public static int[] sampleArray(int n, int[] elements) {
- RandomSamplingAssistant assistant = new RandomSamplingAssistant(n, elements.length, null);
- int[] sample = new int[n];
- int j=0;
- int length = elements.length;
- for (int i=0; i<length; i++) {
- if (assistant.sampleNextElement()) sample[j++] = elements[i];
- }
- return sample;
+ RandomSamplingAssistant assistant = new RandomSamplingAssistant(n, elements.length, null);
+ int[] sample = new int[n];
+ int j=0;
+ int length = elements.length;
+ for (int i=0; i<length; i++) {
+ if (assistant.sampleNextElement()) sample[j++] = elements[i];
+ }
+ return sample;
}
/**
* Returns whether the next element of the input sequence shall be sampled (picked) or not.
* @return <tt>true</tt> if the next element shall be sampled (picked), <tt>false</tt> otherwise.
*/
public boolean sampleNextElement() {
- if (n==0) return false; //reject
- if (skip-- > 0) return false; //reject
+ if (n==0) return false; //reject
+ if (skip-- > 0) return false; //reject
- //accept
- n--;
- if (bufferPosition < buffer.length-1) {
- skip = buffer[bufferPosition+1] - buffer[bufferPosition++];
- --skip;
- }
- else {
- fetchNextBlock();
- }
-
- return true;
+ //accept
+ n--;
+ if (bufferPosition < buffer.length-1) {
+ skip = buffer[bufferPosition+1] - buffer[bufferPosition++];
+ --skip;
+ }
+ else {
+ fetchNextBlock();
+ }
+
+ return true;
}
/**
* Tests the methods of this class.
* To do benchmarking, comment the lines printing stuff to the console.
*/
public static void test(long n, long N) {
- RandomSamplingAssistant assistant = new RandomSamplingAssistant(n,N,null);
+ RandomSamplingAssistant assistant = new RandomSamplingAssistant(n,N,null);
- org.apache.mahout.matrix.list.LongArrayList sample = new org.apache.mahout.matrix.list.LongArrayList((int)n);
- org.apache.mahout.matrix.Timer timer = new org.apache.mahout.matrix.Timer().start();
+ org.apache.mahout.matrix.list.LongArrayList sample = new org.apache.mahout.matrix.list.LongArrayList((int)n);
+ org.apache.mahout.matrix.Timer timer = new org.apache.mahout.matrix.Timer().start();
- for (long i=0; i<N; i++) {
- if (assistant.sampleNextElement()) {
- sample.add(i);
- }
-
- }
-
- timer.stop().display();
- System.out.println("sample="+sample);
- System.out.println("Good bye.\n");
+ for (long i=0; i<N; i++) {
+ if (assistant.sampleNextElement()) {
+ sample.add(i);
+ }
+
+ }
+
+ timer.stop().display();
+ System.out.println("sample="+sample);
+ System.out.println("Good bye.\n");
}
/**
* Tests the methods of this class.
* To do benchmarking, comment the lines printing stuff to the console.
*/
public static void testArraySampling(int n, int N) {
- int[] elements = new int[N];
- for (int i=0; i<N; i++) elements[i]=i;
+ int[] elements = new int[N];
+ for (int i=0; i<N; i++) elements[i]=i;
- org.apache.mahout.matrix.Timer timer = new org.apache.mahout.matrix.Timer().start();
+ org.apache.mahout.matrix.Timer timer = new org.apache.mahout.matrix.Timer().start();
- int[] sample = sampleArray(n, elements);
+ int[] sample = sampleArray(n, elements);
- timer.stop().display();
+ timer.stop().display();
- /*
- System.out.print("\nElements = [");
- for (int i=0; i<N-1; i++) System.out.print(elements[i]+", ");
- System.out.print(elements[N-1]);
- System.out.println("]");
+ /*
+ System.out.print("\nElements = [");
+ for (int i=0; i<N-1; i++) System.out.print(elements[i]+", ");
+ System.out.print(elements[N-1]);
+ System.out.println("]");
- System.out.print("\nSample = [");
- for (int i=0; i<n-1; i++) System.out.print(sample[i]+", ");
- System.out.print(sample[n-1]);
- System.out.println("]");
- */
+ System.out.print("\nSample = [");
+ for (int i=0; i<n-1; i++) System.out.print(sample[i]+", ");
+ System.out.print(sample[n-1]);
+ System.out.println("]");
+ */
- System.out.println("Good bye.\n");
+ System.out.println("Good bye.\n");
}
/**
* Returns whether the next elements of the input sequence shall be sampled (picked) or not.
@@ -173,30 +171,30 @@
* @param acceptList a bitvector which will be filled with <tt>true</tt> where sampling shall occur and <tt>false</tt> where it shall not occur.
*/
private void xsampleNextElements(BooleanArrayList acceptList) {
- // manually inlined
- int length = acceptList.size();
- boolean[] accept = acceptList.elements();
- for (int i=0; i<length; i++) {
- if (n==0) {
- accept[i] = false;
- continue;
- } //reject
- if (skip-- > 0) {
- accept[i] = false;
- continue;
- } //reject
-
- //accept
- n--;
- if (bufferPosition < buffer.length-1) {
- skip = buffer[bufferPosition+1] - buffer[bufferPosition++];
- --skip;
- }
- else {
- fetchNextBlock();
- }
-
- accept[i] = true;
- }
+ // manually inlined
+ int length = acceptList.size();
+ boolean[] accept = acceptList.elements();
+ for (int i=0; i<length; i++) {
+ if (n==0) {
+ accept[i] = false;
+ continue;
+ } //reject
+ if (skip-- > 0) {
+ accept[i] = false;
+ continue;
+ } //reject
+
+ //accept
+ n--;
+ if (bufferPosition < buffer.length-1) {
+ skip = buffer[bufferPosition+1] - buffer[bufferPosition++];
+ --skip;
+ }
+ else {
+ fetchNextBlock();
+ }
+
+ accept[i] = true;
+ }
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/WeightedRandomSampler.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/WeightedRandomSampler.java?rev=883972&r1=883971&r2=883972&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/WeightedRandomSampler.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/jet/random/sampling/WeightedRandomSampler.java Wed Nov 25 03:31:47 2009
@@ -19,8 +19,6 @@
* weight == 1.0 --> all elements are picked (sampled). weight == 10.0 --> Picks one random element from successive blocks of 10 elements each. Etc.
* The subsequence is guaranteed to be <i>stable</i>, i.e. elements never change position relative to each other.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 02/05/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
@@ -28,18 +26,18 @@
@Deprecated
public class WeightedRandomSampler extends org.apache.mahout.matrix.PersistentObject {
//public class BlockedRandomSampler extends Object implements java.io.Serializable {
- protected int skip;
- protected int nextTriggerPos;
- protected int nextSkip;
- protected int weight;
- protected Uniform generator;
+ protected int skip;
+ protected int nextTriggerPos;
+ protected int nextSkip;
+ protected int weight;
+ protected Uniform generator;
- static final int UNDEFINED = -1;
+ static final int UNDEFINED = -1;
/**
* Calls <tt>BlockedRandomSampler(1,null)</tt>.
*/
public WeightedRandomSampler() {
- this(1,null);
+ this(1,null);
}
/**
* Chooses exactly one random element from successive blocks of <tt>weight</tt> input elements each.
@@ -50,24 +48,24 @@
* @param randomGenerator a random number generator. Set this parameter to <tt>null</tt> to use the default random number generator.
*/
public WeightedRandomSampler(int weight, RandomEngine randomGenerator) {
- if (randomGenerator==null) randomGenerator = org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator();
- this.generator = new Uniform(randomGenerator);
- setWeight(weight);
+ if (randomGenerator==null) randomGenerator = org.apache.mahout.jet.random.AbstractDistribution.makeDefaultGenerator();
+ this.generator = new Uniform(randomGenerator);
+ setWeight(weight);
}
/**
* Returns a deep copy of the receiver.
*/
public Object clone() {
- WeightedRandomSampler copy = (WeightedRandomSampler) super.clone();
- copy.generator = (Uniform) this.generator.clone();
- return copy;
+ WeightedRandomSampler copy = (WeightedRandomSampler) super.clone();
+ copy.generator = (Uniform) this.generator.clone();
+ return copy;
}
/**
* Not yet commented.
* @param weight int
*/
public int getWeight() {
- return this.weight;
+ return this.weight;
}
/**
* Chooses exactly one random element from successive blocks of <tt>weight</tt> input elements each.
@@ -76,53 +74,53 @@
* @return <tt>true</tt> if the next element shall be sampled (picked), <tt>false</tt> otherwise.
*/
public boolean sampleNextElement() {
- if (skip>0) { //reject
- skip--;
- return false;
- }
-
- if (nextTriggerPos == UNDEFINED) {
- if (weight == 1) nextTriggerPos = 0; // tuned for speed
- else nextTriggerPos = generator.nextIntFromTo(0,weight-1);
-
- nextSkip = weight - 1 - nextTriggerPos;
- }
-
- if (nextTriggerPos>0) { //reject
- nextTriggerPos--;
- return false;
- }
-
- //accept
- nextTriggerPos = UNDEFINED;
- skip = nextSkip;
+ if (skip>0) { //reject
+ skip--;
+ return false;
+ }
+
+ if (nextTriggerPos == UNDEFINED) {
+ if (weight == 1) nextTriggerPos = 0; // tuned for speed
+ else nextTriggerPos = generator.nextIntFromTo(0,weight-1);
+
+ nextSkip = weight - 1 - nextTriggerPos;
+ }
+
+ if (nextTriggerPos>0) { //reject
+ nextTriggerPos--;
+ return false;
+ }
+
+ //accept
+ nextTriggerPos = UNDEFINED;
+ skip = nextSkip;
- return true;
+ return true;
}
/**
* Not yet commented.
* @param weight int
*/
public void setWeight(int weight) {
- if (weight<1) throw new IllegalArgumentException("bad weight");
- this.weight = weight;
- this.skip = 0;
- this.nextTriggerPos = UNDEFINED;
- this.nextSkip = 0;
+ if (weight<1) throw new IllegalArgumentException("bad weight");
+ this.weight = weight;
+ this.skip = 0;
+ this.nextTriggerPos = UNDEFINED;
+ this.nextSkip = 0;
}
/**
* Not yet commented.
*/
public static void test(int weight, int size) {
- WeightedRandomSampler sampler = new WeightedRandomSampler();
- sampler.setWeight(weight);
+ WeightedRandomSampler sampler = new WeightedRandomSampler();
+ sampler.setWeight(weight);
- org.apache.mahout.matrix.list.IntArrayList sample = new org.apache.mahout.matrix.list.IntArrayList();
- for (int i=0; i<size; i++) {
- if (sampler.sampleNextElement()) sample.add(i);
- }
+ org.apache.mahout.matrix.list.IntArrayList sample = new org.apache.mahout.matrix.list.IntArrayList();
+ for (int i=0; i<size; i++) {
+ if (sampler.sampleNextElement()) sample.add(i);
+ }
- System.out.println("Sample = "+sample);
+ System.out.println("Sample = "+sample);
}
/**
* Chooses exactly one random element from successive blocks of <tt>weight</tt> input elements each.
@@ -131,33 +129,33 @@
* @param acceptList a bitvector which will be filled with <tt>true</tt> where sampling shall occur and <tt>false</tt> where it shall not occur.
*/
private void xsampleNextElements(BooleanArrayList acceptList) {
- // manually inlined
- int length = acceptList.size();
- boolean[] accept = acceptList.elements();
- for (int i=0; i<length; i++) {
- if (skip>0) { //reject
- skip--;
- accept[i] = false;
- continue;
- }
-
- if (nextTriggerPos == UNDEFINED) {
- if (weight == 1) nextTriggerPos = 0; // tuned for speed
- else nextTriggerPos = generator.nextIntFromTo(0,weight-1);
-
- nextSkip = weight - 1 - nextTriggerPos;
- }
-
- if (nextTriggerPos>0) { //reject
- nextTriggerPos--;
- accept[i] = false;
- continue;
- }
-
- //accept
- nextTriggerPos = UNDEFINED;
- skip = nextSkip;
- accept[i] = true;
- }
+ // manually inlined
+ int length = acceptList.size();
+ boolean[] accept = acceptList.elements();
+ for (int i=0; i<length; i++) {
+ if (skip>0) { //reject
+ skip--;
+ accept[i] = false;
+ continue;
+ }
+
+ if (nextTriggerPos == UNDEFINED) {
+ if (weight == 1) nextTriggerPos = 0; // tuned for speed
+ else nextTriggerPos = generator.nextIntFromTo(0,weight-1);
+
+ nextSkip = weight - 1 - nextTriggerPos;
+ }
+
+ if (nextTriggerPos>0) { //reject
+ nextTriggerPos--;
+ accept[i] = false;
+ continue;
+ }
+
+ //accept
+ nextTriggerPos = UNDEFINED;
+ skip = nextSkip;
+ accept[i] = true;
+ }
}
}