сортировка — узкое место c ++ функция сортировки Wi-Fi сигналы

Question

сортировка — узкое место c ++ функция сортировки Wi-Fi сигналы

В настоящее время я делаю программу, в которой я оцениваю координаты WiFi-устройства, используя RSSI. Программа содержит узкое место.

Я попытался заменить сравнение строк с другими функциями. Это не

Полная функция:

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

0

c++lag linked-list sorting

Решение

Другие решения

Я также скептически отношусь к тому, является ли сравнение строк реальной проблемой. Но если вы настаиваете на более быстром способе сравнения строк MAC, вы можете попробовать сравнить в обратном порядке, поскольку префикс (OUI) предоставляется поставщику IEEE и, следовательно, всегда одинаков для одного и того же поставщика.

1

Пытаться

#include <boost/algorithm/string.hpp>

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

или для сравнения без учета регистра

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

0

Нет, более быстрого способа непосредственного сравнения двух произвольных строк не существует. Встроенный метод — самый быстрый способ.

Вместо вашего текущего O(n^2) Алгоритм, вы могли бы сначала отсортировать список MAC (например, поместив их в std::vector затем с помощью std::sort) в O(n log n)затем просто запустите одну итерацию по отсортированному вектору, чтобы объединить соседние равные элементы в список групп (который O(n)для общей сложности O(n log n)).

При большом количестве групп MAC, вероятно, что изменение сложности алгоритма приведет к большему увеличению производительности, чем попытка оптимизировать эту единственную линию.

0

Источник

Accepted Answer

Это должен быть 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;
}

Не проверено, но должно работать что-то подобное.

1