瓶頸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信號

回答

相關問題