Mahout 0.6のユーザベースレコメンダー

諸般の事情により古いMahout 0.6を使ってちょっと大きいデータでユーザベースレコメンダーの実験をしていたら、いつも一定の進捗で計算が止まってしまう…。ので、どこで止まっているのか調べたら、GenericItemPreferenceArrayクラスのselectionSortメソッドだった。メンバ変数のlong[] idsを与えられた基準でソートするのだが、O(n^2)のアルゴリズムなので、idsが凄い長いと、現実的な時間では終わらないようだ。

メソッド冒頭のコメントをみると、

// I think this sort will prove to be too dumb, but, it's in place and OK for tiny, mostly sorted data

とあり…。

で、試しにヒープソートに変えてみたら動いたのでメモ。

修正前

  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;
      }
    }
    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;
        }
      }
      if (i != min) {
        swap(i, min);
      }
    }
  }

修正後

  private void selectionSort(int type) {
    int max = length();
    boolean sorted = true;
    for (int i = 1; i < max; i++) {
      if (isLess(i, i - 1, type)) {
        sorted = false;
        break;
      }
    }
    if (sorted) {
      return;
    }
    for(int i = 0; i < max; i++){
      int j = i;
      while(j > 0){
        int parent = (j-1)/2;
        if(isLess(parent, j, type)){          
          swap(j, parent);
        }
        j = parent;
      }
    }
    int toIdx = max - 1;
    while(toIdx > 0){
      swap(0, toIdx);
      int j = 0;
      int lChild = 2 * j + 1;
      int rChild = lChild + 1;          
      while(lChild < toIdx){
        int child = 0;
        if(rChild < toIdx && isLess(lChild, rChild, type)){
          child = rChild;
        }
        else{
          child = lChild;
        }
        if(isLess(j, child, type)){
          swap(child, j);
        }
        j = child;
        lChild = 2 * j + 1;
        rChild = lChild + 1;            
      }
      toIdx--;
    }    
  }