文章/答案/技术大牛

发布

社区首页 >问答首页 >合并两个脉冲，如果它们匹配的话

问合并两个脉冲，如果它们匹配的话
EN

Code Review用户

提问于 2021-06-09 07:50:10

回答 2查看 128关注 0票数 4

函数processFus()需要：

两个脉冲列表(每个200000个)，作为输入
两个脉冲列表，空的，pulseValid的和无效的。该函数必须在流程结束时填充它们。

函数检查listPulseA中的每个脉冲是否与listPulseB中的一个脉冲匹配。要检查是否匹配，listPulseB中的脉冲必须首先在时间窗口内。

我正在寻求在风格和表现上的建议。

在(最坏的)情况下，我们可以在listPulseB中用1微秒隔开20万个脉冲，这样就可以进行30万次检查(20万pulsesA，* 1500 pulseB，即时间窗口内的-> cf #define THRESHOLD_SEARCH 1.5)，而且需要花费太多的时间(~800 ms，而我想要的时间小于200 ms)。

listPulseA和listPulseB中的脉冲按timeOfArrival排序。

主内测试显示有20万个匹配，因此20万个脉冲有效，40万个无效。若要查看不匹配和不融合，必须将DIFF_MAX_TOA_A_B设置为0。在本例中，将有400 000个有效脉冲和0无效脉冲

fus.hpp：

#ifndef SRS_FUS_HPP_
#define SRS_FUS_HPP_

#include <list>

#define LSB_TIME_PRECISION 10
#define listPulse_MAXSIZE 400000

struct Pulse //Can't modify this structure
{
    unsigned long long timeOfArrival; //Ns
    unsigned long frequency;
    unsigned long duration;
    unsigned long timePrecision;
    unsigned int quality;
    bool isValid;
    bool isRejected;
    bool isTruncated;
    
};


struct ListPulse
{
    Pulse listPulse[listPulse_MAXSIZE];
    long size = 0;
};

struct InfoPulse
{
    Pulse pulse;
    unsigned long long sumTOADuration;
    unsigned long long timePrecision;
};



class Fus {
public:
    Fus(){}
    virtual ~Fus(){}
    
    void processFus(std::list<Pulse> &listPulseA, std::list<Pulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid);
    
private:

    void filterListB(std::list<Pulse> &listPulseB, std::list<InfoPulse> &listInfoPulseB);
    
    inline bool checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &seuilMatch, const unsigned long long &sumTOADurationA); 
    
    void createPulse(const Pulse &pulseA, const Pulse &pulseB, Pulse &pulseFus);
    
    void fillListOut(const std::list<Pulse> &listPulseA, const std::list<InfoPulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid);
    void chooseListToAdd(const Pulse &pulse, ListPulse &pulseValid, ListPulse &pulseInvalid);
    void addToList(const Pulse &pulse, ListPulse &listPulse);
    
};


#endif

fus.cpp：

#include "fus.hpp"
#include <iostream>

#define THRESHOLD_SEARCH 1.5 // ms, can't change it
#define DIFF_MAX_TOA_A_B 200 // ns
#define MS_TO_NS 1000000

