Author: srowen
Date: Sun Nov 2 07:18:47 2008
New Revision: 709887
URL: http://svn.apache.org/viewvc?rev=709887&view=rev
Log:
Break out the prime related methods into another class for possible reuse
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastMap.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RandomUtils.java
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastMap.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastMap.java?rev=709887&r1=709886&r2=709887&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastMap.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastMap.java
Sun Nov 2 07:18:47 2008
@@ -41,11 +41,6 @@
*/
public final class FastMap<K, V> implements Map<K, V> {
- /**
- * The largest prime less than 2<sup>31</sup>-1 that is the smaller of a
twin prime pair.
- */
- private static final int MAX_INT_SMALLER_TWIN_PRIME = 2147482949;
-
public static final int NO_MAX_SIZE = Integer.MAX_VALUE;
/**
@@ -79,20 +74,21 @@
*
* @param size desired capacity
* @param maxSize max capacity
- * @throws IllegalArgumentException if size is less than 1 or at least half
of [EMAIL PROTECTED] #MAX_INT_SMALLER_TWIN_PRIME}
+ * @throws IllegalArgumentException if size is less than 1 or at least half
of
+ * [EMAIL PROTECTED] RandomUtils#MAX_INT_SMALLER_TWIN_PRIME}
*/
@SuppressWarnings("unchecked")
public FastMap(int size, int maxSize) throws IllegalArgumentException {
if (size < 1) {
throw new IllegalArgumentException("size must be at least 1");
}
- if (size >= MAX_INT_SMALLER_TWIN_PRIME >> 1) {
- throw new IllegalArgumentException("size must be less than " +
(MAX_INT_SMALLER_TWIN_PRIME >> 1));
+ if (size >= RandomUtils.MAX_INT_SMALLER_TWIN_PRIME >> 1) {
+ throw new IllegalArgumentException("size must be less than " +
(RandomUtils.MAX_INT_SMALLER_TWIN_PRIME >> 1));
}
if (maxSize < 1) {
throw new IllegalArgumentException("maxSize must be at least 1");
}
- int hashSize = nextTwinPrime(2 * size);
+ int hashSize = RandomUtils.nextTwinPrime(2 * size);
keys = (K[]) new Object[hashSize];
values = (V[]) new Object[hashSize];
this.maxSize = maxSize;
@@ -287,10 +283,10 @@
private void growAndRehash() {
int hashSize = keys.length;
- if (hashSize >= MAX_INT_SMALLER_TWIN_PRIME >> 1) {
+ if (hashSize >= RandomUtils.MAX_INT_SMALLER_TWIN_PRIME >> 1) {
throw new IllegalStateException("Can't grow any more");
}
- rehash(nextTwinPrime(2 * hashSize));
+ rehash(RandomUtils.nextTwinPrime(2 * hashSize));
}
@SuppressWarnings("unchecked")
@@ -313,57 +309,6 @@
}
}
- // Simple methods for finding a next larger prime
-
-
- /**
- * <p>Finds next-largest "twin primes": numbers p and p+2 such that both are
prime. Finds the smallest such p such
- * that the smaller twin, p, is greater than or equal to n. Returns p+2, the
larger of the two twins.</p>
- */
- private static int nextTwinPrime(int n) {
- if (n > MAX_INT_SMALLER_TWIN_PRIME) {
- throw new IllegalArgumentException();
- }
- int next = nextPrime(n);
- while (isNotPrime(next + 2)) {
- next = nextPrime(next + 4);
- }
- return next + 2;
- }
-
- /**
- * <p>Finds smallest prime p such that p is greater than or equal to n.</p>
- */
- private static int nextPrime(int n) {
- // Make sure the number is odd. Is this too clever?
- n |= 0x1;
- // There is no problem with overflow since Integer.MAX_INT is prime, as it
happens
- while (isNotPrime(n)) {
- n += 2;
- }
- return n;
- }
-
- /**
- * @param n
- * @return <code>true</code> iff n is not a prime
- */
- private static boolean isNotPrime(int n) {
- if (n < 2) {
- throw new IllegalArgumentException();
- }
- if ((n & 0x1) == 0) { // even
- return true;
- }
- int max = 1 + (int) Math.sqrt((double) n);
- for (int d = 3; d <= max; d += 2) {
- if (n % d == 0) {
- return true;
- }
- }
- return false;
- }
-
private void iteratorRemove(int lastNext) {
if (lastNext >= values.length) {
throw new NoSuchElementException();
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RandomUtils.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RandomUtils.java?rev=709887&r1=709886&r2=709887&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RandomUtils.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RandomUtils.java
Sun Nov 2 07:18:47 2008
@@ -24,6 +24,9 @@
/**
* <p>The source of random stuff for the whole project. This lets us make all
randomness in
* the project predictable, if desired, for when we run unit tests, which
should be repeatable.</p>
+ *
+ * <p>This class is increasingly incorrectly named as it also includes other
mathematical
+ * utility methods.</p>
*/
public final class RandomUtils {
@@ -35,6 +38,11 @@
};
private static boolean testSeed;
+ /**
+ * The largest prime less than 2<sup>31</sup>-1 that is the smaller of a
twin prime pair.
+ */
+ public static final int MAX_INT_SMALLER_TWIN_PRIME = 2147482949;
+
private RandomUtils() {
}
@@ -55,4 +63,52 @@
return (int) (bits ^ (bits >>> 32));
}
+ /**
+ * <p>Finds next-largest "twin primes": numbers p and p+2 such that both are
prime. Finds the smallest such p such
+ * that the smaller twin, p, is greater than or equal to n. Returns p+2, the
larger of the two twins.</p>
+ */
+ public static int nextTwinPrime(int n) {
+ if (n > MAX_INT_SMALLER_TWIN_PRIME) {
+ throw new IllegalArgumentException();
+ }
+ int next = nextPrime(n);
+ while (isNotPrime(next + 2)) {
+ next = nextPrime(next + 4);
+ }
+ return next + 2;
+ }
+
+ /**
+ * <p>Finds smallest prime p such that p is greater than or equal to n.</p>
+ */
+ public static int nextPrime(int n) {
+ // Make sure the number is odd. Is this too clever?
+ n |= 0x1;
+ // There is no problem with overflow since Integer.MAX_INT is prime, as it
happens
+ while (isNotPrime(n)) {
+ n += 2;
+ }
+ return n;
+ }
+
+ /**
+ * @param n
+ * @return <code>true</code> iff n is not a prime
+ */
+ public static boolean isNotPrime(int n) {
+ if (n < 2) {
+ throw new IllegalArgumentException();
+ }
+ if ((n & 0x1) == 0) { // even
+ return true;
+ }
+ int max = 1 + (int) Math.sqrt((double) n);
+ for (int d = 3; d <= max; d += 2) {
+ if (n % d == 0) {
+ return true;
+ }
+ }
+ return false;
+ }
+
}
