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 2012/02/07 19:45:58 UTC
svn commit: r1241548 - in
/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model:
GenericItemPreferenceArray.java GenericUserPreferenceArray.java
Author: srowen
Date: Tue Feb 7 18:45:58 2012
New Revision: 1241548
URL: http://svn.apache.org/viewvc?rev=1241548&view=rev
Log:
MAHOUT-963 faster sort of items/users
Modified:
mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericItemPreferenceArray.java
mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericUserPreferenceArray.java
Modified: mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericItemPreferenceArray.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericItemPreferenceArray.java?rev=1241548&r1=1241547&r2=1241548&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericItemPreferenceArray.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericItemPreferenceArray.java Tue Feb 7 18:45:58 2012
@@ -143,7 +143,7 @@ public final class GenericItemPreference
@Override
public void sortByUser() {
- selectionSort(USER);
+ lateralSort(USER);
}
@Override
@@ -151,12 +151,12 @@ public final class GenericItemPreference
@Override
public void sortByValue() {
- selectionSort(VALUE);
+ lateralSort(VALUE);
}
@Override
public void sortByValueReversed() {
- selectionSort(VALUE_REVERSED);
+ lateralSort(VALUE_REVERSED);
}
@Override
@@ -174,30 +174,25 @@ public final class GenericItemPreference
return id == itemID;
}
- private void selectionSort(int type) {
- // I think this sort will prove to be too dumb, but, it's in place and OK for tiny, mostly sorted data
- int max = length();
- boolean sorted = true;
- for (int i = 1; i < max; i++) {
- if (isLess(i, i - 1, type)) {
- sorted = false;
- break;
+ private void lateralSort(int type) {
+ //Comb sort: http://en.wikipedia.org/wiki/Comb_sort
+ int length = length();
+ int gap = length;
+ boolean swapped = false;
+ while (gap > 1 || swapped) {
+ if (gap > 1) {
+ gap /= 1.247330950103979; // = 1 / (1 - 1/e^phi)
}
- }
- if (sorted) {
- return;
- }
- for (int i = 0; i < max; i++) {
- int min = i;
- for (int j = i + 1; j < max; j++) {
- if (isLess(j, min, type)) {
- min = j;
+ swapped = false;
+ int max = length - gap;
+ for (int i = 0; i < max; i++){
+ int other = i + gap;
+ if (isLess(other, i, type)) {
+ swap(i, other);
+ swapped = true;
}
}
- if (i != min) {
- swap(i, min);
- }
- }
+ }
}
private boolean isLess(int i, int j, int type) {
Modified: mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericUserPreferenceArray.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericUserPreferenceArray.java?rev=1241548&r1=1241547&r2=1241548&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericUserPreferenceArray.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model/GenericUserPreferenceArray.java Tue Feb 7 18:45:58 2012
@@ -152,17 +152,17 @@ public final class GenericUserPreference
@Override
public void sortByItem() {
- selectionSort(ITEM);
+ lateralSort(ITEM);
}
@Override
public void sortByValue() {
- selectionSort(VALUE);
+ lateralSort(VALUE);
}
@Override
public void sortByValueReversed() {
- selectionSort(VALUE_REVERSED);
+ lateralSort(VALUE_REVERSED);
}
@Override
@@ -179,33 +179,28 @@ public final class GenericUserPreference
}
return false;
}
-
- private void selectionSort(int type) {
- // I think this sort will prove to be too dumb, but, it's in place and OK for tiny, mostly sorted data
- int max = length();
- boolean sorted = true;
- for (int i = 1; i < max; i++) {
- if (isLess(i, i - 1, type)) {
- sorted = false;
- break;
+
+ private void lateralSort(int type) {
+ //Comb sort: http://en.wikipedia.org/wiki/Comb_sort
+ int length = length();
+ int gap = length;
+ boolean swapped = false;
+ while (gap > 1 || swapped) {
+ if (gap > 1) {
+ gap /= 1.247330950103979; // = 1 / (1 - 1/e^phi)
}
- }
- if (sorted) {
- return;
- }
- for (int i = 0; i < max; i++) {
- int min = i;
- for (int j = i + 1; j < max; j++) {
- if (isLess(j, min, type)) {
- min = j;
+ swapped = false;
+ int max = length - gap;
+ for (int i = 0; i < max; i++){
+ int other = i + gap;
+ if (isLess(other, i, type)) {
+ swap(i, other);
+ swapped = true;
}
}
- if (i != min) {
- swap(i, min);
- }
- }
+ }
}
-
+
private boolean isLess(int i, int j, int type) {
switch (type) {
case ITEM:
@@ -309,4 +304,4 @@ public final class GenericUserPreference
}
-}
\ No newline at end of file
+}