Вычислить расстояние Левенштейна с апарапи - PullRequest
Новая
       23

Вычислить расстояние Левенштейна с апарапи

3 голосов
/ 06 февраля 2012

Я смотрю на возможность реализации алгоритма расстояния Левенштейна с использованием APARAPI, но я сталкиваюсь с некоторыми проблемами, связанными с ограничениями , которые ставит - в частности, мне нужно создать массив в ядре, котороезапрещено.

Есть ли способ обойти это, или лучше кто-нибудь получил метод расстояния Левенштейна, который работает с APARAPI?

Прикрепленный код только для того, чтобы попытаться отсортировать APARAPIЯ знаю, что я ничего не делаю с результатом, и я просто выполняю один раз в данный момент. 

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

1 Ответ

4 голосов
/ 07 февраля 2012

Как вы указали, Aparapi не допускает никаких новых форм в теле ядра, однако вы можете предварительно выделить буфер целых чисел, к которому имеет доступ код ядра.

Кроме того, поскольку вы можете определить размер группы во время выполнения, ваш буфер не обязательно должен быть огромным, но есть некоторая разумная пропорция / отношение Kernel.getGroupSize ().

Конечно, вам нужно будет преобразовать аргументы из String в char [], чтобы удовлетворить объектное ограничение Aparapi (строки не допускаются), но я думаю, что из аналогичного потока в списках обсуждений aparapi вы уже нашли обходной путь для этого.

Если вы готовы экспериментировать с некоторым «экспериментальным кодом», у меня есть ветка в SVN с тегом SupportLocalMemory, которая позволит вам поместить ваш временный буфер int [] в локальную память, что также должно быть более производительным.

Гари

...