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--; } }