You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ra...@apache.org on 2018/09/08 23:35:08 UTC
[04/15] mahout git commit: NO-JIRA Trevors updates
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/list/package-info.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/list/package-info.java b/core/src/main/java/org/apache/mahout/math/list/package-info.java
new file mode 100644
index 0000000..43b5c4b
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/list/package-info.java
@@ -0,0 +1,144 @@
+/**
+ * <HTML>
+ * <BODY>
+ * Resizable lists holding objects or primitive data types such as <tt>int</tt>,
+ * <tt>double</tt>, etc. For non-resizable lists (1-dimensional matrices) see
+ * package <code>org.apache.mahout.math.matrix</code>.<p></p>
+ * <h1><a name="Overview"></a>Getting Started</h1>
+ * <h2>1. Overview</h2>
+ * <p>The list package offers flexible object oriented abstractions modelling dynamically
+ * resizing lists holding objects or primitive data types such as <tt>int</tt>,
+ * <tt>double</tt>, etc. It is designed to be scalable in terms of performance
+ * and memory requirements.</p>
+ * <p>Features include: </p>
+ * <p></p>
+ * <ul>
+ * <li>Lists operating on objects as well as all primitive data types such as <tt>int</tt>,
+ * <tt>double</tt>, etc.
+ * </li>
+ * <li>Compact representations</li>
+ * <li>A number of general purpose list operations including: adding, inserting,
+ * removing, iterating, searching, sorting, extracting ranges and copying. All
+ * operations are designed to perform well on mass data.
+ * </li>
+ * <li>Support for quick access to list elements. This is achieved by bounds-checking
+ * and non-bounds-checking accessor methods as well as zero-copy transformations
+ * to primitive arrays such as <tt>int[]</tt>, <tt>double[]</tt>, etc.
+ * </li>
+ * <li>Allows to use high level algorithms on primitive data types without any
+ * space and time overhead. Operations on primitive arrays, Colt lists and JAL
+ * algorithms can freely be mixed at zero copy overhead.
+ * </li>
+ * </ul>
+ * <p>File-based I/O can be achieved through the standard Java built-in serialization
+ * mechanism. All classes implement the {@link java.io.Serializable} interface.
+ * However, the toolkit is entirely decoupled from advanced I/O. It provides data
+ * structures and algorithms only.
+ * <p> This toolkit borrows concepts and terminology from the Javasoft <a
+ * href="http://www.javasoft.com/products/jdk/1.2/docs/guide/collections/index.html">
+ * Collections framework</a> written by Josh Bloch and introduced in JDK 1.2.
+ * <h2>2. Introduction</h2>
+ * <p>Lists are fundamental to virtually any application. Large scale resizable lists
+ * are, for example, used in scientific computations, simulations database management
+ * systems, to name just a few.</p>
+ * <h2></h2>
+ * <p>A list is a container holding elements that can be accessed via zero-based
+ * indexes. Lists may be implemented in different ways (most commonly with arrays).
+ * A resizable list automatically grows as elements are added. The lists of this
+ * package do not automatically shrink. Shrinking needs to be triggered by explicitly
+ * calling <tt>trimToSize()</tt> methods.</p>
+ * <p><i>Growing policy</i>: A list implemented with arrays initially has a certain
+ * <tt>initialCapacity</tt> - per default 10 elements, but customizable upon instance
+ * construction. As elements are added, this capacity may nomore be sufficient.
+ * When a list is automatically grown, its capacity is expanded to <tt>1.5*currentCapacity</tt>.
+ * Thus, excessive resizing (involving copying) is avoided.</p>
+ * <h4>Copying</h4>
+ * <p>
+ * <p>Any list can be copied. A copy is <i>equal</i> to the original but entirely
+ * independent of the original. So changes in the copy are not reflected in the
+ * original, and vice-versa.
+ * <h2>3. Organization of this package</h2>
+ * <p>Class naming follows the schema <tt><ElementType><ImplementationTechnique>List</tt>.
+ * For example, we have a {@link org.apache.mahout.math.list.DoubleArrayList}, which is a list
+ * holding <tt>double</tt> elements implemented with <tt>double</tt>[] arrays.
+ * </p>
+ * <p>The classes for lists of a given value type are derived from a common abstract
+ * base class tagged <tt>Abstract<ElementType></tt><tt>List</tt>. For example,
+ * all lists operating on <tt>double</tt> elements are derived from
+ * {@link org.apache.mahout.math.list.AbstractDoubleList},
+ * which in turn is derived from an abstract base class tying together all lists
+ * regardless of value type, {@link org.apache.mahout.math.list.AbstractList}. The abstract
+ * base classes provide skeleton implementations for all but few methods. Experimental
+ * data layouts (such as compressed, sparse, linked, etc.) can easily be implemented
+ * and inherit a rich set of functionality. Have a look at the javadoc <a href="package-tree.html">tree
+ * view</a> to get the broad picture.</p>
+ * <h2>4. Example usage</h2>
+ * <p>The following snippet fills a list, randomizes it, extracts the first half
+ * of the elements, sums them up and prints the result. It is implemented entirely
+ * with accessor methods.</p>
+ * <table>
+ * <td class="PRE">
+ * <pre>
+ * int s = 1000000;<br>AbstractDoubleList list = new DoubleArrayList();
+ * for (int i=0; i<s; i++) { list.add((double)i); }
+ * list.shuffle();
+ * AbstractDoubleList part = list.partFromTo(0,list.size()/2 - 1);
+ * double sum = 0.0;
+ * for (int i=0; i<part.size(); i++) { sum += part.get(i); }
+ * log.info(sum);
+ * </pre>
+ * </td>
+ * </table>
+ * <p> For efficiency, all classes provide back doors to enable getting/setting the
+ * backing array directly. In this way, the high level operations of these classes
+ * can be used where appropriate, and one can switch to <tt>[]</tt>-array index
+ * notations where necessary. The key methods for this are <tt>public <ElementType>[]
+ * elements()</tt> and <tt>public void elements(<ElementType>[])</tt>. The
+ * former trustingly returns the array it internally keeps to store the elements.
+ * Holding this array in hand, we can use the <tt>[]</tt>-array operator to
+ * perform iteration over large lists without needing to copy the array or paying
+ * the performance penalty introduced by accessor methods. Alternatively any JAL
+ * algorithm (or other algorithm) can operate on the returned primitive array.
+ * The latter method forces a list to internally hold a user provided array. Using
+ * this approach one can avoid needing to copy the elements into the list.
+ * <p>As a consequence, operations on primitive arrays, Colt lists and JAL algorithms
+ * can freely be mixed at zero-copy overhead.
+ * <p> Note that such special treatment certainly breaks encapsulation. This functionality
+ * is provided for performance reasons only and should only be used when absolutely
+ * necessary. Here is the above example in mixed notation:
+ * <table>
+ * <td class="PRE">
+ * <pre>
+ * int s = 1000000;<br>DoubleArrayList list = new DoubleArrayList(s); // list.size()==0, capacity==s
+ * list.setSize(s); // list.size()==s<br>double[] values = list.elements();
+ * // zero copy, values.length==s<br>for (int i=0; i<s; i++) { values[i]=(double)i; }
+ * list.shuffle();
+ * double sum = 0.0;
+ * int limit = values.length/2;
+ * for (int i=0; i<limit; i++) { sum += values[i]; }
+ * log.info(sum);
+ * </pre>
+ * </td>
+ * </table>
+ * <p> Or even more compact using lists as algorithm objects:
+ * <table>
+ * <td class="PRE">
+ * <pre>
+ * int s = 1000000;<br>double[] values = new double[s];
+ * for (int i=0; i<s; i++) { values[i]=(double)i; }
+ * new DoubleArrayList(values).shuffle(); // zero-copy, shuffle via back door
+ * double sum = 0.0;
+ * int limit = values.length/2;
+ * for (int i=0; i<limit; i++) { sum += values[i]; }
+ * log.info(sum);
+ * </pre>
+ * </td>
+ * </table>
+ * <p>
+ * <h2>5. Notes </h2>
+ * <p>The quicksorts and mergesorts are the JDK 1.2 V1.26 algorithms, modified as
+ * necessary to operate on the given data types.
+ * </BODY>
+ * </HTML>
+ */
+package org.apache.mahout.math.list;
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/map/HashFunctions.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/map/HashFunctions.java b/core/src/main/java/org/apache/mahout/math/map/HashFunctions.java
new file mode 100644
index 0000000..b749307
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/map/HashFunctions.java
@@ -0,0 +1,115 @@
+/*
+Copyright 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math.map;
+
+
+/**
+ * Provides various hash functions.
+ */
+public final class HashFunctions {
+
+ /**
+ * Utility class pattern: all static members, no inheritance.
+ */
+ private HashFunctions() {
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(char value) {
+ return value;
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(double value) {
+ long bits = Double.doubleToLongBits(value);
+ return (int) (bits ^ (bits >>> 32));
+
+ //return (int) Double.doubleToLongBits(value*663608941.737);
+ // this avoids excessive hashCollisions in the case values are of the form (1.0, 2.0, 3.0, ...)
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(float value) {
+ return Float.floatToIntBits(value * 663608941.737f);
+ // this avoids excessive hashCollisions in the case values are of the form (1.0, 2.0, 3.0, ...)
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ * The hashcode computation is similar to the last step
+ * of MurMurHash3.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(int value) {
+ int h = value;
+ h ^= h >>> 16;
+ h *= 0x85ebca6b;
+ h ^= h >>> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >>> 16;
+ return h;
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(long value) {
+ return (int) (value ^ (value >> 32));
+ /*
+ value &= 0x7FFFFFFFFFFFFFFFL; // make it >=0 (0x7FFFFFFFFFFFFFFFL==Long.MAX_VALUE)
+ int hashCode = 0;
+ do hashCode = 31*hashCode + (int) (value%10);
+ while ((value /= 10) > 0);
+
+ return 28629151*hashCode; // spread even further; h*31^5
+ */
+ }
+
+ /**
+ * Returns a hashcode for the specified object.
+ *
+ * @return a hash code value for the specified object.
+ */
+ public static int hash(Object object) {
+ return object == null ? 0 : object.hashCode();
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(short value) {
+ return value;
+ }
+
+ /**
+ * Returns a hashcode for the specified value.
+ *
+ * @return a hash code value for the specified value.
+ */
+ public static int hash(boolean value) {
+ return value ? 1231 : 1237;
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/map/OpenHashMap.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/map/OpenHashMap.java b/core/src/main/java/org/apache/mahout/math/map/OpenHashMap.java
new file mode 100644
index 0000000..0efca4b
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/map/OpenHashMap.java
@@ -0,0 +1,652 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*
+Copyright � 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math.map;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.mahout.math.function.ObjectObjectProcedure;
+import org.apache.mahout.math.function.ObjectProcedure;
+import org.apache.mahout.math.set.AbstractSet;
+import org.apache.mahout.math.set.OpenHashSet;
+
+/**
+ * Open hash map. This implements Map, but it does not respect several aspects of the Map contract
+ * that impose the very sorts of performance penalities that this class exists to avoid.
+ * {@link #entrySet}, {@link #values}, and {@link #keySet()} do <strong>not</strong> return
+ * collections that share storage with the main map, and changes to those returned objects
+ * are <strong>not</strong> reflected in the container.
+ **/
+public class OpenHashMap<K,V> extends AbstractSet implements Map<K,V> {
+ protected static final byte FREE = 0;
+ protected static final byte FULL = 1;
+ protected static final byte REMOVED = 2;
+ protected static final Object NO_KEY_VALUE = null;
+
+ /** The hash table keys. */
+ protected Object[] table;
+
+ /** The hash table values. */
+ protected Object[] values;
+
+ /** The state of each hash table entry (FREE, FULL, REMOVED). */
+ protected byte[] state;
+
+ /** The number of table entries in state==FREE. */
+ protected int freeEntries;
+
+
+ /** Constructs an empty map with default capacity and default load factors. */
+ public OpenHashMap() {
+ this(DEFAULT_CAPACITY);
+ }
+
+ /**
+ * Constructs an empty map with the specified initial capacity and default load factors.
+ *
+ * @param initialCapacity the initial capacity of the map.
+ * @throws IllegalArgumentException if the initial capacity is less than zero.
+ */
+ public OpenHashMap(int initialCapacity) {
+ this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);
+ }
+
+ /**
+ * Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.
+ *
+ * @param initialCapacity the initial capacity.
+ * @param minLoadFactor the minimum load factor.
+ * @param maxLoadFactor the maximum load factor.
+ * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+ * (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+ * maxLoadFactor)</tt>.
+ */
+ public OpenHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ setUp(initialCapacity, minLoadFactor, maxLoadFactor);
+ }
+
+ /** Removes all (key,value) associations from the receiver. Implicitly calls <tt>trimToSize()</tt>. */
+ @Override
+ public void clear() {
+ Arrays.fill(this.state, FREE);
+ distinct = 0;
+ freeEntries = table.length; // delta
+ trimToSize();
+ }
+
+ /**
+ * Returns a deep copy of the receiver.
+ *
+ * @return a deep copy of the receiver.
+ */
+ @Override
+ @SuppressWarnings("unchecked")
+ public Object clone() {
+ OpenHashMap<K,V> copy = (OpenHashMap<K,V>) super.clone();
+ copy.table = copy.table.clone();
+ copy.values = copy.values.clone();
+ copy.state = copy.state.clone();
+ return copy;
+ }
+
+ /**
+ * Returns <tt>true</tt> if the receiver contains the specified key.
+ *
+ * @return <tt>true</tt> if the receiver contains the specified key.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsKey(Object key) {
+ return indexOfKey((K)key) >= 0;
+ }
+
+ /**
+ * Returns <tt>true</tt> if the receiver contains the specified value.
+ *
+ * @return <tt>true</tt> if the receiver contains the specified value.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsValue(Object value) {
+ return indexOfValue((V)value) >= 0;
+ }
+
+ /**
+ * Ensures that the receiver can hold at least the specified number of associations without needing to allocate new
+ * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver. <p> This
+ * method never need be called; it is for performance tuning only. Calling this method before <tt>put()</tt>ing a
+ * large number of associations boosts performance, because the receiver will grow only once instead of potentially
+ * many times and hash collisions get less probable.
+ *
+ * @param minCapacity the desired minimum capacity.
+ */
+ @Override
+ public void ensureCapacity(int minCapacity) {
+ if (table.length < minCapacity) {
+ int newCapacity = nextPrime(minCapacity);
+ rehash(newCapacity);
+ }
+ }
+
+ /**
+ * Applies a procedure to each key of the receiver, if any. Note: Iterates over the keys in no particular order.
+ * Subclasses can define a particular order, for example, "sorted by key". All methods which <i>can</i> be expressed
+ * in terms of this method (most methods can) <i>must guarantee</i> to use the <i>same</i> order defined by this
+ * method, even if it is no particular order. This is necessary so that, for example, methods <tt>keys</tt> and
+ * <tt>values</tt> will yield association pairs, not two uncorrelated lists.
+ *
+ * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+ * continues.
+ * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+ */
+ @SuppressWarnings("unchecked")
+ public boolean forEachKey(ObjectProcedure<K> procedure) {
+ for (int i = table.length; i-- > 0;) {
+ if (state[i] == FULL && !procedure.apply((K)table[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Applies a procedure to each (key,value) pair of the receiver, if any. Iteration order is guaranteed to be
+ * <i>identical</i> to the order used by method {@link #forEachKey(ObjectProcedure)}.
+ *
+ * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
+ * continues.
+ * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
+ */
+ @SuppressWarnings("unchecked")
+ public boolean forEachPair(ObjectObjectProcedure<K,V> procedure) {
+ for (int i = table.length; i-- > 0;) {
+ if (state[i] == FULL && !procedure.apply((K)table[i], (V)values[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Returns the value associated with the specified key. It is often a good idea to first check with {@link
+ * #containsKey(Object)} whether the given key has a value associated or not, i.e. whether there exists an association
+ * for the given key or not.
+ *
+ * @param key the key to be searched for.
+ * @return the value associated with the specified key; <tt>0</tt> if no such key is present.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public V get(Object key) {
+ int i = indexOfKey((K)key);
+ if (i < 0) {
+ return null;
+ } //not contained
+ return (V)values[i];
+ }
+
+ /**
+ * @param key the key to be added to the receiver.
+ * @return the index where the key would need to be inserted, if it is not already contained. Returns -index-1 if the
+ * key is already contained at slot index. Therefore, if the returned index < 0, then it is already contained
+ * at slot -index-1. If the returned index >= 0, then it is NOT already contained and should be inserted at
+ * slot index.
+ */
+ protected int indexOfInsertion(K key) {
+ Object[] tab = table;
+ byte[] stat = state;
+ int length = tab.length;
+
+ int hash = key.hashCode() & 0x7FFFFFFF;
+ int i = hash % length;
+ int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+ //int decrement = (hash / length) % length;
+ if (decrement == 0) {
+ decrement = 1;
+ }
+
+ // stop if we find a removed or free slot, or if we find the key itself
+ // do NOT skip over removed slots (yes, open addressing is like that...)
+ while (stat[i] == FULL && !equalsMindTheNull(key, tab[i])) {
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+
+ if (stat[i] == REMOVED) {
+ // stop if we find a free slot, or if we find the key itself.
+ // do skip over removed slots (yes, open addressing is like that...)
+ // assertion: there is at least one FREE slot.
+ int j = i;
+ while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+ if (stat[i] == FREE) {
+ i = j;
+ }
+ }
+
+
+ if (stat[i] == FULL) {
+ // key already contained at slot i.
+ // return a negative number identifying the slot.
+ return -i - 1;
+ }
+ // not already contained, should be inserted at slot i.
+ // return a number >= 0 identifying the slot.
+ return i;
+ }
+
+ /**
+ * @param key the key to be searched in the receiver.
+ * @return the index where the key is contained in the receiver, returns -1 if the key was not found.
+ */
+ protected int indexOfKey(K key) {
+ Object[] tab = table;
+ byte[] stat = state;
+ int length = tab.length;
+
+ int hash = key.hashCode() & 0x7FFFFFFF;
+ int i = hash % length;
+ int decrement = hash % (length - 2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
+ //int decrement = (hash / length) % length;
+ if (decrement == 0) {
+ decrement = 1;
+ }
+
+ // stop if we find a free slot, or if we find the key itself.
+ // do skip over removed slots (yes, open addressing is like that...)
+ while (stat[i] != FREE && (stat[i] == REMOVED || !equalsMindTheNull(key, tab[i]))) {
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+
+ if (stat[i] == FREE) {
+ return -1;
+ } // not found
+ return i; //found, return index where key is contained
+ }
+
+ /**
+ * @param value the value to be searched in the receiver.
+ * @return the index where the value is contained in the receiver, returns -1 if the value was not found.
+ */
+ protected int indexOfValue(V value) {
+ Object[] val = values;
+ byte[] stat = state;
+
+ for (int i = stat.length; --i >= 0;) {
+ if (stat[i] == FULL && equalsMindTheNull(val[i], value)) {
+ return i;
+ }
+ }
+
+ return -1; // not found
+ }
+
+ /**
+ * Fills all keys contained in the receiver into the specified list. Fills the list, starting at index 0. After this
+ * call returns the specified list has a new size that equals <tt>this.size()</tt>.
+ * This method can be used
+ * to iterate over the keys of the receiver.
+ *
+ * @param list the list to be filled, can have any size.
+ */
+ @SuppressWarnings("unchecked")
+ public void keys(List<K> list) {
+ list.clear();
+
+
+ Object [] tab = table;
+ byte[] stat = state;
+
+ for (int i = tab.length; i-- > 0;) {
+ if (stat[i] == FULL) {
+ list.add((K)tab[i]);
+ }
+ }
+ }
+
+ /**
+ * Associates the given key with the given value. Replaces any old <tt>(key,someOtherValue)</tt> association, if
+ * existing.
+ *
+ * @param key the key the value shall be associated with.
+ * @param value the value to be associated.
+ * @return <tt>true</tt> if the receiver did not already contain such a key; <tt>false</tt> if the receiver did
+ * already contain such a key - the new value has now replaced the formerly associated value.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public V put(K key, V value) {
+ int i = indexOfInsertion(key);
+ if (i < 0) { //already contained
+ i = -i - 1;
+ V previous = (V) this.values[i];
+ this.values[i] = value;
+ return previous;
+ }
+
+ if (this.distinct > this.highWaterMark) {
+ int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ return put(key, value);
+ }
+
+ this.table[i] = key;
+ this.values[i] = value;
+ if (this.state[i] == FREE) {
+ this.freeEntries--;
+ }
+ this.state[i] = FULL;
+ this.distinct++;
+
+ if (this.freeEntries < 1) { //delta
+ int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ }
+
+ return null;
+ }
+
+ /**
+ * Rehashes the contents of the receiver into a new table with a smaller or larger capacity. This method is called
+ * automatically when the number of keys in the receiver exceeds the high water mark or falls below the low water
+ * mark.
+ */
+ @SuppressWarnings("unchecked")
+ protected void rehash(int newCapacity) {
+ int oldCapacity = table.length;
+ //if (oldCapacity == newCapacity) return;
+
+ Object[] oldTable = table;
+ Object[] oldValues = values;
+ byte[] oldState = state;
+
+ Object[] newTable = new Object[newCapacity];
+ Object[] newValues = new Object[newCapacity];
+ byte[] newState = new byte[newCapacity];
+
+ this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
+ this.highWaterMark = chooseHighWaterMark(newCapacity, this.maxLoadFactor);
+
+ this.table = newTable;
+ this.values = newValues;
+ this.state = newState;
+ this.freeEntries = newCapacity - this.distinct; // delta
+
+ for (int i = oldCapacity; i-- > 0;) {
+ if (oldState[i] == FULL) {
+ Object element = oldTable[i];
+ int index = indexOfInsertion((K)element);
+ newTable[index] = element;
+ newValues[index] = oldValues[i];
+ newState[index] = FULL;
+ }
+ }
+ }
+
+ /**
+ * Removes the given key with its associated element from the receiver, if present.
+ *
+ * @param key the key to be removed from the receiver.
+ * @return <tt>true</tt> if the receiver contained the specified key, <tt>false</tt> otherwise.
+ */
+ @SuppressWarnings("unchecked")
+ @Override
+ public V remove(Object key) {
+ int i = indexOfKey((K)key);
+ if (i < 0) {
+ return null;
+ }
+ // key not contained
+ V removed = (V) values[i];
+
+ this.state[i] = REMOVED;
+ //this.values[i]=0; // delta
+ this.distinct--;
+
+ if (this.distinct < this.lowWaterMark) {
+ int newCapacity = chooseShrinkCapacity(this.distinct, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ }
+
+ return removed;
+ }
+
+ /**
+ * Initializes the receiver.
+ *
+ * @param initialCapacity the initial capacity of the receiver.
+ * @param minLoadFactor the minLoadFactor of the receiver.
+ * @param maxLoadFactor the maxLoadFactor of the receiver.
+ * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+ * (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+ * maxLoadFactor)</tt>.
+ */
+ @Override
+ protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ int capacity = initialCapacity;
+ super.setUp(capacity, minLoadFactor, maxLoadFactor);
+ capacity = nextPrime(capacity);
+ if (capacity == 0) {
+ capacity = 1;
+ } // open addressing needs at least one FREE slot at any time.
+
+ this.table = new Object[capacity];
+ this.values = new Object[capacity];
+ this.state = new byte[capacity];
+
+ // memory will be exhausted long before this pathological case happens, anyway.
+ this.minLoadFactor = minLoadFactor;
+ if (capacity == PrimeFinder.LARGEST_PRIME) {
+ this.maxLoadFactor = 1.0;
+ } else {
+ this.maxLoadFactor = maxLoadFactor;
+ }
+
+ this.distinct = 0;
+ this.freeEntries = capacity; // delta
+
+ // lowWaterMark will be established upon first expansion.
+ // establishing it now (upon instance construction) would immediately make the table shrink upon first put(...).
+ // After all the idea of an "initialCapacity" implies violating lowWaterMarks when an object is young.
+ // See ensureCapacity(...)
+ this.lowWaterMark = 0;
+ this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
+ }
+
+ /**
+ * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An
+ * application can use this operation to minimize the storage of the receiver.
+ */
+ @Override
+ public void trimToSize() {
+ // * 1.2 because open addressing's performance exponentially degrades beyond that point
+ // so that even rehashing the table can take very long
+ int newCapacity = nextPrime((int) (1 + 1.2 * size()));
+ if (table.length > newCapacity) {
+ rehash(newCapacity);
+ }
+ }
+
+ /**
+ * Access for unit tests.
+ * @param capacity
+ * @param minLoadFactor
+ * @param maxLoadFactor
+ */
+ void getInternalFactors(int[] capacity,
+ double[] minLoadFactor,
+ double[] maxLoadFactor) {
+ capacity[0] = table.length;
+ minLoadFactor[0] = this.minLoadFactor;
+ maxLoadFactor[0] = this.maxLoadFactor;
+ }
+
+ private class MapEntry implements Map.Entry<K,V> {
+ private final K key;
+ private final V value;
+
+ MapEntry(K key, V value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ @Override
+ public K getKey() {
+ return key;
+ }
+
+ @Override
+ public V getValue() {
+ return value;
+ }
+
+ @Override
+ public V setValue(V value) {
+ throw new UnsupportedOperationException("Map.Entry.setValue not supported for OpenHashMap");
+ }
+
+ }
+
+ /**
+ * Allocate a set to contain Map.Entry objects for the pairs and return it.
+ */
+ @Override
+ public Set<java.util.Map.Entry<K,V>> entrySet() {
+ final Set<Entry<K, V>> entries = new OpenHashSet<>();
+ forEachPair(new ObjectObjectProcedure<K,V>() {
+ @Override
+ public boolean apply(K key, V value) {
+ entries.add(new MapEntry(key, value));
+ return true;
+ }
+ });
+ return entries;
+ }
+
+ /**
+ * Allocate a set to contain keys and return it.
+ * This violates the 'backing' provisions of the map interface.
+ */
+ @Override
+ public Set<K> keySet() {
+ final Set<K> keys = new OpenHashSet<>();
+ forEachKey(new ObjectProcedure<K>() {
+ @Override
+ public boolean apply(K element) {
+ keys.add(element);
+ return true;
+ }
+ });
+ return keys;
+ }
+
+ @Override
+ public void putAll(Map<? extends K,? extends V> m) {
+ for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
+ put(e.getKey(), e.getValue());
+ }
+ }
+
+ /**
+ * Allocate a list to contain the values and return it.
+ * This violates the 'backing' provision of the Map interface.
+ */
+ @Override
+ public Collection<V> values() {
+ final List<V> valueList = new ArrayList<>();
+ forEachPair(new ObjectObjectProcedure<K,V>() {
+ @Override
+ public boolean apply(K key, V value) {
+ valueList.add(value);
+ return true;
+ }
+ });
+ return valueList;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof OpenHashMap)) {
+ return false;
+ }
+ final OpenHashMap<K,V> o = (OpenHashMap<K,V>) obj;
+ if (o.size() != size()) {
+ return false;
+ }
+ final boolean[] equal = new boolean[1];
+ equal[0] = true;
+ forEachPair(new ObjectObjectProcedure<K,V>() {
+ @Override
+ public boolean apply(K key, V value) {
+ Object ov = o.get(key);
+ if (!value.equals(ov)) {
+ equal[0] = false;
+ return false;
+ }
+ return true;
+ }
+ });
+ return equal[0];
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append('{');
+ forEachPair(new ObjectObjectProcedure<K,V>() {
+ @Override
+ public boolean apply(K key, V value) {
+ sb.append('[');
+ sb.append(key);
+ sb.append(" -> ");
+ sb.append(value);
+ sb.append("] ");
+ return true;
+ }
+ });
+ sb.append('}');
+ return sb.toString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/map/PrimeFinder.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/map/PrimeFinder.java b/core/src/main/java/org/apache/mahout/math/map/PrimeFinder.java
new file mode 100644
index 0000000..b02611e
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/map/PrimeFinder.java
@@ -0,0 +1,145 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.mahout.math.map;
+
+import java.util.Arrays;
+
+/**
+ * Not of interest for users; only for implementors of hashtables.
+ * Used to keep hash table capacities prime numbers.
+ *
+ * <p>Choosing prime numbers as hash table capacities is a good idea to keep them working fast,
+ * particularly under hash table expansions.
+ *
+ * <p>However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to keep capacities prime.
+ * This class provides efficient means to choose prime capacities.
+ *
+ * <p>Choosing a prime is <tt>O(log 300)</tt> (binary search in a list of 300 int's).
+ * Memory requirements: 1 KB static memory.
+ *
+ */
+public final class PrimeFinder {
+
+ /** The largest prime this class can generate; currently equal to <tt>Integer.MAX_VALUE</tt>. */
+ public static final int LARGEST_PRIME = Integer.MAX_VALUE; //yes, it is prime.
+
+ /**
+ * The prime number list consists of 11 chunks. Each chunk contains prime numbers. A chunk starts with a prime P1. The
+ * next element is a prime P2. P2 is the smallest prime for which holds: P2 >= 2*P1. The next element is P3, for which
+ * the same holds with respect to P2, and so on.
+ *
+ * Chunks are chosen such that for any desired capacity >= 1000 the list includes a prime number <= desired capacity *
+ * 1.11 (11%). For any desired capacity >= 200 the list includes a prime number <= desired capacity * 1.16 (16%). For
+ * any desired capacity >= 16 the list includes a prime number <= desired capacity * 1.21 (21%).
+ *
+ * Therefore, primes can be retrieved which are quite close to any desired capacity, which in turn avoids wasting
+ * memory. For example, the list includes 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081. So if you need a
+ * prime >= 1040, you will find a prime <= 1040*1.11=1154.
+ *
+ * Chunks are chosen such that they are optimized for a hashtable growthfactor of 2.0; If your hashtable has such a
+ * growthfactor then, after initially "rounding to a prime" upon hashtable construction, it will later expand to prime
+ * capacities such that there exist no better primes.
+ *
+ * In total these are about 32*10=320 numbers -> 1 KB of static memory needed. If you are stingy, then delete every
+ * second or fourth chunk.
+ */
+
+ private static final int[] PRIME_CAPACITIES = {
+ //chunk #0
+ LARGEST_PRIME,
+
+ //chunk #1
+ 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 102877, 205759,
+ 411527, 823117, 1646237, 3292489, 6584983, 13169977, 26339969, 52679969, 105359939,
+ 210719881, 421439783, 842879579, 1685759167,
+
+ //chunk #2
+ 433, 877, 1759, 3527, 7057, 14143, 28289, 56591, 113189, 226379, 452759, 905551, 1811107,
+ 3622219, 7244441, 14488931, 28977863, 57955739, 115911563, 231823147, 463646329, 927292699,
+ 1854585413,
+
+ //chunk #3
+ 953, 1907, 3821, 7643, 15287, 30577, 61169, 122347, 244703, 489407, 978821, 1957651, 3915341,
+ 7830701, 15661423, 31322867, 62645741, 125291483, 250582987, 501165979, 1002331963,
+ 2004663929,
+
+ //chunk #4
+ 1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853, 267713, 535481, 1070981, 2141977, 4283963,
+ 8567929, 17135863, 34271747, 68543509, 137087021, 274174111, 548348231, 1096696463,
+
+ //chunk #5
+ 31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741, 143483, 286973, 573953,
+ 1147921, 2295859, 4591721, 9183457, 18366923, 36733847, 73467739, 146935499, 293871013,
+ 587742049, 1175484103,
+
+ //chunk #6
+ 599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027, 310081, 620171, 1240361, 2480729,
+ 4961459, 9922933, 19845871, 39691759, 79383533, 158767069, 317534141, 635068283, 1270136683,
+
+ //chunk #7
+ 311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037, 164089, 328213, 656429, 1312867,
+ 2625761, 5251529, 10503061, 21006137, 42012281, 84024581, 168049163, 336098327, 672196673,
+ 1344393353,
+
+ //chunk #8
+ 3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899,
+ 701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557,
+ 359339171, 718678369, 1437356741,
+
+ //chunk #9
+ 43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159, 46327, 92657, 185323, 370661, 741337,
+ 1482707, 2965421, 5930887, 11861791, 23723597, 47447201, 94894427, 189788857, 379577741,
+ 759155483, 1518310967,
+
+ //chunk #10
+ 379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649, 195311, 390647, 781301, 1562611,
+ 3125257, 6250537, 12501169, 25002389, 50004791, 100009607, 200019221, 400038451, 800076929,
+ 1600153859
+ };
+
+
+ static { //initializer
+ // The above prime numbers are formatted for human readability.
+ // To find numbers fast, we sort them once and for all.
+
+ Arrays.sort(PRIME_CAPACITIES);
+ }
+
+ /** Makes this class non instantiable, but still let's others inherit from it. */
+ private PrimeFinder() {
+ }
+
+ /**
+ * Returns a prime number which is {@code <= desiredCapacity} and very close to {@code desiredCapacity}
+ * (within 11% if {@code desiredCapacity <= 1000}).
+ *
+ * @param desiredCapacity the capacity desired by the user.
+ * @return the capacity which should be used for a hashtable.
+ */
+ public static int nextPrime(int desiredCapacity) {
+ int i = java.util.Arrays.binarySearch(PRIME_CAPACITIES, desiredCapacity);
+ if (i < 0) {
+ // desired capacity not found, choose next prime greater than desired capacity
+ i = -i - 1; // remember the semantics of binarySearch...
+ }
+ return PRIME_CAPACITIES[i];
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/map/QuickOpenIntIntHashMap.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/map/QuickOpenIntIntHashMap.java b/core/src/main/java/org/apache/mahout/math/map/QuickOpenIntIntHashMap.java
new file mode 100644
index 0000000..6a7cef8
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/map/QuickOpenIntIntHashMap.java
@@ -0,0 +1,215 @@
+/*
+Copyright � 1999 CERN - European Organization for Nuclear Research.
+Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
+is hereby granted without fee, provided that the above copyright notice appear in all copies and
+that both that copyright notice and this permission notice appear in supporting documentation.
+CERN makes no representations about the suitability of this software for any purpose.
+It is provided "as is" without expressed or implied warranty.
+*/
+package org.apache.mahout.math.map;
+
+/**
+ * Status: Experimental; Do not use for production yet. Hash map holding (key,value) associations of type
+ * <tt>(int-->int)</tt>; Automatically grows and shrinks as needed; Implemented using open addressing with double
+ * hashing. First see the <a href="package-summary.html">package summary</a> and javadoc <a
+ * href="package-tree.html">tree view</a> to get the broad picture.
+ *
+ * Implements open addressing with double hashing, using "Brent's variation". Brent's variation slows insertions a bit
+ * down (not much) but reduces probes (collisions) for successful searches, in particular for large load factors. (It
+ * does not improve unsuccessful searches.) See D. Knuth, Searching and Sorting, 3rd ed., p.533-545
+ *
+ * @author wolfgang.hoschek@cern.ch
+ * @version 1.0, 09/24/99
+ * @see java.util.HashMap
+ */
+class QuickOpenIntIntHashMap extends OpenIntIntHashMap {
+ //public int totalProbesSaved = 0; // benchmark only
+
+ /** Constructs an empty map with default capacity and default load factors. */
+ QuickOpenIntIntHashMap() {
+ this(DEFAULT_CAPACITY);
+ }
+
+ /**
+ * Constructs an empty map with the specified initial capacity and default load factors.
+ *
+ * @param initialCapacity the initial capacity of the map.
+ * @throws IllegalArgumentException if the initial capacity is less than zero.
+ */
+ QuickOpenIntIntHashMap(int initialCapacity) {
+ this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR);
+ }
+
+ /**
+ * Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.
+ *
+ * @param initialCapacity the initial capacity.
+ * @param minLoadFactor the minimum load factor.
+ * @param maxLoadFactor the maximum load factor.
+ * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) ||
+ * (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >=
+ * maxLoadFactor)</tt>.
+ */
+ QuickOpenIntIntHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
+ setUp(initialCapacity, minLoadFactor, maxLoadFactor);
+ }
+
+ /**
+ * Associates the given key with the given value. Replaces any old <tt>(key,someOtherValue)</tt> association, if
+ * existing.
+ *
+ * @param key the key the value shall be associated with.
+ * @param value the value to be associated.
+ * @return <tt>true</tt> if the receiver did not already contain such a key; <tt>false</tt> if the receiver did
+ * already contain such a key - the new value has now replaced the formerly associated value.
+ */
+ @Override
+ public boolean put(int key, int value) {
+ /*
+ This is open addressing with double hashing, using "Brent's variation".
+ Brent's variation slows insertions a bit down (not much) but reduces probes (collisions) for successful searches,
+ in particular for large load factors.
+ (It does not improve unsuccessful searches.)
+ See D. Knuth, Searching and Sorting, 3rd ed., p.533-545
+
+ h1(key) = hash % M
+ h2(key) = decrement = Max(1, hash/M % M)
+ M is prime = capacity = table.length
+ probing positions are table[(h1-j*h2) % M] for j=0,1,...
+ (M and h2 could also be chosen differently, but h2 is required to be relative prime to M.)
+ */
+
+ int[] tab = table;
+ byte[] stat = state;
+ int length = tab.length;
+
+ int hash = HashFunctions.hash(key) & 0x7FFFFFFF;
+ int i = hash % length;
+ int decrement = (hash / length) % length;
+ if (decrement == 0) {
+ decrement = 1;
+ }
+
+ // stop if we find a removed or free slot, or if we find the key itself
+ // do NOT skip over removed slots (yes, open addressing is like that...)
+ //int comp = comparisons;
+ int t = 0; // the number of probes
+ int p0 = i; // the first position to probe
+ while (stat[i] == FULL && tab[i] != key) {
+ t++;
+ i -= decrement;
+ //hashCollisions++;
+ if (i < 0) {
+ i += length;
+ }
+ }
+ if (stat[i] == FULL) {
+ // key already contained at slot i.
+ this.values[i] = value;
+ return false;
+ }
+ // not already contained, should be inserted at slot i.
+
+ if (this.distinct > this.highWaterMark) {
+ int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ return put(key, value);
+ }
+
+ /*
+ Brent's variation does a local reorganization to reduce probes. It essentially means:
+ We test whether it is possible to move the association we probed first (table[p0]) out of the way.
+ If this is possible, it will reduce probes for the key to be inserted, since it takes its place;
+ it gets hit earlier.
+ However, future probes for the key that we move out of the way will increase.
+ Thus we only move it out of the way, if we have a net gain, that is, if we save more probes than we loose.
+ For the first probe we safe more than we loose if the number of probes we needed was >=2 (t>=2).
+ If the first probe cannot be moved out of the way, we try the next probe (p1).
+ Now we safe more than we loose if t>=3.
+ We repeat this until we find that we cannot gain or that we can indeed move p(x) out of the way.
+
+ Note: Under the great majority of insertions t<=1, so the loop is entered very infrequently.
+ */
+ while (t > 1) {
+ int key0 = tab[p0];
+ hash = HashFunctions.hash(key0) & 0x7FFFFFFF;
+ decrement = (hash / length) % length;
+ if (decrement == 0) {
+ decrement = 1;
+ }
+ int pc = p0 - decrement; // pc = (p0-j*decrement) % M, j=1,2,..
+ if (pc < 0) {
+ pc += length;
+ }
+
+ if (stat[pc] != FREE) { // not a free slot, continue searching for free slot to move to, or break.
+ p0 = pc;
+ t--;
+ } else { // free or removed slot found, now move...
+ tab[pc] = key0;
+ stat[pc] = FULL;
+ values[pc] = values[p0];
+ i = p0; // prepare to insert: table[p0]=key
+ t = 0; // break loop
+ }
+ }
+
+ this.table[i] = key;
+ this.values[i] = value;
+ if (this.state[i] == FREE) {
+ this.freeEntries--;
+ }
+ this.state[i] = FULL;
+ this.distinct++;
+
+ if (this.freeEntries < 1) { //delta
+ int newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
+ rehash(newCapacity);
+ }
+
+ return true;
+ }
+
+ /**
+ * Rehashes the contents of the receiver into a new table with a smaller or larger capacity. This method is called
+ * automatically when the number of keys in the receiver exceeds the high water mark or falls below the low water
+ * mark.
+ */
+ @Override
+ protected void rehash(int newCapacity) {
+ int oldCapacity = table.length;
+ //if (oldCapacity == newCapacity) return;
+
+ int[] oldTable = table;
+ int[] oldValues = values;
+ byte[] oldState = state;
+
+ int[] newTable = new int[newCapacity];
+ int[] newValues = new int[newCapacity];
+ byte[] newState = new byte[newCapacity];
+
+ this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
+ this.highWaterMark = chooseHighWaterMark(newCapacity, this.maxLoadFactor);
+
+ this.table = newTable;
+ this.values = newValues;
+ this.state = newState;
+ this.freeEntries = newCapacity - this.distinct; // delta
+
+ int tmp = this.distinct;
+ this.distinct = Integer.MIN_VALUE; // switch of watermarks
+ for (int i = oldCapacity; i-- > 0;) {
+ if (oldState[i] == FULL) {
+ put(oldTable[i], oldValues[i]);
+ /*
+ int element = oldTable[i];
+ int index = indexOfInsertion(element);
+ newTable[index]=element;
+ newValues[index]=oldValues[i];
+ newState[index]=FULL;
+ */
+ }
+ }
+ this.distinct = tmp;
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/map/package-info.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/map/package-info.java b/core/src/main/java/org/apache/mahout/math/map/package-info.java
new file mode 100644
index 0000000..9356f45
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/map/package-info.java
@@ -0,0 +1,250 @@
+/**
+ * <HTML>
+ * <BODY>
+ * Automatically growing and shrinking maps holding objects or primitive
+ * data types such as <tt>int</tt>, <tt>double</tt>, etc. Currently all maps are
+ * based upon hashing.
+ * <h2><a name="Overview"></a>1. Overview</h2>
+ * <p>The map package offers flexible object oriented abstractions modelling automatically
+ * resizing maps. It is designed to be scalable in terms of performance and memory
+ * requirements.</p>
+ * <p>Features include: </p>
+ * <p></p>
+ * <ul>
+ * <li>Maps operating on objects as well as all primitive data types such as <code>int</code>,
+ * <code>double</code>, etc.
+ * </li>
+ * <li>Compact representations</li>
+ * <li>Support for quick access to associations</li>
+ * <li>A number of general purpose map operations</li>
+ * </ul>
+ * <p>File-based I/O can be achieved through the standard Java built-in serialization
+ * mechanism. All classes implement the {@link java.io.Serializable} interface.
+ * However, the toolkit is entirely decoupled from advanced I/O. It provides data
+ * structures and algorithms only.
+ * <p> This toolkit borrows some terminology from the Javasoft <a
+ * href="http://www.javasoft.com/products/jdk/1.2/docs/guide/collections/index.html">
+ * Collections framework</a> written by Josh Bloch and introduced in JDK 1.2.
+ * <h2>2. Introduction</h2>
+ * <p>A map is an associative container that manages a set of (key,value) pairs.
+ * It is useful for implementing a collection of one-to-one mappings. A (key,value)
+ * pair is called an <i>association</i>. A value can be looked up up via its key.
+ * Associations can quickly be set, removed and retrieved. They are stored in a
+ * hashing structure based on the hash code of their keys, which is obtained by
+ * using a hash function. </p>
+ * <p> A map can, for example, contain <tt>Name-->Location</tt> associations like
+ * <tt>{("Pete", "Geneva"), ("Steve", "Paris"), ("Robert", "New York")}</tt> used
+ * in address books or <tt>Index-->Value</tt> mappings like <tt>{(0, 100), (3,
+ * 1000), (100000, 70)}</tt> representing sparse lists or matrices. For example
+ * this could mean at index 0 we have a value of 100, at index 3 we have a value
+ * of 1000, at index 1000000 we have a value of 70, and at all other indexes we
+ * have a value of, say, zero. Another example is a map of IP addresses to domain
+ * names (DNS). Maps can also be useful to represent<i> multi sets</i>, that is,
+ * sets where elements can occur more than once. For multi sets one would have
+ * <tt>Value-->Frequency</tt> mappings like <tt>{(100, 1), (50, 1000), (101, 3))}</tt>
+ * meaning element 100 occurs 1 time, element 50 occurs 1000 times, element 101
+ * occurs 3 times. Further, maps can also manage <tt>ObjectIdentifier-->Object</tt>
+ * mappings like <tt>{(12, obj1), (7, obj2), (10000, obj3), (9, obj4)}</tt> used
+ * in Object Databases.
+ * <p> A map cannot contain two or more <i>equal</i> keys; a key can map to at most
+ * one value. However, more than one key can map to identical values. For primitive
+ * data types "equality" of keys is defined as identity (operator <tt>==</tt>).
+ * For maps using <tt>Object</tt> keys, the meaning of "equality" can be specified
+ * by the user upon instance construction. It can either be defined to be identity
+ * (operator <tt>==</tt>) or to be given by the method {@link java.lang.Object#equals(Object)}.
+ * Associations of kind <tt>(AnyType,Object)</tt> can be of the form <tt>(AnyKey,null)
+ * </tt>, i.e. values can be <tt>null</tt>.
+ * <p> The classes of this package make no guarantees as to the order of the elements
+ * returned by iterators; in particular, they do not guarantee that the order will
+ * remain constant over time.
+ * <h2></h2>
+ * <h4>Copying</h4>
+ * <p>
+ * <p>Any map can be copied. A copy is <i>equal</i> to the original but entirely
+ * independent of the original. So changes in the copy are not reflected in the
+ * original, and vice-versa.
+ * <h2>3. Package organization</h2>
+ * <p>For most primitive data types and for objects there exists a separate map version.
+ * All versions are just the same, except that they operate on different data types.
+ * Colt includes two kinds of implementations for maps: The two different implementations
+ * are tagged <b>Chained</b> and <b>Open</b>.
+ * Note: Chained is no more included. Wherever it is mentioned it is of historic interest only.</p>
+ * <ul>
+ * <li><b>Chained</b> uses extendible separate chaining with chains holding unsorted
+ * dynamically linked collision lists.
+ * <li><b>Open</b> uses extendible open addressing with double hashing.
+ * </ul>
+ * <p>Class naming follows the schema <tt><Implementation><KeyType><ValueType>HashMap</tt>.
+ * For example, a {@link org.apache.mahout.math.map.OpenIntDoubleHashMap} holds <tt>(int-->double)</tt>
+ * associations and is implemented with open addressing. A {@link org.apache.mahout.math.map.OpenIntObjectHashMap}
+ * holds <tt>(int-->Object)</tt> associations and is implemented with open addressing.
+ * </p>
+ * <p>The classes for maps of a given (key,value) type are derived from a common
+ * abstract base class tagged <tt>Abstract<KeyType><ValueType></tt><tt>Map</tt>.
+ * For example, all maps operating on <tt>(int-->double)</tt> associations are
+ * derived from {@link org.apache.mahout.math.map.AbstractIntDoubleMap}, which in turn is derived
+ * from an abstract base class tying together all maps regardless of assocation
+ * type, {@link org.apache.mahout.math.set.AbstractSet}. The abstract base classes provide skeleton
+ * implementations for all but few methods. Experimental layouts (such as chaining,
+ * open addressing, extensible hashing, red-black-trees, etc.) can easily be implemented
+ * and inherit a rich set of functionality. Have a look at the javadoc <a href="package-tree.html">tree
+ * view</a> to get the broad picture.</p>
+ * <h2>4. Example usage</h2>
+ * <TABLE>
+ * <TD CLASS="PRE">
+ * <PRE>
+ * int[] keys = {0 , 3 , 100000, 9 };
+ * double[] values = {100.0, 1000.0, 70.0 , 71.0};
+ * AbstractIntDoubleMap map = new OpenIntDoubleHashMap();
+ * // add several associations
+ * for (int i=0; i < keys.length; i++) map.put(keys[i], values[i]);
+ * log.info("map="+map);
+ * log.info("size="+map.size());
+ * log.info(map.containsKey(3));
+ * log.info("get(3)="+map.get(3));
+ * log.info(map.containsKey(4));
+ * log.info("get(4)="+map.get(4));
+ * log.info(map.containsValue(71.0));
+ * log.info("keyOf(71.0)="+map.keyOf(71.0));
+ * // remove one association
+ * map.removeKey(3);
+ * log.info("\nmap="+map);
+ * log.info(map.containsKey(3));
+ * log.info("get(3)="+map.get(3));
+ * log.info(map.containsValue(1000.0));
+ * log.info("keyOf(1000.0)="+map.keyOf(1000.0));
+ * // clear
+ * map.clear();
+ * log.info("\nmap="+map);
+ * log.info("size="+map.size());
+ * </PRE>
+ * </TD>
+ * </TABLE>
+ * yields the following output
+ * <TABLE>
+ * <TD CLASS="PRE">
+ * <PRE>
+ * map=[0->100.0, 3->1000.0, 9->71.0, 100000->70.0]
+ * size=4
+ * true
+ * get(3)=1000.0
+ * false
+ * get(4)=0.0
+ * true
+ * keyOf(71.0)=9
+ * map=[0->100.0, 9->71.0, 100000->70.0]
+ * false
+ * get(3)=0.0
+ * false
+ * keyOf(1000.0)=-2147483648
+ * map=[]
+ * size=0
+ * </PRE>
+ * </TD>
+ * </TABLE>
+ * <h2> 5. Notes </h2>
+ * <p>
+ * Note that implementations are not synchronized.
+ * <p>
+ * Choosing efficient parameters for hash maps is not always easy.
+ * However, since parameters determine efficiency and memory requirements, here is a quick guide how to choose them.
+ * If your use case does not heavily operate on hash maps but uses them just because they provide
+ * convenient functionality, you can safely skip this section.
+ * For those of you who care, read on.
+ * <p>
+ * There are three parameters that can be customized upon map construction: <tt>initialCapacity</tt>,
+ * <tt>minLoadFactor</tt> and <tt>maxLoadFactor</tt>.
+ * The more memory one can afford, the faster a hash map.
+ * The hash map's capacity is the maximum number of associations that can be added without needing to allocate new
+ * internal memory.
+ * A larger capacity means faster adding, searching and removing.
+ * The <tt>initialCapacity</tt> corresponds to the capacity used upon instance construction.
+ * <p>
+ * The <tt>loadFactor</tt> of a hash map measures the degree of "fullness".
+ * It is given by the number of assocations (<tt>size()</tt>)
+ * divided by the hash map capacity <tt>(0.0 <= loadFactor <= 1.0)</tt>.
+ * The more associations are added, the larger the loadFactor and the more hash map performance degrades.
+ * Therefore, when the loadFactor exceeds a customizable threshold (<tt>maxLoadFactor</tt>), the hash map is
+ * automatically grown.
+ * In such a way performance degradation can be avoided.
+ * Similarly, when the loadFactor falls below a customizable threshold (<tt>minLoadFactor</tt>), the hash map is
+ * automatically shrinked.
+ * In such a way excessive memory consumption can be avoided.
+ * Automatic resizing (both growing and shrinking) obeys the following invariant:
+ * <p>
+ * <tt>capacity * minLoadFactor <= size() <= capacity * maxLoadFactor</tt>
+ * <p> The term <tt>capacity * minLoadFactor</tt> is called the <i>low water mark</i>,
+ * <tt>capacity * maxLoadFactor</tt> is called the <i>high water mark</i>. In other
+ * words, the number of associations may vary within the water mark constraints.
+ * When it goes out of range, the map is automatically resized and memory consumption
+ * changes proportionally.
+ * <ul>
+ * <li>To tune for memory at the expense of performance, both increase <tt>minLoadFactor</tt> and
+ * <tt>maxLoadFactor</tt>.
+ * <li>To tune for performance at the expense of memory, both decrease <tt>minLoadFactor</tt> and
+ * <tt>maxLoadFactor</tt>.
+ * As as special case set <tt>minLoadFactor=0</tt> to avoid any automatic shrinking.
+ * </ul>
+ * Resizing large hash maps can be time consuming, <tt>O(size())</tt>, and should be avoided if possible (maintaining
+ * primes is not the reason).
+ * Unnecessary growing operations can be avoided if the number of associations is known before they are added, or can be
+ * estimated.<p>
+ * In such a case good parameters are as follows:
+ * <p>
+ * <i>For chaining:</i>
+ * <br>Set the <tt>initialCapacity = 1.4*expectedSize</tt> or greater.
+ * <br>Set the <tt>maxLoadFactor = 0.8</tt> or greater.
+ * <p>
+ * <i>For open addressing:</i>
+ * <br>Set the <tt>initialCapacity = 2*expectedSize</tt> or greater. Alternatively call <tt>ensureCapacity(...)</tt>.
+ * <br>Set the <tt>maxLoadFactor = 0.5</tt>.
+ * <br>Never set <tt>maxLoadFactor > 0.55</tt>; open addressing exponentially slows down beyond that point.
+ * <p>
+ * In this way the hash map will never need to grow and still stay fast.
+ * It is never a good idea to set <tt>maxLoadFactor < 0.1</tt>,
+ * because the hash map would grow too often.
+ * If it is entirelly unknown how many associations the application will use,
+ * the default constructor should be used. The map will grow and shrink as needed.
+ * <p>
+ * <b>Comparision of chaining and open addressing</b>
+ * <p> Chaining is faster than open addressing, when assuming unconstrained memory
+ * consumption. Open addressing is more space efficient than chaining, because
+ * it does not create entry objects but uses primitive arrays which are considerably
+ * smaller. Entry objects consume significant amounts of memory compared to the
+ * information they actually hold. Open addressing also poses no problems to the
+ * garbage collector. In contrast, chaining can create millions of entry objects
+ * which are linked; a nightmare for any garbage collector. In addition, entry
+ * object creation is a bit slow. <br>
+ * Therefore, with the same amount of memory, or even less memory, hash maps with
+ * larger capacity can be maintained under open addressing, which yields smaller
+ * loadFactors, which in turn keeps performance competitive with chaining. In our
+ * benchmarks, using significantly less memory, open addressing usually is not
+ * more than 1.2-1.5 times slower than chaining.
+ * <p><b>Further readings</b>:
+ * <br>Knuth D., The Art of Computer Programming: Searching and Sorting, 3rd ed.
+ * <br>Griswold W., Townsend G., The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon,
+ * Software - Practice and Experience, Vol. 23(4), 351-367 (April 1993).
+ * <br>Larson P., Dynamic hash tables, Comm. of the ACM, 31, (4), 1988.
+ * <p>
+ * <b>Performance:</b>
+ * <p>
+ * Time complexity:
+ * <br>The classes offer <i>expected</i> time complexity <tt>O(1)</tt> (i.e. constant time) for the basic operations
+ * <tt>put</tt>, <tt>get</tt>, <tt>removeKey</tt>, <tt>containsKey</tt> and <tt>size</tt>,
+ * assuming the hash function disperses the elements properly among the buckets.
+ * Otherwise, pathological cases, although highly improbable, can occur, degrading performance to <tt>O(N)</tt> in the
+ * worst case.
+ * Operations <tt>containsValue</tt> and <tt>keyOf</tt> are <tt>O(N)</tt>.
+ * <p>
+ * Memory requirements for <i>open addressing</i>:
+ * <br>worst case: <tt>memory [bytes] = (1/minLoadFactor) * size() * (1 + sizeOf(key) + sizeOf(value))</tt>.
+ * <br>best case: <tt>memory [bytes] = (1/maxLoadFactor) * size() * (1 + sizeOf(key) + sizeOf(value))</tt>.
+ * Where <tt>sizeOf(int) = 4</tt>, <tt>sizeOf(double) = 8</tt>, <tt>sizeOf(Object) = 4</tt>, etc.
+ * Thus, an <tt>OpenIntIntHashMap</tt> with minLoadFactor=0.25 and maxLoadFactor=0.5 and 1000000 associations uses
+ * between 17 MB and 34 MB.
+ * The same map with 1000 associations uses between 17 and 34 KB.
+ * <p>
+ * </BODY>
+ * </HTML>
+ */
+package org.apache.mahout.math.map;
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/package-info.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/package-info.java b/core/src/main/java/org/apache/mahout/math/package-info.java
new file mode 100644
index 0000000..de664f0
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/package-info.java
@@ -0,0 +1,4 @@
+/**
+ * Core base classes; Operations on primitive arrays such as sorting, partitioning and permuting.
+ */
+package org.apache.mahout.math;
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/random/AbstractSamplerFunction.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/random/AbstractSamplerFunction.java b/core/src/main/java/org/apache/mahout/math/random/AbstractSamplerFunction.java
new file mode 100644
index 0000000..d657fd9
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/random/AbstractSamplerFunction.java
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math.random;
+
+import org.apache.mahout.math.function.DoubleFunction;
+
+/**
+ * This shim allows samplers to be used to initialize vectors.
+ */
+public abstract class AbstractSamplerFunction extends DoubleFunction implements Sampler<Double> {
+ /**
+ * Apply the function to the argument and return the result
+ *
+ * @param ignored Ignored argument
+ * @return A sample from this distribution.
+ */
+ @Override
+ public double apply(double ignored) {
+ return sample();
+ }
+
+ @Override
+ public abstract Double sample();
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/random/ChineseRestaurant.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/random/ChineseRestaurant.java b/core/src/main/java/org/apache/mahout/math/random/ChineseRestaurant.java
new file mode 100644
index 0000000..8127b92
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/random/ChineseRestaurant.java
@@ -0,0 +1,111 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math.random;
+
+import com.google.common.base.Preconditions;
+import org.apache.mahout.common.RandomUtils;
+import org.apache.mahout.math.list.DoubleArrayList;
+
+import java.util.Random;
+
+/**
+ *
+ * Generates samples from a generalized Chinese restaurant process (or Pittman-Yor process).
+ *
+ * The number of values drawn exactly once will asymptotically be equal to the discount parameter
+ * as the total number of draws T increases without bound. The number of unique values sampled will
+ * increase as O(alpha * log T) if discount = 0 or O(alpha * T^discount) for discount > 0.
+ */
+public final class ChineseRestaurant implements Sampler<Integer> {
+
+ private final double alpha;
+ private double weight = 0;
+ private double discount = 0;
+ private final DoubleArrayList weights = new DoubleArrayList();
+ private final Random rand = RandomUtils.getRandom();
+
+ /**
+ * Constructs a Dirichlet process sampler. This is done by setting discount = 0.
+ * @param alpha The strength parameter for the Dirichlet process.
+ */
+ public ChineseRestaurant(double alpha) {
+ this(alpha, 0);
+ }
+
+ /**
+ * Constructs a Pitman-Yor sampler.
+ *
+ * @param alpha The strength parameter that drives the number of unique values as a function of draws.
+ * @param discount The discount parameter that drives the percentage of values that occur once in a large sample.
+ */
+ public ChineseRestaurant(double alpha, double discount) {
+ Preconditions.checkArgument(alpha > 0, "Strength Parameter, alpha must be greater then 0!");
+ Preconditions.checkArgument(discount >= 0 && discount <= 1, "Must be: 0 <= discount <= 1");
+ this.alpha = alpha;
+ this.discount = discount;
+ }
+
+ @Override
+ public Integer sample() {
+ double u = rand.nextDouble() * (alpha + weight);
+ for (int j = 0; j < weights.size(); j++) {
+ // select existing options with probability (w_j - d) / (alpha + w)
+ if (u < weights.get(j) - discount) {
+ weights.set(j, weights.get(j) + 1);
+ weight++;
+ return j;
+ } else {
+ u -= weights.get(j) - discount;
+ }
+ }
+
+ // if no existing item selected, pick new item with probability (alpha - d*t) / (alpha + w)
+ // where t is number of pre-existing cases
+ weights.add(1);
+ weight++;
+ return weights.size() - 1;
+ }
+
+ /**
+ * @return the number of unique values that have been returned.
+ */
+ public int size() {
+ return weights.size();
+ }
+
+ /**
+ * @return the number draws so far.
+ */
+ public int count() {
+ return (int) weight;
+ }
+
+ /**
+ * @param j Which value to test.
+ * @return The number of times that j has been returned so far.
+ */
+ public int count(int j) {
+ Preconditions.checkArgument(j >= 0);
+
+ if (j < weights.size()) {
+ return (int) weights.get(j);
+ } else {
+ return 0;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/random/Empirical.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/random/Empirical.java b/core/src/main/java/org/apache/mahout/math/random/Empirical.java
new file mode 100644
index 0000000..78bfec5
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/random/Empirical.java
@@ -0,0 +1,124 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math.random;
+
+import com.google.common.base.Preconditions;
+import org.apache.mahout.common.RandomUtils;
+
+import java.util.Random;
+
+/**
+ * Samples from an empirical cumulative distribution.
+ */
+public final class Empirical extends AbstractSamplerFunction {
+ private final Random gen;
+ private final boolean exceedMinimum;
+ private final boolean exceedMaximum;
+
+ private final double[] x;
+ private final double[] y;
+ private final int n;
+
+ /**
+ * Sets up a sampler for a specified empirical cumulative distribution function. The distribution
+ * can have optional exponential tails on either or both ends, but otherwise does a linear
+ * interpolation between known points.
+ *
+ * @param exceedMinimum Should we generate samples less than the smallest quantile (i.e. generate a left tail)?
+ * @param exceedMaximum Should we generate samples greater than the largest observed quantile (i.e. generate a right
+ * tail)?
+ * @param samples The number of samples observed to get the quantiles.
+ * @param ecdf Alternating values that represent which percentile (in the [0..1] range)
+ * and values. For instance, if you have the min, median and max of 1, 3, 10
+ * you should pass 0.0, 1, 0.5, 3, 1.0, 10. Note that the list must include
+ * the 0-th (1.0-th) quantile if the left (right) tail is not allowed.
+ */
+ public Empirical(boolean exceedMinimum, boolean exceedMaximum, int samples, double... ecdf) {
+ Preconditions.checkArgument(ecdf.length % 2 == 0, "ecdf must have an even count of values");
+ Preconditions.checkArgument(samples >= 3, "Sample size must be >= 3");
+
+ // if we can't exceed the observed bounds, then we have to be given the bounds.
+ Preconditions.checkArgument(exceedMinimum || ecdf[0] == 0);
+ Preconditions.checkArgument(exceedMaximum || ecdf[ecdf.length - 2] == 1);
+
+ gen = RandomUtils.getRandom();
+
+ n = ecdf.length / 2;
+ x = new double[n];
+ y = new double[n];
+
+ double lastX = ecdf[1];
+ double lastY = ecdf[0];
+ for (int i = 0; i < ecdf.length; i += 2) {
+ // values have to be monotonic increasing
+ Preconditions.checkArgument(i == 0 || ecdf[i + 1] > lastY);
+ y[i / 2] = ecdf[i + 1];
+ lastY = y[i / 2];
+
+ // quantiles have to be in [0,1] and be monotonic increasing
+ Preconditions.checkArgument(ecdf[i] >= 0 && ecdf[i] <= 1);
+ Preconditions.checkArgument(i == 0 || ecdf[i] > lastX);
+
+ x[i / 2] = ecdf[i];
+ lastX = x[i / 2];
+ }
+
+ // squeeze a bit to allow for unobserved tails
+ double x0 = exceedMinimum ? 0.5 / samples : 0;
+ double x1 = 1 - (exceedMaximum ? 0.5 / samples : 0);
+ for (int i = 0; i < n; i++) {
+ x[i] = x[i] * (x1 - x0) + x0;
+ }
+
+ this.exceedMinimum = exceedMinimum;
+ this.exceedMaximum = exceedMaximum;
+ }
+
+ @Override
+ public Double sample() {
+ return sample(gen.nextDouble());
+ }
+
+ public double sample(double u) {
+ if (exceedMinimum && u < x[0]) {
+ // generate from left tail
+ if (u == 0) {
+ u = 1.0e-16;
+ }
+ return y[0] + Math.log(u / x[0]) * x[0] * (y[1] - y[0]) / (x[1] - x[0]);
+ } else if (exceedMaximum && u > x[n - 1]) {
+ if (u == 1) {
+ u = 1 - 1.0e-16;
+ }
+ // generate from right tail
+ double dy = y[n - 1] - y[n - 2];
+ double dx = x[n - 1] - x[n - 2];
+ return y[n - 1] - Math.log((1 - u) / (1 - x[n - 1])) * (1 - x[n - 1]) * dy / dx;
+ } else {
+ // linear interpolation
+ for (int i = 1; i < n; i++) {
+ if (x[i] > u) {
+ double dy = y[i] - y[i - 1];
+ double dx = x[i] - x[i - 1];
+ return y[i - 1] + (u - x[i - 1]) * dy / dx;
+ }
+ }
+ throw new RuntimeException(String.format("Can't happen (%.3f is not in [%.3f,%.3f]", u, x[0], x[n - 1]));
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/random/IndianBuffet.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/random/IndianBuffet.java b/core/src/main/java/org/apache/mahout/math/random/IndianBuffet.java
new file mode 100644
index 0000000..27b5d84
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/random/IndianBuffet.java
@@ -0,0 +1,157 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math.random;
+
+import com.google.common.base.CharMatcher;
+import com.google.common.base.Charsets;
+import com.google.common.base.Splitter;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.common.io.LineProcessor;
+import com.google.common.io.Resources;
+import org.apache.mahout.common.RandomUtils;
+
+import java.io.IOException;
+import java.util.List;
+import java.util.Random;
+
+/**
+ * Samples a "document" from an IndianBuffet process.
+ *
+ * See http://mlg.eng.cam.ac.uk/zoubin/talks/turin09.pdf for details
+ */
+public final class IndianBuffet<T> implements Sampler<List<T>> {
+ private final List<Integer> count = Lists.newArrayList();
+ private int documents = 0;
+ private final double alpha;
+ private WordFunction<T> converter = null;
+ private final Random gen;
+
+ public IndianBuffet(double alpha, WordFunction<T> converter) {
+ this.alpha = alpha;
+ this.converter = converter;
+ gen = RandomUtils.getRandom();
+ }
+
+ public static IndianBuffet<Integer> createIntegerDocumentSampler(double alpha) {
+ return new IndianBuffet<>(alpha, new IdentityConverter());
+ }
+
+ public static IndianBuffet<String> createTextDocumentSampler(double alpha) {
+ return new IndianBuffet<>(alpha, new WordConverter());
+ }
+
+ @Override
+ public List<T> sample() {
+ List<T> r = Lists.newArrayList();
+ if (documents == 0) {
+ double n = new PoissonSampler(alpha).sample();
+ for (int i = 0; i < n; i++) {
+ r.add(converter.convert(i));
+ count.add(1);
+ }
+ documents++;
+ } else {
+ documents++;
+ int i = 0;
+ for (double cnt : count) {
+ if (gen.nextDouble() < cnt / documents) {
+ r.add(converter.convert(i));
+ count.set(i, count.get(i) + 1);
+ }
+ i++;
+ }
+ int newItems = new PoissonSampler(alpha / documents).sample().intValue();
+ for (int j = 0; j < newItems; j++) {
+ r.add(converter.convert(i + j));
+ count.add(1);
+ }
+ }
+ return r;
+ }
+
+ private interface WordFunction<T> {
+ T convert(int i);
+ }
+
+ /**
+ * Just converts to an integer.
+ */
+ public static class IdentityConverter implements WordFunction<Integer> {
+ @Override
+ public Integer convert(int i) {
+ return i;
+ }
+ }
+
+ /**
+ * Converts to a string.
+ */
+ public static class StringConverter implements WordFunction<String> {
+ @Override
+ public String convert(int i) {
+ return String.valueOf(i);
+ }
+ }
+
+ /**
+ * Converts to one of a list of common English words for reasonably small integers and converts
+ * to a token like w_92463 for big integers.
+ */
+ public static final class WordConverter implements WordFunction<String> {
+ private final Splitter onSpace = Splitter.on(CharMatcher.WHITESPACE).omitEmptyStrings().trimResults();
+ private final List<String> words;
+
+ public WordConverter() {
+ try {
+ words = Resources.readLines(Resources.getResource("words.txt"), Charsets.UTF_8,
+ new LineProcessor<List<String>>() {
+ private final List<String> theWords = Lists.newArrayList();
+
+ @Override
+ public boolean processLine(String line) {
+ Iterables.addAll(theWords, onSpace.split(line));
+ return true;
+ }
+
+ @Override
+ public List<String> getResult() {
+ return theWords;
+ }
+ });
+ } catch (IOException e) {
+ throw new ImpossibleException(e);
+ }
+ }
+
+ @Override
+ public String convert(int i) {
+ if (i < words.size()) {
+ return words.get(i);
+ } else {
+ return "w_" + i;
+ }
+ }
+ }
+
+ public static class ImpossibleException extends RuntimeException {
+ public ImpossibleException(Throwable e) {
+ super(e);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/random/Missing.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/random/Missing.java b/core/src/main/java/org/apache/mahout/math/random/Missing.java
new file mode 100644
index 0000000..8141a71
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/random/Missing.java
@@ -0,0 +1,59 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math.random;
+
+import java.util.Random;
+
+import org.apache.mahout.common.RandomUtils;
+
+/**
+ * Models data with missing values. Note that all variables with the same fraction of missing
+ * values will have the same sequence of missing values. Similarly, if two variables have
+ * missing probabilities of p1 > p2, then all of the p2 missing values will also be missing for
+ * p1.
+ */
+public final class Missing<T> implements Sampler<T> {
+ private final Random gen;
+ private final double p;
+ private final Sampler<T> delegate;
+ private final T missingMarker;
+
+ public Missing(int seed, double p, Sampler<T> delegate, T missingMarker) {
+ this.p = p;
+ this.delegate = delegate;
+ this.missingMarker = missingMarker;
+ gen = RandomUtils.getRandom(seed);
+ }
+
+ public Missing(double p, Sampler<T> delegate, T missingMarker) {
+ this(1, p, delegate, missingMarker);
+ }
+
+ public Missing(double p, Sampler<T> delegate) {
+ this(1, p, delegate, null);
+ }
+
+ @Override
+ public T sample() {
+ if (gen.nextDouble() >= p) {
+ return delegate.sample();
+ } else {
+ return missingMarker;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/mahout/blob/545648f6/core/src/main/java/org/apache/mahout/math/random/MultiNormal.java
----------------------------------------------------------------------
diff --git a/core/src/main/java/org/apache/mahout/math/random/MultiNormal.java b/core/src/main/java/org/apache/mahout/math/random/MultiNormal.java
new file mode 100644
index 0000000..748d4e8
--- /dev/null
+++ b/core/src/main/java/org/apache/mahout/math/random/MultiNormal.java
@@ -0,0 +1,118 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.math.random;
+
+import org.apache.mahout.common.RandomUtils;
+import org.apache.mahout.math.DenseVector;
+import org.apache.mahout.math.DiagonalMatrix;
+import org.apache.mahout.math.Matrix;
+import org.apache.mahout.math.Vector;
+import org.apache.mahout.math.function.DoubleFunction;
+
+import java.util.Random;
+
+/**
+ * Samples from a multi-variate normal distribution.
+ * <p/>
+ * This is done by sampling from several independent unit normal distributions to get a vector u.
+ * The sample value that is returned is then A u + m where A is derived from the covariance matrix
+ * and m is the mean of the result.
+ * <p/>
+ * If \Sigma is the desired covariance matrix, then you can use any value of A such that A' A =
+ * \Sigma. The Cholesky decomposition can be used to compute A if \Sigma is positive definite.
+ * Slightly more expensive is to use the SVD U S V' = \Sigma and then set A = U \sqrt{S}.
+ *
+ * Useful special cases occur when \Sigma is diagonal so that A = \sqrt(\Sigma) or where \Sigma = r I.
+ *
+ * Another special case is where m = 0.
+ */
+public class MultiNormal implements Sampler<Vector> {
+ private final Random gen;
+ private final int dimension;
+ private final Matrix scale;
+ private final Vector mean;
+
+ /**
+ * Constructs a sampler with diagonal scale matrix.
+ * @param diagonal The diagonal elements of the scale matrix.
+ */
+ public MultiNormal(Vector diagonal) {
+ this(new DiagonalMatrix(diagonal), null);
+ }
+
+ /**
+ * Constructs a sampler with diagonal scale matrix and (potentially)
+ * non-zero mean.
+ * @param diagonal The scale matrix's principal diagonal.
+ * @param mean The desired mean. Set to null if zero mean is desired.
+ */
+ public MultiNormal(Vector diagonal, Vector mean) {
+ this(new DiagonalMatrix(diagonal), mean);
+ }
+
+ /**
+ * Constructs a sampler with non-trivial scale matrix and mean.
+ */
+ public MultiNormal(Matrix a, Vector mean) {
+ this(a, mean, a.columnSize());
+ }
+
+ public MultiNormal(int dimension) {
+ this(null, null, dimension);
+ }
+
+ public MultiNormal(double radius, Vector mean) {
+ this(new DiagonalMatrix(radius, mean.size()), mean);
+ }
+
+ private MultiNormal(Matrix scale, Vector mean, int dimension) {
+ gen = RandomUtils.getRandom();
+ this.dimension = dimension;
+ this.scale = scale;
+ this.mean = mean;
+ }
+
+ @Override
+ public Vector sample() {
+ Vector v = new DenseVector(dimension).assign(
+ new DoubleFunction() {
+ @Override
+ public double apply(double ignored) {
+ return gen.nextGaussian();
+ }
+ }
+ );
+ if (mean != null) {
+ if (scale != null) {
+ return scale.times(v).plus(mean);
+ } else {
+ return v.plus(mean);
+ }
+ } else {
+ if (scale != null) {
+ return scale.times(v);
+ } else {
+ return v;
+ }
+ }
+ }
+
+ public Vector getScale() {
+ return mean;
+ }
+}