C++优化
问题描述:
我正在做一些实时的东西,我需要很多速度。但在我的代码,我有这样的:C++优化
float maxdepth;
uint32_t faceindex;
for (uint32_t tr_iterator = 0; tr_iterator < facesNum-1; tr_iterator++)
{
maxdepth = VXTrisDepth[tr_iterator];
faceindex = tr_iterator;
uint32_t tr_literator = 3*tr_iterator;
uint32_t facelindex = 3*faceindex;
for (uint32_t tr_titerator = tr_iterator+1; tr_titerator < facesNum; tr_titerator++)
{
float depth = VXTrisDepth[tr_titerator];
if (depth > maxdepth)
{
maxdepth = depth;
faceindex = tr_titerator;
}
}
Vei2 itmpx = trs[tr_literator+0];
trs[tr_literator+0] = trs[facelindex+0];
trs[facelindex+0] = itmpx;
itmpx = trs[tr_literator+1];
trs[tr_literator+1] = trs[facelindex+1];
trs[facelindex+1] = itmpx;
itmpx = trs[tr_literator+2];
trs[tr_literator+2] = trs[facelindex+2];
trs[facelindex+2] = itmpx;
float id = VXTrisDepth[tr_iterator];
VXTrisDepth[tr_iterator] = VXTrisDepth[faceindex];
VXTrisDepth[faceindex] = id;
}
VXTrisDepth只是浮动的数组,faceindex是一个uint32_t的,是一个很大的数字,TRS是Vei2的数组,Vei2仅仅是一个整数二维矢量。 问题是,当我们在facenum中有类似16074的东西时,这个循环需要700毫秒才能在我的计算机上运行,而且这太方便了,有没有优化的想法?
答
我已经重写了一下,找出你真的在做什么。
警告所有代码是未经测试
float maxdepth;
uint32_t faceindex;
for (uint32_t tr_iterator = 0; tr_iterator < facesNum-1; tr_iterator++) {
faceindex = tr_iterator;
uint32_t tr_literator = 3*tr_iterator;
uint32_t facelindex = 3*faceindex;
auto fi = std::max_element(&VXTrisDepth[tr_iterator], &VXTrisDepth[facesNum]);
maxdepth = *fi;
faceindex = std::distance(&VXTrisDepth[0], fi);
// hmm was this originally a VEC3...
std::swap(trs[tr_literator+0], trs[facelindex+0]);
std::swap(trs[tr_literator+1], trs[facelindex+1]);
std::swap(trs[tr_literator+2], trs[facelindex+2]);
// with the above this looks like a struct of arrays. SOA vs AOS
std::swap(VXTrisDepth[tr_iterator], VXTrisDepth[faceindex]);
}
现在看起来两个阵列的selection sort这是O(N^2)难怪感觉迟钝。
有多种方法来解决这
- 外部索引,使与长度facesNum阵列,从零到initalized facesNum-1以及使用该索引VXTrisDepth对其进行排序。然后根据索引数组重新排列2个原始数组。
- 外部索引和键对,使它易于使用std :: pair,对它进行排序,然后重新排序原始2个数组。
- 对2个数组进行排序,就好像它是一个,轻微的破解。使用std :: swap你需要专注于一个类型,所以它可能被误用来交换2个数组。没有额外的存储需要。
让我们尝试一个简单的版本与外部对。
我们需要3个阶段
- 化妆辅助阵列O(N)
- 排序辅助阵列O(N LG N)
- 订货原来阵列O(N)
而且一些更多的代码
// make helper array
using hPair = std::pair<float, int>; // order is important
std::vector<hPair> helper;
helper.reserve(numFaces);
for (int idx = 0; idx < facesNum; idx++)
helper.emplace_back(VXTrisDepth[idx], idx);
// sort it using std::pair's operator < or write your own
std::sort(helper.begin(), helper.end());
// reorder the SOA arrays
auto vx = std::begin(VXTrisDepth);
for (auto& help : helper) {
int tr_literator = help.second;
std::swap(trs[tr_literator+0], trs[facelindex+0]);
std::swap(trs[tr_literator+1], trs[facelindex+1]);
std::swap(trs[tr_literator+2], trs[facelindex+2]);
*vs++ = help.first; // we already have the sorted depth in helper.
//std::swap(VXTrisDepth[tr_iterator], VXTrisDepth[faceindex]);
}
记得测试th在它仍然有效...你已经有一个测试框架的权利?
你尝试过'-O3'开关吗? –
尝试在你有tmp变量的地方使用std :: swap – JLev
可能的优化是将第二个循环移出第一个循环,“2nd”循环为每个tr_titerator构建一个maxdepth和faceindex矢量, 1st循环使用它来代替。 – megabyte1024