瓶颈 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

尝试

#include <boost/algorithm/string.hpp>

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

或不区分大小写的比较

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

Answer 2

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

Answer 3

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

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

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

Answer 4

必须要返回 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;
}

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

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

bottleneck c++ sort functionWi-Fi signals

c++

sorting

linked-list

lag