String - Suffix Array #4

Activity

1. NASU41

   added

   help wantedExtra attention is neededExtra attention is needed

   on Sep 8, 2020
2. uwi commented on Sep 8, 2020

   

   uwi

   on Sep 8, 2020

   Collaborator

   More actions

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

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

   

   suisen-cp

   on Sep 9, 2020

   Collaborator

   More actions

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

   

   uwi

   on Sep 9, 2020

   Collaborator

   More actions

   @suisen-cp コードもらえますか？パフォーマンス測ってみます。
5. suisen-cp commented on Sep 9, 2020

   

   suisen-cp

   on Sep 9, 2020

   Collaborator

   More actions

   直接貼ります

   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;
                       }
                   }
               }
           }
       }
   }
6. uwi commented on Sep 10, 2020

   

   uwi

   on Sep 10, 2020

   Last edited by uwi

   Collaborator

   More actions

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

   added

   invalidThis doesn't seem rightThis doesn't seem right

   and removed

   help wantedExtra attention is neededExtra attention is needed

   invalidThis doesn't seem rightThis doesn't seem right

   on Sep 10, 2020
8. uwi

   self-assigned this

   on Sep 10, 2020
9. NASU41

   added a commit that references this issue on Sep 13, 2020

   Merge pull request #4 from suisen-cp/two-sat

   ...

   1438482
10. NASU41

    added a commit that references this issue on Sep 21, 2020

    Merge pull request #38 from NASU41/StringAlgorithm

    ...

    d3d2766
11. uwi commented on Sep 21, 2020

    

    uwi

    on Sep 21, 2020

    Last edited by uwi

    Collaborator

    More actions

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

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

    👍React with 👍1Reacted by Shou Ohba