瓶颈C++排序functionWi-Fi信号

目前我正在制作一个程序，使用RSSI估计WiFi设备坐标。该计划包含一个瓶颈。瓶颈C++排序functionWi-Fi信号

我试过用其他函数替换字符串比较。那没

的全部功能：

std::list<std::list<wSignal*>> SignalGrouper::groupByMac (std::list<wSignal*> signals) 
{ 
    std::list<std::list<wSignal*>> groupedSignals; 
    std::list<wSignal*> doneSignals; 
    for (std::list<wSignal*>::iterator it1=signals.begin(); it1 != signals.end(); ++it1) //take first signal 
    { 
     if(DoesSignalExist(doneSignals, *it1) == false) //check if signal is already been grouped 
     { 
      std::list<wSignal*> group; 
      for (std::list<wSignal*>::iterator it2=signals.begin(); it2 != signals.end(); ++it2) 
      { 
       if(DoesSignalExist(doneSignals, *it2) == false) 
       { 
        if(boost::iequals((*it2)->MAC, (*it1)->MAC)) 
        { 
         group.push_back(*it2); 
         doneSignals.push_back(*it2); 
        } 
       } 
      } 
      groupedSignals.push_back(group); 
     } 
    } 
    return groupedSignals; 
}

来源

2017-07-19 Rik Smits

您是如何确定这是瓶颈的？是堆栈轨迹的统计抽样吗？因为如果你有数十亿字符串，代码自然会在'（* it2） - > MAC ==（* it1） - > MAC'上花费很多时间。你不能比专用功能更有效率。 – StoryTeller

'std :: string'比较函数首先检查字符串长度，在这里它们将相等，因为您有2个MAC地址。如果它们相同，则每个字符都将进行比较，直到找到第一个差异或“\ 0”。所以没有更快的方法......正如StoryTeller已经说过的那样：这真的是瓶颈吗？ –

尝试将'signals'更改为以'MAC'为关键字的'std :: map'。 –

它是要返回的std :: list吗？否则，你可以通过使用一个std ::地图这样减少迭代步骤：

std::map<MAC, std::list<wSignal*>> SignalGrouper::groupByMac (std::list<wSignal*> signals) 
{ 
    std::map<MAC, std::list<wSignal*>> groupedSignals; 
    for (std::list<wSignal*>::iterator it1 = signals.begin(); it1 != signals.end(); ++it1) //take first signal 
    { 
     std::map<MAC, std::list<wSignal*>>::iterator it2 = groupedSignals.find((*it1)->MAC); 
     if(it2 != groupedSignals.end()) { 
      it->second.push_back(*it1); 
     } else { 
      groupedSignals[(*it1)->MAC] = (*it1); 
     } 
    } 
    return groupedSignals; 
}

没有测试，但应该工作类似的东西。

来源

2017-07-19 14:50:25 cruesli

'for（auto * signal：signals）{groupedSignals [signal - > MAC] .push_back（信号）; }' – Jarod42

尝试

#include <boost/algorithm/string.hpp> 

boost::equals((*it2)->MAC, (*it2)->MAC);

或区分大小写的比较

boost::iequals((*it2)->MAC, (*it2)->MAC);

来源

2017-07-19 12:20:26 cruesli

像这样改善字符串比较没有用。任何其他的瓶颈可能是什么建议？在这个函数中，我试图将std :: list 排序为较小的std :: list ，其中信号都具有相同的MAC。我想要包含在一个列表中的较小列表：std :: list > –

我也持怀疑态度的字符串比较是否是真正的问题。但是如果你坚持更快的方式来比较MAC字符串，你可以尝试反向比较，因为前缀（OUI）是由IEEE向供应商提供的，因此对于同一供应商来说总是相同的。

来源

2017-07-19 12:44:03 Dassem

不，没有更快的方法来直接比较两个任意字符串。内置方法是最快的方法。

而不是当前的O(n^2)算法，你可以先（通过将它们放入std::vector然后使用std::sort如）在O(n log n)排序的MAC地址列表，然后只需运行一次迭代对有序载体聚集相邻相等的元素成组的列表（其为O(n)，总体复杂度为O(n log n)）。

由于有大量的MAC进行分组，所以像这样的算法复杂度变化可能会导致比试图优化单条线更大的性能增加。

来源

2017-07-19 13:11:54 hnefatl

如何在需要按结构成员排序时对矢量进行排序？（wSignal） –

@RikSmits：你只需要一个比较函数或'operator <'就可以了：https://stackoverflow.com/a/1380496/8051589 –

瓶颈C++排序functionWi-Fi信号

回答

相关问题