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はちょうどフロートの配列で、TRSはVei2の配列で、Vei2はちょうど整数の2Dベクトルで、faceindexはのuint32_tで、大きな数です。 問題はfacensumに16074のようなものがあるとき、このループは私のコンピュータ上で実行するには700ミリ秒かかります。それはあまりにも、最適化の考えですか？

Answer 1

私はあなたが本当にやっていたことを見つけるために少し書き直しました。すべてのコードを警告

は、今ではO（N^2）それは遅い感じも不思議では2つの配列のselection sortのように見えるテストされていない

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]); 
} 

です。この

• 外部インデックスをソートするための複数の方法があり

  、ゼロからfacesNum-1にinitalized長facesNum持つ配列を作成し、VXTrisDepthにインデックスを使用してそれらを並べ替えます。次に、2つの元の配列をインデックス配列に従って並べ替えます。

• インデックスとキーの外部ペアで、std :: pairを使いやすくし、ソートして元の2つの配列を並べ替えます。
• 2つの配列を1のようにソートします。わずかにハックします。 std :: swapを使用すると、タイプを専門にする必要があるので、2つの配列を入れ替えることができます。余分なストレージは必要ありません。

外部ペアとの簡単なバージョンを試してみましょう。

我々は、元の配列のO（N）

リオーダー3つの段階

• メイクヘルパー配列O（N）
• ソートヘルパー配列O（N LG 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]); 
  }  
  

  まだ動作しています...あなたはすでにテストフレームワークを持っていますか？