Author: srowen
Date: Tue Nov 4 08:11:01 2008
New Revision: 711286
URL: http://svn.apache.org/viewvc?rev=711286&view=rev
Log:
Added FastSet and used it to reduce memory usage
Added:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastSet.java
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastSetTest.java
(contents, props changed)
- copied, changed from r710031,
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastMapTest.java
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RefreshHelper.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/eval/GenericRecommenderIRStatsEvaluator.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericDataModel.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/AbstractRecommender.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericItemBasedRecommender.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericUserBasedRecommender.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/MemoryDiffStorage.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/jdbc/AbstractJDBCDiffStorage.java
Added:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastSet.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastSet.java?rev=711286&view=auto
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastSet.java
(added)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastSet.java
Tue Nov 4 08:11:01 2008
@@ -0,0 +1,308 @@
+/**
+ * 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.cf.taste.impl.common;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.lang.reflect.Array;
+
+/**
+ * <p>This is an optimized [EMAIL PROTECTED] Set} implementation, based on
algorithms described in Knuth's
+ * "Art of Computer Programming", Vol. 3, p. 529.</p>
+ *
+ * <p>It should be faster than [EMAIL PROTECTED] java.util.HashSet} in some
cases, but not all. It should definitely
+ * be more memory efficient since that implementation is actually just a
[EMAIL PROTECTED] java.util.HashMap} underneath
+ * mapping values to a dummy object.</p>
+ *
+ * <p>This class is not a bit thread-safe.</p>
+ *
+ * <p>This implementation does not allow <code>null</code> as a key.</p>
+ *
+ * @see FastMap
+ */
+public final class FastSet<K> implements Set<K> {
+
+ /**
+ * Dummy object used to represent a key that has been removed.
+ */
+ private static final Object REMOVED = new Object();
+
+ private K[] keys;
+ private int numEntries;
+ private int numSlotsUsed;
+
+ /**
+ * Creates a new [EMAIL PROTECTED] FastSet} with default capacity.
+ */
+ public FastSet() {
+ this(11);
+ }
+
+ public FastSet(Collection<? extends K> c) {
+ this(c.size());
+ addAll(c);
+ }
+
+ @SuppressWarnings("unchecked")
+ public FastSet(int size) {
+ if (size < 1) {
+ throw new IllegalArgumentException("size must be at least 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));
+ }
+ int hashSize = RandomUtils.nextTwinPrime(2 * size);
+ keys = (K[]) new Object[hashSize];
+ }
+
+ /**
+ * This is for the benefit of inner classes. Without it the compiler would
just generate a similar synthetic
+ * accessor. Might as well make it explicit.
+ */
+ K[] getKeys() {
+ return keys;
+ }
+
+ private int find(Object key) {
+ int theHashCode = key.hashCode() & 0x7FFFFFFF; // make sure it's positive
+ K[] keys = this.keys;
+ int hashSize = keys.length;
+ int jump = 1 + theHashCode % (hashSize - 2);
+ int index = theHashCode % hashSize;
+ K currentKey = keys[index];
+ while (currentKey != null && (currentKey == REMOVED ||
!key.equals(currentKey))) {
+ if (index < jump) {
+ index += hashSize - jump;
+ } else {
+ index -= jump;
+ }
+ currentKey = keys[index];
+ }
+ return index;
+ }
+
+ public int size() {
+ return numEntries;
+ }
+
+ public boolean isEmpty() {
+ return numEntries == 0;
+ }
+
+ public boolean contains(Object key) {
+ return key != null && keys[find(key)] != null;
+ }
+
+ /**
+ * @throws NullPointerException if key is null
+ */
+ public boolean add(K key) {
+ if (key == null) {
+ throw new NullPointerException();
+ }
+ int hashSize = keys.length;
+ if (numSlotsUsed >= hashSize >> 1) {
+ growAndRehash();
+ }
+ // Here we may later consider implementing Brent's variation described on
page 532
+ int index = find(key);
+ if (keys[index] == null) {
+ keys[index] = key;
+ numEntries++;
+ numSlotsUsed++;
+ return true;
+ }
+ return false;
+ }
+
+ public Iterator<K> iterator() {
+ return new KeyIterator();
+ }
+
+ public boolean remove(Object key) {
+ if (key == null) {
+ return false;
+ }
+ int index = find(key);
+ if (keys[index] == null) {
+ return false;
+ } else {
+ ((Object[]) keys)[index] = REMOVED;
+ numEntries--;
+ return true;
+ }
+ // Could un-set recentlyAccessed's bit but doesn't matter
+ }
+
+ public boolean containsAll(Collection<?> c) {
+ for (Object o : c) {
+ if (o == null || keys[find(o)] == null) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public boolean addAll(Collection<? extends K> c) {
+ boolean changed = false;
+ for (K k : c) {
+ if (add(k)) {
+ changed = true;
+ }
+ }
+ return changed;
+ }
+
+ public boolean retainAll(Collection<?> c) {
+ boolean changed = false;
+ Iterator<K> iterator = iterator();
+ while (iterator.hasNext()) {
+ K k = iterator.next();
+ if (!c.contains(k)) {
+ iterator.remove();
+ changed = true;
+ }
+ }
+ return changed;
+ }
+
+ public boolean removeAll(Collection<?> c) {
+ boolean changed = false;
+ for (Object o : c) {
+ if (remove(o)) {
+ changed = true;
+ }
+ }
+ return changed;
+ }
+
+ public void clear() {
+ numEntries = 0;
+ numSlotsUsed = 0;
+ Arrays.fill(keys, null);
+ }
+
+ public Object[] toArray() {
+ return toArray(new Object[numEntries]);
+ }
+
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ if (a.length < numEntries) {
+ a = (T[]) Array.newInstance(a.getClass().getComponentType(), numEntries);
+ }
+ int keyOffset = 0;
+ int resultOffset = 0;
+ while (resultOffset < a.length) {
+ K key = keys[keyOffset++];
+ if (key != null && key != REMOVED) {
+ a[resultOffset++] = (T) key;
+ }
+ }
+ return a;
+ }
+
+ private void growAndRehash() {
+ int hashSize = keys.length;
+ if (hashSize >= RandomUtils.MAX_INT_SMALLER_TWIN_PRIME >> 1) {
+ throw new IllegalStateException("Can't grow any more");
+ }
+ rehash(RandomUtils.nextTwinPrime(2 * hashSize));
+ }
+
+ public void rehash() {
+ rehash(keys.length);
+ }
+
+ @SuppressWarnings("unchecked")
+ private void rehash(int newHashSize) {
+ K[] oldKeys = keys;
+ numEntries = 0;
+ numSlotsUsed = 0;
+ keys = (K[]) new Object[newHashSize];
+ int length = oldKeys.length;
+ for (int i = 0; i < length; i++) {
+ K key = oldKeys[i];
+ if (key != null && key != REMOVED) {
+ add(key);
+ }
+ }
+ }
+
+ /**
+ * Convenience method to quickly compute just the size of the intersection
with another [EMAIL PROTECTED] FastSet}.
+ */
+ @SuppressWarnings("unchecked")
+ public int intersectionSize(FastSet other) {
+ int count = 0;
+ K[] otherKeys = (K[]) other.keys;
+ for (int i = 0; i < otherKeys.length; i++) {
+ K key = otherKeys[i];
+ if (key != null && key != REMOVED && keys[find(key)] != null) {
+ count++;
+ }
+ }
+ return count;
+ }
+
+ private final class KeyIterator implements Iterator<K> {
+
+ private int position;
+ private int lastNext = -1;
+
+ public boolean hasNext() {
+ goToNext();
+ return position < getKeys().length;
+ }
+
+ public K next() {
+ goToNext();
+ lastNext = position;
+ K[] keys = getKeys();
+ if (position >= keys.length) {
+ throw new NoSuchElementException();
+ }
+ return keys[position++];
+ }
+
+ private void goToNext() {
+ K[] keys = getKeys();
+ int length = keys.length;
+ while (position < length && (keys[position] == null || keys[position] ==
REMOVED)) {
+ position++;
+ }
+ }
+
+ public void remove() {
+ if (lastNext >= keys.length) {
+ throw new NoSuchElementException();
+ }
+ if (lastNext < 0) {
+ throw new IllegalStateException();
+ }
+ ((Object[]) keys)[lastNext] = REMOVED;
+ numEntries--;
+ }
+
+ }
+
+
+}
\ No newline at end of file
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RefreshHelper.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RefreshHelper.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RefreshHelper.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/RefreshHelper.java
Tue Nov 4 08:11:01 2008
@@ -23,7 +23,6 @@
import java.util.ArrayList;
import java.util.Collection;
-import java.util.HashSet;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.locks.ReentrantLock;
@@ -73,7 +72,7 @@
}
public static Collection<Refreshable> buildRefreshed(Collection<Refreshable>
currentAlreadyRefreshed) {
- return currentAlreadyRefreshed == null ? new HashSet<Refreshable>(3) :
currentAlreadyRefreshed;
+ return currentAlreadyRefreshed == null ? new FastSet<Refreshable>(3) :
currentAlreadyRefreshed;
}
public static void maybeRefresh(Collection<Refreshable> alreadyRefreshed,
Refreshable refreshable) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/eval/GenericRecommenderIRStatsEvaluator.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/eval/GenericRecommenderIRStatsEvaluator.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/eval/GenericRecommenderIRStatsEvaluator.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/eval/GenericRecommenderIRStatsEvaluator.java
Tue Nov 4 08:11:01 2008
@@ -26,6 +26,7 @@
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
import org.apache.mahout.cf.taste.impl.common.RunningAverageAndStdDev;
import org.apache.mahout.cf.taste.impl.common.FullRunningAverageAndStdDev;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.impl.model.GenericDataModel;
import org.apache.mahout.cf.taste.impl.model.GenericUser;
import org.apache.mahout.cf.taste.model.DataModel;
@@ -40,7 +41,6 @@
import java.util.ArrayList;
import java.util.Collection;
-import java.util.HashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;
@@ -99,7 +99,7 @@
for (User user : dataModel.getUsers()) {
if (random.nextDouble() < evaluationPercentage) {
Object id = user.getID();
- Collection<Item> relevantItems = new HashSet<Item>(at);
+ Collection<Item> relevantItems = new FastSet<Item>(at);
Preference[] prefs = user.getPreferencesAsArray();
double theRelevanceThreshold;
if (Double.isNaN(relevanceThreshold)) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericDataModel.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericDataModel.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericDataModel.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericDataModel.java
Tue Nov 4 08:11:01 2008
@@ -22,6 +22,7 @@
import org.apache.mahout.cf.taste.impl.common.ArrayIterator;
import org.apache.mahout.cf.taste.impl.common.EmptyIterable;
import org.apache.mahout.cf.taste.impl.common.FastMap;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.Preference;
@@ -32,7 +33,6 @@
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
@@ -183,11 +183,11 @@
if (prefs1 == null || prefs2 == null) {
return 0;
}
- Set<Object> users1 = new HashSet<Object>(prefs1.length);
+ Set<Object> users1 = new FastSet<Object>(prefs1.length);
for (int i = 0; i < prefs1.length; i++) {
users1.add(prefs1[i].getUser().getID());
}
- Set<Object> users2 = new HashSet<Object>(prefs2.length);
+ Set<Object> users2 = new FastSet<Object>(prefs2.length);
for (int i = 0; i < prefs2.length; i++) {
users2.add(prefs2[i].getUser().getID());
}
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/AbstractRecommender.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/AbstractRecommender.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/AbstractRecommender.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/AbstractRecommender.java
Tue Nov 4 08:11:01 2008
@@ -23,10 +23,10 @@
import org.apache.mahout.cf.taste.model.User;
import org.apache.mahout.cf.taste.recommender.RecommendedItem;
import org.apache.mahout.cf.taste.recommender.Recommender;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.HashSet;
import java.util.List;
import java.util.Set;
@@ -98,7 +98,7 @@
if (theUser == null) {
throw new IllegalArgumentException("theUser is null");
}
- Set<Item> allItems = new HashSet<Item>(dataModel.getNumItems());
+ Set<Item> allItems = new FastSet<Item>(dataModel.getNumItems());
for (Item item : dataModel.getItems()) {
// If not already preferred by the user, add it
if (theUser.getPreferenceFor(item.getID()) == null) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericItemBasedRecommender.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericItemBasedRecommender.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericItemBasedRecommender.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericItemBasedRecommender.java
Tue Nov 4 08:11:01 2008
@@ -24,6 +24,7 @@
import org.apache.mahout.cf.taste.impl.common.Pair;
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.Preference;
@@ -37,7 +38,6 @@
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.List;
import java.util.Set;
@@ -146,7 +146,7 @@
toItems.add(model.getItem(itemID));
}
TopItems.Estimator<Item> estimator = new
MultiMostSimilarEstimator(toItems, similarity, rescorer);
- Collection<Item> allItems = new HashSet<Item>(model.getNumItems());
+ Collection<Item> allItems = new FastSet<Item>(model.getNumItems());
for (Item item : model.getItems()) {
allItems.add(item);
}
@@ -174,7 +174,7 @@
Item recommendedItem = model.getItem(itemID);
TopItems.Estimator<Item> estimator = new RecommendedBecauseEstimator(user,
recommendedItem, similarity);
- Collection<Item> allUserItems = new HashSet<Item>();
+ Collection<Item> allUserItems = new FastSet<Item>();
Preference[] prefs = user.getPreferencesAsArray();
for (int i = 0; i < prefs.length; i++) {
allUserItems.add(prefs[i].getItem());
@@ -189,7 +189,7 @@
TopItems.Estimator<Item>
estimator) throws TasteException {
DataModel model = getDataModel();
Item toItem = model.getItem(itemID);
- Collection<Item> allItems = new HashSet<Item>(model.getNumItems());
+ Collection<Item> allItems = new FastSet<Item>(model.getNumItems());
for (Item item : model.getItems()) {
allItems.add(item);
}
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericUserBasedRecommender.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericUserBasedRecommender.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericUserBasedRecommender.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/GenericUserBasedRecommender.java
Tue Nov 4 08:11:01 2008
@@ -22,6 +22,7 @@
import org.apache.mahout.cf.taste.similarity.UserSimilarity;
import org.apache.mahout.cf.taste.impl.common.Pair;
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.Preference;
@@ -36,7 +37,6 @@
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.List;
import java.util.Set;
@@ -132,7 +132,7 @@
TopItems.Estimator<User> estimator)
throws TasteException {
DataModel model = getDataModel();
User toUser = model.getUser(userID);
- Collection<User> allUsers = new HashSet<User>(model.getNumUsers());
+ Collection<User> allUsers = new FastSet<User>(model.getNumUsers());
for (User user : model.getUsers()) {
allUsers.add(user);
}
@@ -164,7 +164,7 @@
}
private static Set<Item> getAllOtherItems(Iterable<User> theNeighborhood,
User theUser) {
- Set<Item> allItems = new HashSet<Item>();
+ Set<Item> allItems = new FastSet<Item>();
for (User user : theNeighborhood) {
Preference[] prefs = user.getPreferencesAsArray();
for (int i = 0; i < prefs.length; i++) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java
Tue Nov 4 08:11:01 2008
@@ -25,6 +25,7 @@
import org.apache.mahout.cf.taste.impl.common.RandomUtils;
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.Preference;
@@ -38,7 +39,6 @@
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
@@ -278,7 +278,7 @@
} else {
// Begin with a cluster for each user:
for (User user : model.getUsers()) {
- Collection<User> newCluster = new HashSet<User>();
+ Collection<User> newCluster = new FastSet<User>();
newCluster.add(user);
newClusters.add(newCluster);
}
@@ -307,7 +307,7 @@
while (clusterSimilarity.getSimilarity(cluster1, cluster2) >=
clusteringThreshold) {
newClusters.remove(cluster1);
newClusters.remove(cluster2);
- Collection<User> merged = new HashSet<User>(cluster1.size() +
cluster2.size());
+ Collection<User> merged = new FastSet<User>(cluster1.size() +
cluster2.size());
merged.addAll(cluster1);
merged.addAll(cluster2);
newClusters.add(merged);
@@ -330,7 +330,7 @@
Collection<User> cluster2 = nearestPair.getSecond();
newClusters.remove(cluster1);
newClusters.remove(cluster2);
- Collection<User> merged = new HashSet<User>(cluster1.size() +
cluster2.size());
+ Collection<User> merged = new FastSet<User>(cluster1.size() +
cluster2.size());
merged.addAll(cluster1);
merged.addAll(cluster2);
newClusters.add(merged);
@@ -375,7 +375,7 @@
private static List<RecommendedItem>
computeTopRecsForCluster(Collection<User> cluster)
throws TasteException {
- Collection<Item> allItems = new HashSet<Item>();
+ Collection<Item> allItems = new FastSet<Item>();
for (User user : cluster) {
Preference[] prefs = user.getPreferencesAsArray();
for (int i = 0; i < prefs.length; i++) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java
Tue Nov 4 08:11:01 2008
@@ -24,6 +24,7 @@
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
import org.apache.mahout.cf.taste.impl.common.RandomUtils;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.Preference;
@@ -37,7 +38,6 @@
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
@@ -303,7 +303,7 @@
List<Collection<User>> clusters = new LinkedList<Collection<User>>();
// Begin with a cluster for each user:
for (User user : model.getUsers()) {
- Collection<User> newCluster = new HashSet<User>();
+ Collection<User> newCluster = new FastSet<User>();
newCluster.add(user);
clusters.add(newCluster);
}
@@ -381,7 +381,7 @@
}
// Make new merged cluster
- Collection<User> merged = new HashSet<User>(cluster1.size() +
cluster2.size());
+ Collection<User> merged = new FastSet<User>(cluster1.size() +
cluster2.size());
merged.addAll(cluster1);
merged.addAll(cluster2);
@@ -458,7 +458,7 @@
private static List<RecommendedItem>
computeTopRecsForCluster(Collection<User> cluster)
throws TasteException {
- Collection<Item> allItems = new HashSet<Item>();
+ Collection<Item> allItems = new FastSet<Item>();
for (User user : cluster) {
Preference[] prefs = user.getPreferencesAsArray();
for (int i = 0; i < prefs.length; i++) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/MemoryDiffStorage.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/MemoryDiffStorage.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/MemoryDiffStorage.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/MemoryDiffStorage.java
Tue Nov 4 08:11:01 2008
@@ -28,6 +28,7 @@
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
import org.apache.mahout.cf.taste.impl.common.RunningAverageAndStdDev;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.Preference;
@@ -37,7 +38,6 @@
import org.slf4j.LoggerFactory;
import java.util.Collection;
-import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
@@ -196,7 +196,7 @@
public Set<Item> getRecommendableItems(Object userID) throws TasteException {
User user = dataModel.getUser(userID);
- Set<Item> result = new HashSet<Item>(dataModel.getNumItems());
+ Set<Item> result = new FastSet<Item>(dataModel.getNumItems());
for (Item item : dataModel.getItems()) {
// If not already preferred by the user, add it
if (user.getPreferenceFor(item.getID()) == null) {
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/jdbc/AbstractJDBCDiffStorage.java
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/jdbc/AbstractJDBCDiffStorage.java?rev=711286&r1=711285&r2=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/jdbc/AbstractJDBCDiffStorage.java
(original)
+++
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/slopeone/jdbc/AbstractJDBCDiffStorage.java
Tue Nov 4 08:11:01 2008
@@ -22,6 +22,7 @@
import org.apache.mahout.cf.taste.impl.common.IOUtils;
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
+import org.apache.mahout.cf.taste.impl.common.FastSet;
import org.apache.mahout.cf.taste.model.Item;
import org.apache.mahout.cf.taste.model.JDBCDataModel;
import org.apache.mahout.cf.taste.model.Preference;
@@ -35,7 +36,6 @@
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.Collection;
-import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.Callable;
@@ -249,7 +249,7 @@
stmt.setObject(3, userID);
log.debug("Executing SQL query: {}", getRecommendableItemsSQL);
rs = stmt.executeQuery();
- Set<Item> items = new HashSet<Item>();
+ Set<Item> items = new FastSet<Item>();
while (rs.next()) {
items.add(dataModel.getItem(rs.getObject(1), true));
}
Copied:
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastSetTest.java
(from r710031,
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastMapTest.java)
URL:
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastSetTest.java?p2=lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastSetTest.java&p1=lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastMapTest.java&r1=710031&r2=711286&rev=711286&view=diff
==============================================================================
---
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastMapTest.java
(original)
+++
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastSetTest.java
Tue Nov 4 08:11:01 2008
@@ -20,89 +20,78 @@
import org.apache.mahout.cf.taste.impl.TasteTestCase;
import java.util.Collection;
-import java.util.HashMap;
import java.util.HashSet;
-import java.util.Map;
import java.util.Random;
import java.util.Set;
/**
- * <p>Tests [EMAIL PROTECTED] FastMap}.</p>
+ * <p>Tests [EMAIL PROTECTED]
org.apache.mahout.cf.taste.impl.common.FastSet}.</p>
*/
-public final class FastMapTest extends TasteTestCase {
+public final class FastSetTest extends TasteTestCase {
- public void testPutAndGet() {
- FastMap<String, String> map = new FastMap<String, String>();
- assertNull(map.get("foo"));
- map.put("foo", "bar");
- assertEquals("bar", map.get("foo"));
+ public void testContainsAndAdd() {
+ FastSet<String> set = new FastSet<String>();
+ assertFalse(set.contains("foo"));
+ set.add("foo");
+ assertTrue(set.contains("foo"));
}
+
public void testRemove() {
- Map<String, String> map = new FastMap<String, String>();
- map.put("foo", "bar");
- map.remove("foo");
- assertEquals(0, map.size());
- assertTrue(map.isEmpty());
- assertNull(map.get("foo"));
+ FastSet<String> set = new FastSet<String>();
+ set.add("foo");
+ set.remove("foo");
+ assertEquals(0, set.size());
+ assertTrue(set.isEmpty());
+ assertFalse(set.contains("foo"));
}
+
public void testClear() {
- Map<String, String> map = new FastMap<String, String>();
- map.put("foo", "bar");
- map.clear();
- assertEquals(0, map.size());
- assertTrue(map.isEmpty());
- assertNull(map.get("foo"));
+ FastSet<String> set = new FastSet<String>();
+ set.add("foo");
+ set.clear();
+ assertEquals(0, set.size());
+ assertTrue(set.isEmpty());
+ assertFalse(set.contains("foo"));
}
public void testSizeEmpty() {
- Map<String, String> map = new FastMap<String, String>();
- assertEquals(0, map.size());
- assertTrue(map.isEmpty());
- map.put("foo", "bar");
- assertEquals(1, map.size());
- assertFalse(map.isEmpty());
- map.remove("foo");
- assertEquals(0, map.size());
- assertTrue(map.isEmpty());
+ FastSet<String> set = new FastSet<String>();
+ assertEquals(0, set.size());
+ assertTrue(set.isEmpty());
+ set.add("foo");
+ assertEquals(1, set.size());
+ assertFalse(set.isEmpty());
+ set.remove("foo");
+ assertEquals(0, set.size());
+ assertTrue(set.isEmpty());
}
public void testContains() {
- FastMap<String, String> map = buildTestFastMap();
- assertTrue(map.containsKey("foo"));
- assertTrue(map.containsKey("baz"));
- assertTrue(map.containsKey("alpha"));
- assertTrue(map.containsValue("bar"));
- assertTrue(map.containsValue("bang"));
- assertTrue(map.containsValue("beta"));
- assertFalse(map.containsKey("something"));
- assertFalse(map.containsValue("something"));
+ FastSet<String> set = buildTestFastSet();
+ assertTrue(set.contains("foo") );
+ assertTrue(set.contains("baz"));
+ assertTrue(set.contains("alpha"));
+ assertFalse(set.contains("something"));
}
public void testNull() {
- Map<String, String> map = new FastMap<String, String>();
- try {
- map.put(null, "bar");
- fail("Should have thrown NullPointerException");
- } catch (NullPointerException npe) {
- // good
- }
+ FastSet<String> set = new FastSet<String>();
try {
- map.put("foo", null);
+ set.add(null);
fail("Should have thrown NullPointerException");
} catch (NullPointerException npe) {
// good
}
- assertNull(map.get(null));
+ assertFalse(set.contains(null));
}
public void testRehash() {
- FastMap<String, String> map = buildTestFastMap();
- map.remove("foo");
- map.rehash();
- assertNull(map.get("foo"));
- assertEquals("bang", map.get("baz"));
+ FastSet<String> set = buildTestFastSet();
+ set.remove("foo");
+ set.rehash();
+ assertFalse(set.contains("foo"));
}
public void testGrow() {
@@ -113,60 +102,31 @@
assertEquals("bang", map.get("baz"));
}
- public void testKeySet() {
- FastMap<String, String> map = buildTestFastMap();
+ public void testIterator() {
+ FastSet<String> set = buildTestFastSet();
Collection<String> expected = new HashSet<String>(3);
expected.add("foo");
expected.add("baz");
expected.add("alpha");
- Set<String> actual = map.keySet();
- assertTrue(expected.containsAll(actual));
- assertTrue(actual.containsAll(expected));
- }
-
- public void testValues() {
- FastMap<String, String> map = buildTestFastMap();
- Collection<String> expected = new HashSet<String>(3);
- expected.add("bar");
- expected.add("bang");
- expected.add("beta");
- Collection<String> actual = map.values();
- assertTrue(expected.containsAll(actual));
- assertTrue(actual.containsAll(expected));
- }
-
- public void testEntrySet() {
- FastMap<String, String> map = buildTestFastMap();
- Set<Map.Entry<String, String>> actual = map.entrySet();
- Collection<String> expectedKeys = new HashSet<String>(3);
- expectedKeys.add("foo");
- expectedKeys.add("baz");
- expectedKeys.add("alpha");
- Collection<String> expectedValues = new HashSet<String>(3);
- expectedValues.add("bar");
- expectedValues.add("bang");
- expectedValues.add("beta");
- assertEquals(3, actual.size());
- for (Map.Entry<String, String> entry : actual) {
- expectedKeys.remove(entry.getKey());
- expectedValues.remove(entry.getValue());
+ for (String s : set) {
+ expected.remove(s);
}
- assertEquals(0, expectedKeys.size());
- assertEquals(0, expectedValues.size());
+ assertTrue(expected.isEmpty());
}
- public void testVersusHashMap() {
- Map<Integer, String> actual = new FastMap<Integer, String>(1, 1000000);
- Map<Integer, String> expected = new HashMap<Integer, String>(1000000);
+
+ public void testVersusHashSet() {
+ Set<Integer> actual = new FastSet<Integer>(1);
+ Set<Integer> expected = new HashSet<Integer>(1000000);
Random r = RandomUtils.getRandom();
for (int i = 0; i < 1000000; i++) {
double d = r.nextDouble();
Integer key = r.nextInt(100);
if (d < 0.4) {
- assertEquals(expected.get(key), actual.get(key));
+ assertEquals(expected.contains(key), actual.contains(key));
} else {
if (d < 0.7) {
- assertEquals(expected.put(key, "foo"), actual.put(key, "foo"));
+ assertEquals(expected.add(key), actual.add(key));
} else {
assertEquals(expected.remove(key), actual.remove(key));
}
@@ -176,24 +136,13 @@
}
}
- public void testMaxSize() {
- Map<String, String> map = new FastMap<String, String>(1, 1);
- map.put("foo", "bar");
- assertEquals(1, map.size());
- map.put("baz", "bang");
- assertEquals(1, map.size());
- assertNull(map.get("foo"));
- map.put("baz", "buzz");
- assertEquals(1, map.size());
- assertEquals("buzz", map.get("baz"));
+ private static FastSet<String> buildTestFastSet() {
+ FastSet<String> set = new FastSet<String>();
+ set.add("foo");
+ set.add("baz");
+ set.add("alpha");
+ return set;
}
- private static FastMap<String, String> buildTestFastMap() {
- FastMap<String, String> map = new FastMap<String, String>();
- map.put("foo", "bar");
- map.put("baz", "bang");
- map.put("alpha", "beta");
- return map;
- }
-}
+}
\ No newline at end of file
Propchange:
lucene/mahout/trunk/core/src/test/java/org/apache/mahout/cf/taste/impl/common/FastSetTest.java
------------------------------------------------------------------------------
svn:mergeinfo =