//listPulseA and listPulseB are sorted by timeOfArrival before
//We need to check for each pulseA if it match with a pulseB, and if it's the case create a new pulse, insert it inside the listPulseB
//If two pulse match they become invalid and the new one is valid
//at the ned of the process we must fill the two list "pulseValid" and "pulseInvalid"
void Fus::processFus(std::list<Pulse> &listPulseA, std::list<Pulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid)
{
    pulseValid.size = 0;
    pulseInvalid.size = 0;
    
    
    std::list<InfoPulse> listInfoPulseB;
    
    filterListB(listPulseB, listInfoPulseB);
    
    std::list<InfoPulse>::iterator indB = listInfoPulseB.begin();
    std::list<InfoPulse>::iterator lastIndB = listInfoPulseB.begin();
    
    
    for(auto &pulseA:listPulseA)
    {
        if(pulseA.isRejected || pulseA.isTruncated) //Filter
        {
            pulseA.isValid = 0;
        }
        else
        {
            pulseA.isValid = 1;
            
            bool keepGoing = true;
            indB = lastIndB; // Get the last indB which was inside the time window, so we don't have to get through the whole list everytime
            
            unsigned long long toaWindowA = 0;
            if(pulseA.timeOfArrival > THRESHOLD_SEARCH * MS_TO_NS)
            {
                toaWindowA = pulseA.timeOfArrival - THRESHOLD_SEARCH * MS_TO_NS;
            }
            const unsigned long long thresholdMatchA = DIFF_MAX_TOA_A_B + pulseA.timePrecision * LSB_TIME_PRECISION;
            const unsigned long long sumTOADurationA = pulseA.timeOfArrival + pulseA.duration;
            
            //Get the first pulse B inside the time window of the pulse A
            while(keepGoing && indB != listInfoPulseB.end())
            {
                InfoPulse &refPulseB = *indB;
                if(refPulseB.pulse.isValid && toaWindowA < refPulseB.pulse.timeOfArrival)
                {
                    keepGoing = false;
                    lastIndB = indB;
                }
                else
                {
                    ++indB;
                }
            }
            
            keepGoing = true;
            // Once we get the first pulseB inside the window
            // while we are still inside the window and there is no match, continue
            while(keepGoing && indB != listInfoPulseB.end())
            {
                InfoPulse &refPulseB = *indB;
                const unsigned long long thresholdMatch = thresholdMatchA + refPulseB.timePrecision;
                const long long isInWindow = thresholdMatch + sumTOADurationA - refPulseB.pulse.timeOfArrival;
                if(isInWindow < 0)
                {
                    keepGoing = false;
                }
                else
                {
                    if(checkMatch(pulseA, refPulseB, thresholdMatch, sumTOADurationA))
                    {
                        //If match, we create a new pulse, and we insert it in the listB
                        // the two old pulses are not valid anymore
                        Pulse pulseFus;
                        createPulse(pulseA, refPulseB.pulse, pulseFus);
                        pulseA.isValid = false;
                        refPulseB.pulse.isValid = false;
                        
                        InfoPulse infoPulseB = {pulseFus, pulseFus.timeOfArrival + pulseFus.duration, pulseFus.timePrecision * LSB_TIME_PRECISION};
                        listInfoPulseB.insert(indB, infoPulseB);
                        keepGoing = false;
                    }
                    ++indB;
                }
            }
        }
        
    }
    
    fillListOut(listPulseA, listInfoPulseB, pulseValid, pulseInvalid);
    
}


void Fus::filterListB(std::list<Pulse> &listPulseB, std::list<InfoPulse> &listInfoPulseB)
{
    for(auto &pulse:listPulseB)
    {
        if(pulse.isRejected || pulse.isTruncated) //Filter
        {
            pulse.isValid = 0;
        }
        else
        {
            pulse.isValid = 1;
        }
        InfoPulse infoPulseB = {pulse, pulse.timeOfArrival + pulse.duration, pulse.timePrecision * LSB_TIME_PRECISION};
        listInfoPulseB.push_back(infoPulseB);
    }
    
}
    
bool Fus::checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &thresholdMatch, const unsigned long long &sumTOADurationA)
{
    const long long tmp = sumTOADurationA - pulseB.sumTOADuration - thresholdMatch;
    if(pulseA.timeOfArrival > pulseB.pulse.timeOfArrival)
    {
        if(tmp < 0 || pulseA.timeOfArrival - pulseB.pulse.timeOfArrival < thresholdMatch)
        {
            return true;
        }
    }
    else
    {
        if(pulseB.pulse.timeOfArrival - pulseA.timeOfArrival < thresholdMatch)
        {
            return true;
        }
    }
    return false;
}



void Fus::createPulse(const Pulse &pulseA, const Pulse &pulseB, Pulse &pulseFus)
{
    if(pulseB.quality > 4)
    {
        pulseFus = pulseB;
        pulseFus.isValid = true;
    }
    else
    {
        pulseFus = pulseA;
        pulseFus.frequency = pulseB.frequency;
        pulseFus.isValid = true;
    }   
}
    
void Fus::fillListOut(const std::list<Pulse> &listPulseA, const std::list<InfoPulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid)
{
    auto indA = listPulseA.cbegin();
    auto indB = listPulseB.cbegin();
    auto endA = listPulseA.cend();
    auto endB = listPulseB.cend();
    
    while(indA != endA || indB != endB)
    {
        if(indA == endA)
        {
            chooseListToAdd(indB->pulse, pulseValid, pulseInvalid);
            ++indB;
        }
        else if(indB == endB)
        {
            chooseListToAdd(*indA, pulseValid, pulseInvalid);
            ++indA;
        }
        else
        {
            if(indA->timeOfArrival < indB->pulse.timeOfArrival)
            {
                chooseListToAdd(*indA, pulseValid, pulseInvalid);
                ++indA;
            }
            else
            {
                chooseListToAdd(indB->pulse, pulseValid, pulseInvalid);
                ++indB;
            }
        }   
    }
}

void Fus::chooseListToAdd(const Pulse &pulse, ListPulse &pulseValid, ListPulse &pulseInvalid)
{
    if(pulse.isValid)
    {
        addToList(pulse, pulseValid);
    }
    else
    {
        addToList(pulse, pulseInvalid);
    }
}

