如何避免在 cpp 中使用嵌套循环？

Question

我正在研究传感器的数字采样。我有以下代码来计算最高幅度和相应的时间。

struct LidarPoints{
   float timeStamp;
   float Power;
}
std::vector<LidarPoints> measurement; // To store Lidar points of current measurement

目前功率和能量是一样的（因为delta函数）向量是按时间升序排列的。我想将其更改为步进功能。脉冲持续时间恒定为 10ns。

uint32_t pulseDuration = 5;

问题是找到样本之间的任何重叠，如果有则将振幅相加。

我目前使用以下代码：

for(auto i= 0; i< measurement.size(); i++){
   for(auto j=i+1; i< measurement.size(); j++){
      if(measurement[j].timeStamp - measurement[i].timeStamp) < pulseDuration){
          measurement[i].Power += measurement[j].Power;
          measurement[i].timeStamp = (measurement[i].timeStamp + measurement[j].timeStamp)/2.0f;
    } 
  }
}

是否可以在没有两个 for 循环的情况下编写此代码，因为我负担不起嵌套循环所花费的时间。

Answer 1

如果您的值按时间戳的升序排列，将 else break 添加到 if 语句应该不会影响结果，但应该会快得多。

for(auto i= 0; i< measurement.size(); i++){
   for(auto j=i+1; i< measurement.size(); j++){
      if(measurement[j].timeStamp - measurement[i].timeStamp) < pulseDuration){
          measurement[i].Power += measurement[j].Power;
          measurement[i].timeStamp = (measurement[i].timeStamp + measurement[j].timeStamp)/2.0f;
    } else {
      break;
    }
  }
}

Answer 2

由于抖动等时序复杂性，需要切换到[数值积分][1]（例如Trapezoidal Integration...).

Answer 3

你可以利用向量按timeStamp排序的优势，通过二分查找找到下一个脉冲，从而将复杂度从O(n^2)降低到O(n log n):

#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator

auto it = measurement.begin();
auto end = measurement.end();

while (it != end)
{
    // next timestamp as in your code
    auto timeStampLower = it->timeStamp + pulseDuration;

    // next value in measurement with a timestamp >= timeStampLower
    auto lower_bound = std::lower_bound(it, end, timeStampLower, [](float a, const LidarPoints& b) {
            return a < b.timeStamp;
        });

    // sum over [timeStamp, timeStampLower)
    float sum = std::accumulate(it, lower_bound, 0.0f, [] (float a, const LidarPoints& b) {
            return a + b.timeStamp;
        });

    auto num = std::distance(it, lower_bound);
    // num should be >= since the vector is sorted and pulseDuration is positive
    // you should uncomment next line to catch unexpected error
    // Expects(num >= 1); // needs GSL library
    // assert(num >= 1); // or standard C if you don't want to use GSL

    // average over [timeStamp, timeStampLower)
    it->timeStamp = sum / num;

    // advance it
    it = lower_bound;
}

https://en.cppreference.com/w/cpp/algorithm/lower_bound https://en.cppreference.com/w/cpp/algorithm/accumulate

另请注意，我的算法会产生与您不同的结果，因为您并没有真正计算 measurement[i].timeStamp = (measurement[i].timeStamp + measurement[j].timeStamp)/2.0f

的多个值的平均值

还要考虑：（到目前为止，我不是该领域的专家，所以我只是抛出这个想法，它是否有效取决于您）：使用您的代码，您只需 "squash"一起关闭测量，而不是具有周期性时间的测量向量。这可能是你想要的，也可能不是。

免责声明：未在 "it compiles" 之后进行测试。请不要只是复制粘贴它。它可能是不完整和不正确的。但我希望我给了你一个调查的方向。

如何避免在 cpp 中使用嵌套循环？

How to avoid using nested loops in cpp?

c++

nested-loops

lidar