瓶颈 C++ 排序函数Wi-Fi 信号

Question

目前我正在制作一个程序，其中我通过使用RSSI估计WiFi设备坐标。该程序包含瓶颈。

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

完整功能：

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

Answer 1

它必须是要返回的 std：：list 吗？否则，您可以通过使用 std：：map 来减少迭代步骤，如下所示：

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

未经测试，但应该可以工作。

Answer 2

我也怀疑字符串比较是否是真正的问题。但是，如果您坚持使用更快的方法来比较MAC字符串，则可以尝试反向比较，因为前缀(OUI(由IEEE提供给供应商，因此对于同一供应商始终相同。

Answer 3

尝试

#include <boost/algorithm/string.hpp>
boost::equals((*it2)->MAC, (*it2)->MAC);

或用于不区分大小写的比较

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

Answer 4

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

而不是你当前的O(n^2)算法，你可以先对MAC列表进行排序(例如，将它们放入std::vector然后使用std::sort(在O(n log n)中，然后只需对排序的向量运行一次迭代，将相邻的相等元素聚合成一个组列表(这是O(n)，整体复杂度为O(n log n)(。

由于有大量 MAC 要分组，像这样的算法复杂性更改可能会导致比尝试优化该单行更大的性能提升。