You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by sr...@apache.org on 2010/01/27 23:32:03 UTC
svn commit: r903886 - in
/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common:
FastByIDMap.java FastIDSet.java
Author: srowen
Date: Wed Jan 27 22:32:03 2010
New Revision: 903886
URL: http://svn.apache.org/viewvc?rev=903886&view=rev
Log:
Optimization to find methods
Modified:
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java?rev=903886&r1=903885&r2=903886&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java Wed Jan 27 22:32:03 2010
@@ -86,6 +86,9 @@
this.recentlyAccessed = countingAccesses ? new BitSet(hashSize) : null;
}
+ /**
+ * @see #findForAdd(long)
+ */
private int find(long key) {
int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
long[] keys = this.keys;
@@ -93,7 +96,28 @@
int jump = 1 + theHashCode % (hashSize - 2);
int index = theHashCode % hashSize;
long currentKey = keys[index];
- while (currentKey != NULL && (currentKey == REMOVED || key != currentKey)) {
+ while (currentKey != NULL && key != currentKey) {
+ if (index < jump) {
+ index += hashSize - jump;
+ } else {
+ index -= jump;
+ }
+ currentKey = keys[index];
+ }
+ return index;
+ }
+
+ /**
+ * @see #find(long)
+ */
+ private int findForAdd(long key) {
+ int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
+ long[] keys = this.keys;
+ int hashSize = keys.length;
+ int jump = 1 + theHashCode % (hashSize - 2);
+ int index = theHashCode % hashSize;
+ long currentKey = keys[index];
+ while (currentKey != NULL && currentKey != REMOVED && key != currentKey) { // Different here
if (index < jump) {
index += hashSize - jump;
} else {
@@ -157,8 +181,13 @@
}
}
// Here we may later consider implementing Brent's variation described on page 532
- int index = find(key);
- if (keys[index] == NULL) {
+ int index = findForAdd(key);
+ long keyIndex = keys[index];
+ if (keyIndex == key) {
+ V oldValue = values[index];
+ values[index] = value;
+ return oldValue;
+ } else {
// If size is limited,
if (countingAccesses && numEntries >= maxSize) {
// and we're too large, clear some old-ish entry
@@ -167,12 +196,10 @@
keys[index] = key;
values[index] = value;
numEntries++;
- numSlotsUsed++;
+ if (keyIndex == NULL) {
+ numSlotsUsed++;
+ }
return null;
- } else {
- V oldValue = values[index];
- values[index] = value;
- return oldValue;
}
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java?rev=903886&r1=903885&r2=903886&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java Wed Jan 27 22:32:03 2010
@@ -57,6 +57,9 @@
Arrays.fill(keys, NULL);
}
+ /**
+ * @see #findForAdd(long)
+ */
private int find(long key) {
int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
long[] keys = this.keys;
@@ -64,7 +67,28 @@
int jump = 1 + theHashCode % (hashSize - 2);
int index = theHashCode % hashSize;
long currentKey = keys[index];
- while (currentKey != NULL && (currentKey == REMOVED || key != currentKey)) {
+ while (currentKey != NULL && key != currentKey) { // note: true when currentKey == REMOVED
+ if (index < jump) {
+ index += hashSize - jump;
+ } else {
+ index -= jump;
+ }
+ currentKey = keys[index];
+ }
+ return index;
+ }
+
+ /**
+ * @see #find(long)
+ */
+ private int findForAdd(long key) {
+ int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
+ long[] keys = this.keys;
+ int hashSize = keys.length;
+ int jump = 1 + theHashCode % (hashSize - 2);
+ int index = theHashCode % hashSize;
+ long currentKey = keys[index];
+ while (currentKey != NULL && currentKey != REMOVED && key != currentKey) { // Different here
if (index < jump) {
index += hashSize - jump;
} else {
@@ -102,11 +126,14 @@
}
}
// Here we may later consider implementing Brent's variation described on page 532
- int index = find(key);
- if (keys[index] == NULL) {
+ int index = findForAdd(key);
+ long keyIndex = keys[index];
+ if (keyIndex != key) {
keys[index] = key;
numEntries++;
- numSlotsUsed++;
+ if (keyIndex == NULL) {
+ numSlotsUsed++;
+ }
return true;
}
return false;