Mar*_*ark 14 c algorithm optimization cuda
解决以下问题的速度算法最有效的是什么？
给定6个阵列,D1,D2,D3,D4,D5和D6,每个包含6个数字,如:
D1[0] = number D2[0] = number ...... D6[0] = number
D1[1] = another number D2[1] = another number ....
..... .... ...... ....
D1[5] = yet another number .... ...... ....
给定第二个数组ST1,包含1个数字:
ST1[0] = 6
给定第三个数组ans,包含6个数字:
ans[0] = 3, ans[1] = 4, ans[2] = 5, ......ans[5] = 8
使用数组D1,D2,D3,D4,D5和D6的索引,从0到存储在ST1 [0]中的数字减1,在本例6中,从0到6-1,将ans数组与每个D数组进行比较.如果在相同索引处的任何D中找不到一个或多个ans数,则结果应为0,如果在相同索引处的某个D中找到所有ans数,则结果应为1.也就是说,如果某些ans [i]不等于任何D N [i] 则返回0,并且如果每个ans [i]等于某个D N [i] 则返回1 .
到目前为止,我的算法是:
我试图尽可能地保持一切不受欢迎.
EML := ST1[0] //number contained in ST1[0]
EML1 := 0 //start index for the arrays D
While EML1 < EML
if D1[ELM1] = ans[0]
goto two
if D2[ELM1] = ans[0]
goto two
if D3[ELM1] = ans[0]
goto two
if D4[ELM1] = ans[0]
goto two
if D5[ELM1] = ans[0]
goto two
if D6[ELM1] = ans[0]
goto two
ELM1 = ELM1 + 1
return 0 //If the ans[0] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
two:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[1]
goto three
if D2[ELM1] = ans[1]
goto three
if D3[ELM1] = ans[1]
goto three
if D4[ELM1] = ans[1]
goto three
if D5[ELM1] = ans[1]
goto three
if D6[ELM1] = ans[1]
goto three
ELM1 = ELM1 + 1
return 0 //If the ans[1] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
three:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[2]
goto four
if D2[ELM1] = ans[2]
goto four
if D3[ELM1] = ans[2]
goto four
if D4[ELM1] = ans[2]
goto four
if D5[ELM1] = ans[2]
goto four
if D6[ELM1] = ans[2]
goto four
ELM1 = ELM1 + 1
return 0 //If the ans[2] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
four:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[3]
goto five
if D2[ELM1] = ans[3]
goto five
if D3[ELM1] = ans[3]
goto five
if D4[ELM1] = ans[3]
goto five
if D5[ELM1] = ans[3]
goto five
if D6[ELM1] = ans[3]
goto five
ELM1 = ELM1 + 1
return 0 //If the ans[3] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
five:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[4]
goto six
if D2[ELM1] = ans[4]
goto six
if D3[ELM1] = ans[4]
goto six
if D4[ELM1] = ans[4]
goto six
if D5[ELM1] = ans[4]
goto six
if D6[ELM1] = ans[4]
goto six
ELM1 = ELM1 + 1
return 0 //If the ans[4] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
six:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[5]
return 1 ////If the ans[1] number is not found in either D1[0-6].....
if D2[ELM1] = ans[5] return 1 which will then include ans[0-6] numbers
return 1
if D3[ELM1] = ans[5]
return 1
if D4[ELM1] = ans[5]
return 1
if D5[ELM1] = ans[5]
return 1
if D6[ELM1] = ans[5]
return 1
ELM1 = ELM1 + 1
return 0
作为选择的语言,它将是纯粹的c
我做了原始海报提供的算法的直接琐碎的C实现.它就在这里
正如其他人提出的,首先要做的就是汇总代码.展开对速度并不是很好,因为它会导致代码缓存未命中.我开始滚动内循环并得到了这个.然后我滚动外循环并删除现在无用的gotos并得到下面的代码.
编辑:我改变了几次C代码,因为即使它很简单,当JIT使用CUDA编译或执行它时似乎存在问题(并且CUDA似乎不是非常冗长的错误).这就是为什么下面的代码使用全局...而这只是简单的实现.我们还没有加快速度.它说明了过早的优化.如果我们甚至无法使它工作,为什么还要费心？我想还有一些问题,因为如果我相信维基百科的文章,CUDA似乎对你可以工作的代码施加了很多限制.也许我们应该使用float而不是int？
#include <stdio.h>
int D1[6] = {3, 4, 5, 6, 7, 8};
int D2[6] = {3, 4, 5, 6, 7, 8};
int D3[6] = {3, 4, 5, 6, 7, 8};
int D4[6] = {3, 4, 5, 6, 7, 8};
int D5[6] = {3, 4, 5, 6, 7, 8};
int D6[6] = {3, 4, 5, 6, 7, 9};
int ST1[1] = {6};
int ans[6] = {1, 4, 5, 6, 7, 9};
int * D[6] = { D1, D2, D3, D4, D5, D6 };
/* beware D is passed through globals */
int algo(int * ans, int ELM){
int a, e, p;
for (a = 0 ; a < 6 ; a++){
for (e = 0 ; e < ELM ; e++){
for (p = 0 ; p < 6 ; p++){
if (D[p][e] == ans[a]){
goto cont;
}
}
}
return 0; //bad row of numbers found
cont:;
}
return 1;
}
int main(){
int res;
res = algo(ans, ST1[0]);
printf("algo returned %d\n", res);
}
现在这很有趣,因为我们可以理解代码在做什么.顺便做这个包装工作,我纠正了原始问题中的几个奇怪的问题.我认为这是拼写错误,因为它在全球范围内根本不符合逻辑. - goto总是跳到两个(它应该已经进展) - 最后一个测试检查了ans [0]而不是ans [5]
请标记,如果我错误地认为原始代码应该做什么并且您的原始算法没有拼写错误,请纠正我.
代码在为ans中的每个值执行的操作检查它是否存在于二维数组中.如果任何数字未命中则返回0.如果找到所有数字,则返回1.
我要做的是获得一个真正的快速代码,不是用C语言实现它,而是用python(或C++)这样的另一种语言实现,其中set是标准库提供的基本数据结构.然后我将使用数组的所有值(即O(n))构建一个集合,并检查搜索的数字是否存在于集合中(即O(1)).最终实现应该比现有代码更快,至少从算法的角度来看.
Python示例如下所示,因为它非常简单(打印true/false而不是1/0,但你明白了):
ans_set = set(ans)
print len(set(D1+D2+D3+D4+D5+D6).intersection(ans_set)) == len(ans_set)
这是一个使用集合的可能的C++实现:
#include <iostream>
#include <set>
int algo(int * D1, int * D2, int * D3, int * D4, int * D5, int * D6, int * ans, int ELM){
int e, p;
int * D[6] = { D1, D2, D3, D4, D5, D6 };
std::set<int> ans_set(ans, ans+6);
int lg = ans_set.size();
for (e = 0 ; e < ELM ; e++){
for (p = 0 ; p < 6 ; p++){
if (0 == (lg -= ans_set.erase(D[p][e]))){
// we found all elements of ans_set
return 1;
}
}
}
return 0; // some items in ans are missing
}
int main(){
int D1[6] = {3, 4, 5, 6, 7, 8};
int D2[6] = {3, 4, 5, 6, 7, 8};
int D3[6] = {3, 4, 5, 6, 7, 8};
int D4[6] = {3, 4, 5, 6, 7, 8};
int D5[6] = {3, 4, 5, 6, 7, 8};
int D6[6] = {3, 4, 5, 6, 7, 1};
int ST1[1] = {6};
int ans[] = {1, 4, 5, 6, 7, 8};
int res = algo(D1, D2, D3, D4, D5, D6, ans, ST1[0]);
std::cout << "algo returned " << res << "\n";
}
我们做了一些性能假设:ans的内容应该排序,否则我们应该构建它,我们假设D1..D6的内容将在调用algo之间发生变化.因此,我们不打算为它构造一个集合(因为设置结构是O(n),如果D1..D6正在改变,我们将无法获得任何东西).但是如果我们用相同的D1..D6调用几次算法,那就是改变我们应该做相反的事情并将D1..D6转换成一个我们保持可用的更大的集合.
如果我坚持CI可以做到如下:
由于这里的数据量非常小,我们也可以尝试进行微优化.它可以在这里付出更多.不确定.
EDIT2:CUDA支持的C子集有严格的限制.最严格的一个是我们不应该使用指向主内存的指针.必须考虑到这一点.它解释了为什么当前代码不起作用.最简单的改变可能是依次为每个数组D1..D6调用它.为了保持简短并避免函数调用成本,我们可以使用宏或内联函数.我会发一个提案.
我对你的问题有点困惑，但我想我已经足够帮助你开始了。
#define ROW 6
#define COL 6
int D[ROW][COL]; // This is all of your D arrays in one 2 dimensional array.
接下来您可能应该使用嵌套的 for 循环。每个循环将对应于 的维度D。请记住，索引的顺序很重要。在 C 中保持简洁的最简单方法是记住，D[i]即使D具有多个维度，它也是一个有效的表达式（并且计算结果为指向行的指针：子数组）。
如果您无法将独立的 D 数组更改为一个多维数组，您可以轻松创建一个指针数组，其成员指向每个数组的头并达到相同的效果。
然后，在确定当前D[i]与ans.