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

Question

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

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

当前功率和能量相同(因为 delta 函数)并且 vector 按时间升序排列。我想将其更改为步进功能。脉冲持续时间恒定为 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

您可以利用 vector 按 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

还要考虑:(到目前为止，我不是该领域的专家，所以我只是抛出这个想法，它是否有效取决于您):使用您的代码，您只需“挤压”在一起关闭测量，而不是具有周期性时间的测量 vector 。这可能是您想要的，也可能不是。

免责声明:没有超出“它编译”之外的测试。请不要只是复制粘贴它。它可能是不完整和不正确的。但我希望我给了你一个调查的方向。