void Fus::addToList(const Pulse &pulse, ListPulse &listPulse)
{
    if(listPulse.size < listPulse_MAXSIZE)
    {
        listPulse.listPulse[listPulse.size] = pulse;
        listPulse.size++;
    }
}



int main()
{
    Fus fus;
    std::list<Pulse> listPulseA;
    std::list<Pulse> listPulseB;
    static ListPulse pulseValid;
    static ListPulse pulseInvalid;

    Pulse pulse{0, 10, 100, 0, 10, false, false, false};
    for(int i = 0; i < 200000; ++i)
    {
        pulse.timeOfArrival = i * 1000;
        listPulseA.push_back(pulse);
        pulse.timeOfArrival = i * 1000 + 1;
        pulse.duration = 1;
        listPulseB.push_back(pulse);
    }

    fus.processFus(listPulseA, listPulseB, pulseValid, pulseInvalid);

    std::cout << "pulseValid size : "   << pulseValid.size << std::endl;
    std::cout << "pulseInvalid size : " << pulseInvalid.size << std::endl;
}

c++

performance

回答 2

Code Review用户

回答已采纳

发布于 2021-06-09 13:54:15

一些快速的东西.

void Fus::processFus(std::list<Pulse> &listPulseA, std::list<Pulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid) {

我认为其中许多参数应该是const。通过const &传递输入内容，而不仅仅是普通的&。另外，它是正统的C++风格(自80‘S的Stroustrup第一本书开始)，将&与类型放在一起，而不是变量名；例如const std::string& name。

std::list<InfoPulse>::iterator indB = listInfoPulseB.begin();
std::list<InfoPulse>::iterator lastIndB = listInfoPulseB.begin();

使用auto。它简化了一些事情，并使编写易于稍后更改的通用代码变得更容易。

#define THRESHOLD_SEARCH 1.5 // ms, can't change it
#define DIFF_MAX_TOA_A_B 200 // ns
#define MS_TO_NS 1000000

不要使用#define。这些应该是正常变量，声明为constexpr。

 Fus(){}
 virtual ~Fus(){}

使用=default，假设您需要声明它们。

否则，当类中没有虚拟函数时，为什么要将析构函数声明为virtual？显然你不会以多态的方式使用它..。我也看不出有什么东西是从它衍生出来的。

inline bool checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &seuilMatch, const unsigned long long &sumTOADurationA);

inline关键字在类体内声明的函数上是多余的。这里没有功能身体！你认为inline会在这里做什么？

看来，类Fus根本没有任何状态。也就是说，没有数据成员。那么，定义构造函数和析构函数有什么意义呢？

代码对pulseFus做了很多工作，这意味着应该有该类的成员函数(Pulse)。

这些函数操作一个纯的"out“参数，这是不好的。使用函数返回值返回结果！一个简单的例子是

void Fus::createPulse(const Pulse &pulseA, const Pulse &pulseB, Pulse &pulseFus)

应该是这样的

Pulse choose (const Pulse& A, const Pulse& B)
{
   Pulse result = B.quality>4 ? B : A;
   result.isValid= true;
   result.frequency= B.frequency;
   return result;
}

但实际上，Pulse的构造函数应该设置isValid并使用这些值。

while(indA != endA || indB != endB)
    {
        if(indA == endA)
        {
           // take the rest of B only
        }
        else if(indB == endB)
        {
            // take the rest of A only
        }
        else
        {
            // the normal code to choose from the two lists
        }   
    }
}

这是在每次迭代开始时检查结束情况，这不仅效率低下，而且颠倒了代码的顺序。也就是说，在循环中要做的通常事情是在结束时，嵌套在条件语句中。

将循环条件从包含某项内容改为同时包含某项内容，并将化妆内容放在该循环之后。看起来是这样的：

while (indA != endA && indB != endB)
{
   // normal code to choose from the two lists
}
while (indA != endA)
{
   // take the rest of A only
}
while (indB != endB)
{
   // take the rest of B only
}

顺便说一句，ind对end是令人困惑的相似的名字。

 pulse.isValid = 0;
...
 pulse.isValid = 1;

我想你忘了这是bool？您在其他地方使用true和false。

看一看整篇文章：

if(pulse.isRejected || pulse.isTruncated) //Filter
        {
            pulse.isValid = 0;
        }
        else
        {
            pulse.isValid = 1;
        }

您需要认识到，由其他布尔值和操作(如and和OR )组成的布尔表达式与任何其他带有值的表达式没有什么不同。if语句中的内容并不是一种特殊的、独特的东西，而是一种与任何其他语句一样的表达式。当您只想将表达式的结果作为isValid中的值时，这是复杂的。也就是说，写：pulse.isValid = !(pulse.isRejected || pulse.isTruncated);

