如何快速找到向量和的最大元素？
如何快速找到向量和的最大元素？
提问于 2009-09-03 16:06:49
在我的程序的最内部循环中有一个下面的代码
struct V {
float val [200]; // 0 <= val[i] <= 1
};
V a[600];
V b[250];
V c[250];
V d[350];
V e[350];
// ... init values in a,b,c,d,e ...
int findmax(int ai, int bi, int ci, int di, int ei) {
float best_val = 0.0;
int best_ii = -1;
for (int ii = 0; ii < 200; ii++) {
float act_val =
a[ai].val[ii] +
b[bi].val[ii] +
c[ci].val[ii] +
d[ci].val[ii] +
e[ci].val[ii];
if (act_val > best_val) {
best_val = act_val;
best_ii = ii;
}
}
return best_ii;
}我不在乎它是一些聪明的算法(但这将是最有趣的)，还是一些C++技巧、本质或汇编程序。但我需要让findmax函数更高效。
事先非常感谢。
编辑：，似乎分支是最慢的操作(错误预测？)。
回答 7
Stack Overflow用户
回答已采纳
发布于 2009-09-03 16:17:52
我看不出有明显的算法优化空间。理论上，我们只能计算这五个向量的和，直到很明显不能达到最大值为止，但这只会增加五个数之和的开销。您可以尝试使用多个线程并为线程分配范围，但是当您只有200个非常短的工作项时，您必须考虑线程创建的开销。
因此，我倾向于说，在x86上使用汇编程序和MMX或SSE指令，或者使用(特定于机器的) C++，提供对这些指令的访问的库是最好的选择。
Stack Overflow用户
发布于 2009-09-03 16:34:09
如果编译器在缩短跳转方面遇到困难，这可能会有所帮助：
int findmax(int ai, int bi, int ci, int di, int ei) {
float best_val = 0.0;
int best_ii = -1;
float* a_it = &a[ai].val[0]
float* b_it = &b[bi].val[0]
float* c_it = &c[ci].val[0]
float* d_it = &d[di].val[0] // assume typo ci->di
float* e_it = &e[ei].val[0] // assume typo ci->ei
for (int ii = 0; ii < 200; ii++) {
float act_val = *(a_it++) + *(b_it++) + *(c_it++) + *(d_it++) + *(e_it++);
best_val = (act_val <= best_val) ? best_val : act_val; // becomes _fsel
best_ii = (act_val <= best_val) ? best_ii : ii; // becomes _fsel
}
return best_ii;
}从缓存丢失的角度来看，生成sum表可能会更快一些--我将稍后发布如下内容：
int findmax(int ai, int bi, int ci, int di, int ei) {
float best_val = 0.0;
int best_ii = -1;
float* its[] = {&a[ai].val[0], &a[bi].val[0], &a[ci].val[0], &a[di].val[0], &a[ei].val[0] };
V sums;
for (int ii = 0; ii < 200; ii++) {
sums.val[ii] = * (++its[0]);
}
for (int iter = 1 ; iter < 5; ++iter) {
for (int ii = 0; ii < 200; ii++) {
sums.val[ii] += * (++its[iter]);
}
}
}
for (int ii = 0; ii < 200; ii++) {
best_val = (sums.val[ii] <= best_val) ? best_val : sums.val[ii]; // becomes _fsel
best_ii = (sums.val[ii] <= best_val) ? best_ii : ii; // becomes _fsel
}
return best_ii;
}Stack Overflow用户
发布于 2009-09-03 16:17:30
如果不检查每个和，我看不出有什么方法可以做到这一点，这是一个O(n)问题。但是，由于您的数据是线性排列的，Intel/AMD MMX或SSE指令可能会有所帮助。有关Microsoft的本质实现，请参阅此链接：
http://msdn.microsoft.com/en-us/library/y0dh78ez(VS.71).aspx
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1374372
复制相关文章
相似问题
腾讯云开发者
