mahout-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sro...@apache.org
Subject svn commit: r711286 - in /lucene/mahout/trunk/core/src: main/java/org/apache/mahout/cf/taste/impl/common/ main/java/org/apache/mahout/cf/taste/impl/eval/ main/java/org/apache/mahout/cf/taste/impl/model/ main/java/org/apache/mahout/cf/taste/impl/recomme...
Date Tue, 04 Nov 2008 16:11:02 GMT
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 {@link Set} implementation, based on algorithms described
in Knuth's
+ * "Art of Computer Programming", Vol. 3, p. 529.</p>
+ *
+ * <p>It should be faster than {@link java.util.HashSet} in some cases, but not all.
It should definitely
+ * be more memory efficient since that implementation is actually just a {@link 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 {@link 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
{@link 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 {@link FastMap}.</p>
+ * <p>Tests {@link 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 = 



Mime
View raw message