我正在考虑使用APARAPI实现Levenshtein距离算法的可能性,但是我遇到了limitations带来的一些问题-特别是我需要在内核中创建一个被禁止的数组。
有没有解决的办法,还是更好的办法是有人可以使用APARAPI解决Levenshtein距离的方法?
随附的代码仅用于尝试对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);
最佳答案
正如您指出的那样,Aparapi不允许在内核主体中使用任何形式的新内容,但是您可以预分配一个内核可以访问的整数缓冲区。
此外,由于您可以在运行时确定组大小,因此缓冲区不必很大,而是Kernel.getGroupSize()的合理比例/比率。
当然,您需要将参数从String转换为char []以满足Aparapi的对象限制(不允许使用字符串),但是我认为从aparapi讨论列表的类似主题中,您已经找到了解决方法。
如果您准备尝试一些“实验代码”,我会在SVN标签的SupportLocalMemory中创建一个分支,该分支将允许您将临时int []缓冲区放置在本地内存中,该缓冲区也应具有更高的性能。
加里