String - Suffix Array

[uwi]

Suffix Arrayの実装のうち、NaiveとDoublingについて、以下の懸念点があります。

• intのソートにComparatorを渡せないのでInteger配列に対してComparatorを適用しているが、パフォーマンス上あまり好ましくない。
  • ちゃんとやるならマージソートを手実装してそれにIntBinaryOperatorなりを渡せるようにすると良さそう。
  • サイズが小さいところ限定だから実はそんなに影響ないのかもしれないが
• SA-ISから使うとき、原典では10,40で使うとなっているがそれがJavaにおいて良いパフォーマンスを出す値なのか未検証

[suisen-cp]

int[] のソート用に MergeSort のライブラリを持っているので提供できますが, 10 や 40 程度であれば挿入ソートの方が速いと思われます. (挿入ソートも持っているので提供できます)

[uwi]

@suisen-cp コードもらえますか？パフォーマンス測ってみます。

[suisen-cp]

直接貼ります

class SortUsingComparator {
    static void insertionsortUsingComparator(int[] a, java.util.function.IntBinaryOperator comparator) {
        final int n = a.length;
        for (int i = 1; i < n; i++) {
            final int tmp = a[i];
            if (comparator.applyAsInt(a[i - 1], tmp) > 0) {
                int j = i;
                do {
                    a[j] = a[j - 1];
                    j--;
                } while (j > 0 && comparator.applyAsInt(a[j - 1], tmp) > 0);
                a[j] = tmp;
            }
        }
    }

    static void mergesortUsingComparator(int[] a, java.util.function.IntBinaryOperator comparator) {
        final int n = a.length;
        final int[] work = new int[n];
        for (int block = 1; block <= n; block <<= 1) {
            final int block2 = block << 1;
            for (int l = 0, max = n - block; l < max; l += block2) {
                int m = l + block;
                int r = Math.min(l + block2, n);
                System.arraycopy(a, l, work, 0, block);
                for (int i = l, wi = 0, ti = m;; i++) {
                    if (ti == r) {
                        System.arraycopy(work, wi, a, i, block - wi);
                        break;
                    }
                    if (comparator.applyAsInt(work[wi], a[ti]) > 0) {
                        a[i] = a[ti++];
                    } else {
                        a[i] = work[wi++];
                        if (wi == block) break;
                    }
                }
            }
        }
    }
}

[uwi]

• [x] いただいたものの動確
• [x] 既存コードのパフォーマンス測定
  • [ ] 意地悪な例があまり思いつかないので調べる
• [x] いただいたものを移植
• [x] verify

[uwi]

手元でランダムケースとinsertionSortの最悪ケースで調べてTHRESHOLDを調整した結果、 saNaiveは50未満, saDoubling使わずという結果になりました。

テストコード等もできればリポジトリに上げたいですが、今その場はないようですね。