这个数组比较问题的最佳算法是什么？
解决以下问题的速度算法最有效的是什么？
给定6个arrays，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 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 #include 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 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可以做到如下：
- 复制D1 .. D6中的所有数字在一个唯一的数组中（每行使用memcpy）
- 排序此数组的内容
- 使用二分搜索来检查数字是否可用
由于这里的数据量非常小，我们也可以尝试进行微观优化。 它可以在这里付出更多。 不确定。
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不匹配后，可以使用break语句中断内循环。
只需要比较36个值，最有效的方法是根本不使用CUDA。
只需使用CPU循环。
如果您更改输入，我将更改我的答案。
如果数字的范围有限，那么制作位数组可能会更容易，如下所示：
int IsPresent(int arrays[][6], int ans[6], int ST1) { uint32_t bit_mask = 0; for(int i = 0; i < 6; ++ i) { for(int j = 0; j < ST1; ++ j) { assert(arrays[i][j] >= 0 && arrays[i][j] < 32); // range is limited bit_mask |= 1 << arrays[i][j]; } } // make a "list" of numbers that we have for(int i = 0; i < 6; ++ i) { if(((bit_mask >> ans[i]) & 1) == 0) return 0; // in ans, there is a number that is not present in arrays } return 1; // all of the numbers were found }
这将始终以O（6 * ST1 + 6）运行。 现在这样做的缺点是首先要经过多达36个数组，然后检查六个值。 如果有一个强大的先决条件，数字将主要存在，可以反转测试并提供提前退出：
int IsPresent(int arrays[][6], int ans[6], int ST1) { uint32_t bit_mask = 0; for(int i = 0; i < 6; ++ i) { assert(ans[i][j] >= 0 && ans[i][j] < 32); // range is limited bit_mask |= 1 << ans[i]; } // make a "list" of numbers that we need to find for(int i = 0; i < 6; ++ i) { for(int j = 0; j < ST1; ++ j) bit_mask &= ~(1 << arrays[i][j]); // clear bits of the mask if(!bit_mask) // check if we have them all return 1; // all of the numbers were found } assert(bit_mask != 0); return 0; // there are some numbers remaining yet to be found }
如果第一个数组中的第一个数字覆盖所有的ans （并且是相同数字的六倍），则最多在O（6 * ST1 + 6）中运行，最好在O（6 + 1）中运行。 请注意，位掩码为零的测试可以在每个数组之后（就像现在一样），也可以在每个元素之后（这种方式涉及更多检查，但是当找到所有数字时也会提前截止）。 在CUDA的上下文中，算法的第一个版本可能会更快，因为它涉及更少的分支，并且大多数循环（除了ST1的循环）可以自动展开。
但是，如果数字的范围是无限的，我们可以做其他事情。 由于ans和所有数组中只有最多7 * 6 = 42个不同的数字，因此可以将这些数字映射到42个不同的数字，并使用64位整数作为位掩码。 但可以说，这种数字到整数的映射已经足够用于测试，并且可以完全跳过这个测试。
另一种方法是对数组进行排序，并简单地计算单个数字的覆盖范围：
int IsPresent(int arrays[][6], int ans[6], int ST1) { int all_numbers[36], n = ST1 * 6; for(int i = 0; i < 6; ++ i) memcpy(&all_numbers[i * ST1], &arrays[i], ST1 * sizeof(int)); // copy all of the numbers into a contiguous array std::sort(all_numbers, all_numbers + n); // or use "C" standard library qsort() or a bitonic sorting network on GPU // alternatively, sort each array of 6 separately and then merge the sorted // arrays (can also be done in parallel, to some level) n = std::unique(all_numbers, all_numbers + n) - all_numbers; // this way, we can also remove duplicate numbers, if they are // expect to occur frequently and make the next test faster. // std::unique() actually moves the duplicates to the end of the list // and returns an iterator (a pointer in this case) to one past // the last unique element of the list - that gives us number of // unique items. for(int i = 0; i < 6; ++ i) { int *p = std::lower_bound(all_numbers, all_numbers + n, ans[i]); // use binary search to find the number in question // or use "C" standard library bfind() // or implement binary search yourself on GPU if(p == all_numbers + n) return 0; // not found // alternately, make all_numbers array of 37 and write // all_numbers[n] = -1; before this loop. that will act // as a sentinel and will save this one comparison (assuming // that there is a value that is guaranteed not to occur in ans) if(*p != ans[i]) return 0; // another number found, not ans[i] // std::lower_bound looks for the given number, or for one that // is greater than it, so if the number was to be inserted there // (before the bigger one), the sequence would remain ordered. } return 1; // all the numbers were found }
这将在O（n）中进行复制，O（36 log 36）用于排序，可选地O（n）用于unique （其中n是6 * ST1）和O（n log n）用于搜索（其中n可以更少）如果使用unique话，比6 * ST1）。 因此整个算法以线性时间运行。 请注意，这不涉及任何动态内存分配，因此即使对于GPU平台也是合适的（人们必须实现排序和端口std::unique()和std::lower_bound() ，但所有这些都是非常简单的函数） 。