Вычислить расстояние Levenshtein с aparapi

Question

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

Есть ли способ обойти это, или лучше кто-нибудь получил метод для расстояния Левенштейна, который работает с 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); 

Answer 1

Как показывают Aparapi не позволяет какой-либо форме нового в теле ядра, однако можно предварительно выделить буфер Интс, который код ядра может получить доступ.

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

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

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

Gary