3

APARAPI を使用してレーベンシュタイン距離アルゴリズムを実装する可能性を検討していますが、制限が課せられていくつかの問題に直面しています。具体的には、禁止されているカーネルで配列を作成する必要があるということです。

これを回避する方法はありますか、または APARAPI で動作するレーベンシュタイン距離の方法を誰かが得た方がよいでしょうか?

添付のコードは、APARAPI を整理するための場所にあるだけです。結果に対して何もしていないことはわかっており、現時点では 1 回だけ実行しています。

   Kernel kernel = new Kernel() {


        @Override
        public void run() {
            ld("hello", "heya");
        }

        public int ld(String s, String t) {
            int d[]; // matrix
            int n; // length of s
            int m; // length of t
            int i; // iterates through s
            int j; // iterates through t
            int s_i; // ith character of s
            int t_j; // jth character of t
            int cost; // cost

            // Step 1

            n = s.length();
            m = t.length();
            if (n == 0) {
                return m;
            }
            if (m == 0) {
                return n;
            }
            int firstSize = n+1;
            d = new int[firstSize*(m + 1)]; //THIS ISN'T ALLOWED

            // Step 2

            for (i = 0; i <= n; i++) {
                d[firstSize*i+0] = i;
            }

            for (j = 0; j <= m; j++) {
                d[firstSize*0+j] = j;
            }

            // Step 3

            for (i = 1; i <= n; i++) {

                s_i = s.charAt(i - 1);

                // Step 4

                for (j = 1; j <= m; j++) {

                    t_j = t.charAt(j - 1);

                    // Step 5

                    if (s_i == t_j) {
                        cost = 0;
                    } else {
                        cost = 1;
                    }

                    // Step 6
                    int a = d[firstSize*(i - 1)+j] + 1;
                    int b = d[firstSize*i+(j - 1)] + 1;
                    int c = d[firstSize*(i - 1)+(j - 1)] + cost;

                    int mi;

                    mi = a;
                    if (b < mi) {
                        mi = b;
                    }
                    if (c < mi) {
                        mi = c;
                    }

                    d[firstSize*i+j] = mi;

                }
            }

            return d[firstSize*n+m];

        }
    };
    kernel.execute(1);
4

1 に答える 1

4

あなたが示すように、Aparapiはカーネル本体で新しい形式を許可しませんが、カーネルコードがアクセスできるintのバッファーを事前に割り当てることができます。

さらに、実行時にグループのサイズを決定できるため、バッファーは巨大である必要はありませんが、Kernel.getGroupSize() の適切な比率/比率が必要です。

もちろん、引数を String から char[] に変換して、Aparapi のオブジェクト制限 (文字列は許可されていません) を満たす必要がありますが、aparapi ディスカッション リストの同様のスレッドから、その回避策を既に見つけていると思います。

いくつかの「実験的コード」を試す準備ができている場合は、SVN タグ付けされた SupportLocalMemory にブランチがあり、一時的な int[] バッファをローカル メモリに配置できます。これにより、パフォーマンスも向上します。

ゲイリー

于 2012-02-07T16:27:39.280 に答える