mahout-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sro...@apache.org
Subject svn commit: r1241548 - in /mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/model: GenericItemPreferenceArray.java GenericUserPreferenceArray.java
Date Tue, 07 Feb 2012 18:45:58 GMT
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
+}



Mime
View raw message