C++优化

Question

我正在做一些实时的东西，我需要很多速度。但在我的代码，我有这样的：

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毫秒才能在我的计算机上运行，​​而且这太方便了，有没有优化的想法？

Answer 1

我已经重写了一下，找出你真的在做什么。

警告所有代码是未经测试

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在它仍然有效...你已经有一个测试框架的权利？