就这样！没有控制流，额外的大括号，重复意图等。它只是分配给变量的表达式。

请看一下这个函数：

bool Fus::checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &thresholdMatch, const unsigned long long &sumTOADurationA)
{
    const long long tmp = sumTOADurationA - pulseB.sumTOADuration - thresholdMatch;
    if(pulseA.timeOfArrival > pulseB.pulse.timeOfArrival)
    {
        if(tmp < 0 || pulseA.timeOfArrival - pulseB.pulse.timeOfArrival < thresholdMatch)
        {
            return true;
        }
    }
    else
    {
        if(pulseB.pulse.timeOfArrival - pulseA.timeOfArrival < thresholdMatch)
        {
            return true;
        }
    }
    return false;
}

这里有很多重复的地方，而且似乎有很多简单的代码。

pulseA.timeOfArrival - pulseB.pulse.timeOfArrival < thresholdMatch看起来是以不同的方式重复的，但是结构是相同的。也就是说，它应该是一个辅助函数。甚至tmp也是一样的，是以一种奇怪的方式出现的(减去而不是比较，然后通过比较0来使用，而不仅仅是使用布尔值)。内部else只是测试相同的东西，而参数是相反的--这只是翻转结果的符号，这样就可以打破差异，并且测试中使用的符号，而不是重复与关系操作符相同的差异。类似于：

const auto diff = pulseA.timeOfArrival - pulseB.pulse.timeOfArrival;
if (diff > 0) {
   return sumTOADurationA - pulseB.sumTOADuration < thresholdMatch || diff < thresholdMatch;
} else {
   return -diff < thresholdMatch;
}

嗯..。我想这里复杂的因素是unsigned值的使用，所以这是行不通的。你能改变成有符号的值吗?也就是说，你真的需要在这些值中多加一点范围吗？对于无符号值，您仍然可以通过否定结果来翻转减法的顺序；它只是不能作为测试来检查它是否为负值。

性能

不要将std::list用于集合。由于缓存，在内存中跳来跳去很慢。现代的CPU体系结构使得内存成为主要的瓶颈。对于您的输出，您似乎只做了push_back，因此您需要为每个项目分配动态内存。对于输入，您只是遍历，而不是修改列表，对吗？

使用std::vector。使用reserve可以获得更高的性能。访问向量中的输入意味着内存将是连续的，每个缓存行都包含多个值，并且规则的进程将使CPU注意到提前获取所需的下一个内存块--这与链接列表的情况正好相反，在该列表中，需要的下一个地址不能预先确定，而是一些不同(尚未缓存)的内存。

票数 4

Code Review用户

发布于 2021-06-10 15:49:37

接口

真的有必要使用(顺序的) std::list而不是随机访问集合吗？

这个固定大小的结构应该简单地替换为一个std::vector：

结构ListPulse {脉冲listPulselistPulse_最大尺寸；长尺寸= 0；}；

InfoPulse类型似乎没有添加任何值，因为我们只填充了可以根据需要轻松重新计算的派生数据。如果下游确实需要它，那么通过给它构造函数来简化它的创建：

InfoPulse(Pulse p)
    : pulse{std::move(p)},
      sumTOADuration{pulse.timeOfArrival + pulse.duration},
      timePrecision{pulse.timePrecision * LSB_TIME_PRECISION}
{}

类Fus没有数据成员，看起来它应该只是一个函数名称空间。

算法

包括<algorithm>并利用它。例如：

bool keepGoing = true; //Get the first pulse B inside the time window of the pulse A while (keepGoing && indB != listInfoPulseB.end()) { InfoPulse &refPulseB = \*indB; if (refPulseB.pulse.isValid && toaWindowA < refPulseB.pulse.timeOfArrival) { keepGoing = false; lastIndB = indB; } else { ++indB; } }

这看起来很像std::lower_bound()。

我们似乎在列表之间做了太多的复制工作。我不认为我们需要任何中间存储--我们应该能够在内部进行过滤，并填充输出列表，而不需要创建任何其他集合。

我认为代码的复杂性可以大大降低。作为这个代码的新手，我花了很长时间才知道它想做什么。

票数 3

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/262836

复制

相似问题

问合并两个脉冲，如果它们匹配的话
EN

回答 2

Code Review用户

性能

Code Review用户

接口

算法

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问合并两个脉冲，如果它们匹配的话EN

回答 2

Code Review用户

性能

Code Review用户

接口

算法

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问合并两个脉冲，如果它们匹配的话
EN