std :: mapa uzyskać wartość - znaleźć vs ręcznie pętli

Question

Mam obiekt std :: map map<string , Property*> _propertyMap, gdzie string jest nazwą nieruchomości i Property* zawiera wartości właściwości.

muszę przetworzyć wartości właściwości i konwertować je do konkretnych danych Format- każda nieruchomość ma swój własny format, na przykład jeśli inicjalizacja mapa jest w następujący sposób:.

_propertyMap["id"] = new Property(Property::UUID, "12345678"); 
_propertyMap["name"] = new Property(Property::STRING, "name"); 
.... 

następnie "id" powinny być przetwarzane inaczej niż "name" itd.

Oznacza to, że muszę wyszukać każdą właściwość na mapie i odpowiednio przetworzyć jej wartości.

Pomyślałem o dwóch sposobach, aby to zrobić.

Jeden użyć std::map::find sposób, aby uzyskać konkretną nieruchomość, tak:

map<string , Property*>::iterator it1 = _propertyMap.find("id"); 
if(it1 != _propertyMap.end()) 
{ 
    //element found - process id values 
} 
map<string , Property*>::iterator it2 = _propertyMap.find("name"); 
if(it2 != _propertyMap.end()) 
{ 
    //element found - process name values 
} 
.... 

Dwa, iteracyjne mapę i dla każdego wpisu sprawdzić co nazwa m.in. jest i postępować odpowiednio:

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it) 
    { 
     //if it is events - append the values to the matching nodes 
     if (it->first == "id") 
     { 
      //process id values 
     } 
     else if (it->first == "name") 
       { 
        //process name values 
       } 
     ..... 
    } 

Biorąc pod uwagę, że Time complexity of std::map::find is O(logN), złożoność pierwszego rozwiązania to O(NlogN). Nie jestem pewien co do złożoności drugiego rozwiązania, ponieważ iteruje on mapę raz (O(N)), ale wykonuje dużo if-else każdej iteracji. Próbowałem odpowiedzieć na wspólne pytania dotyczące map::find(), ale nie mogłem znaleźć żadnych przydatnych informacji; większość z nich wystarczy pobrać jedną wartość z mapy, a następnie find() robi to z większą złożonością (O(logN) vs O(N)).

Jakie jest lepsze podejście? a może jest jeszcze jedna, o której nie myślałem?

Również styl kodowania mówi, który z nich jest lepszym kodem?

Answer 1

widzę kilka różnych przypadków użycia tutaj, w zależności od tego, co masz na myśli:

stałych właściwościach

(Tylko dla kompletności, myślę, że nie jest to, co chcesz) Jeśli zarówno nazwa i Rodzaj ewentualnych właściwości należy ustalić, najlepiej wersja jest użycie prostego klasa/struct, ewentualnie przy użyciu boost::optional (std::optional z C++, 17), do wartości, która może być obecna lub nie

struct Data{ 
    int id = 0; 
    std::string name = ""; 
    boost::optional<int> whatever = boost::none; 
} 

Zalety:

• All "wyszukiwań" są rozwiązywane w czasie kompilacji

Wady:

• brak elastyczności, aby rozwinąć w czasie wykonywania

przetwarzać tylko konkretne opcje w zależności od klucza

Jeśli chcesz przetworzyć tylko określony podzbiór o ale zachowaj opcję posiadania (nieprzetworzonych) kluczy niestandardowych, które wydają się odpowiednie.

W tym przypadku należy pamiętać, że korzystając znaleźć tak:

it1 = _propertyMap.find("id"); 

ma złożoność O (logn), ale służy M razy z M beeing liczbę przetworzonych opcji. To nie jest wielkość mapy, jest to liczba przypadków, w których używaszfind(), aby uzyskać określoną właściwość. W twoim (skróconym) przykładzie oznacza to złożoność O (2 * logN), ponieważ szukasz tylko 2 kluczy.

Zasadniczo użycie M-razy find() skaluje się lepiej niż zapętlanie, gdy zwiększa się tylko rozmiar mapy, ale gorzej, jeśli zwiększysz liczbę znalezionych w ten sam sposób. Ale tylko profilowanie może ci powiedzieć, który z nich jest szybszy dla twojego rozmiaru i przypadku użycia.

Process wszystkie opcje w zależności od rodzaju

Ponieważ mapa wygląda dużo jak klawisze mogą być zwyczaj ale typy są z małego podzbioru rozważyć zapętlenie nad mapą i korzystania typy zamiast nazw w celu określenia jak je przetwarzać. Coś takiego:

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it) 
{ 
    if (it->first.type() == Property::UUID) 
    { 
     //process UUID values 
    } 
    else if (it->first.type() == Property::STRING) 
    { 
     //process STRING values 
    } 
    ..... 
} 

Ma to tę zaletę, że nie trzeba żadnych informacji o tym, co klucze mapy są naprawdę, tylko jakiego rodzaju jest w stanie sklepu.

Answer 2

Załóżmy, że mamy mapę N właściwości i szukamy podzestawu właściwości P. Oto pobieżna analiza, nie znając rozkład statystyczny klawiszy:

• w czystej Mapa dojazdowa szukać P razy z złożoność O (log (n)), czyli O (p * log (n))

• W podejściu łańcuchowym - jeśli będziesz przemierzać mapę. To jest O (N).Ale nie powinieneś zapominać, że łańcuch if-then jest również (hiden) traversal listy elementów P. Tak więc dla każdego z N elementów wykonujesz wyszukiwanie potencjalnie aż do elementów P. Tak więc masz tutaj złożoność O (p * n).

Oznacza to, że podejście do mapy przewyższy Twoje przemieszczenie, a luka wydajnościowa znacząco wzrośnie dzięki n. Oczywiście nie uwzględnia to narzutów funkcji na mapie, których nie ma w łańcuchu. Tak więc, jeśli P i N są małe, twoje podejście może nadal wytrzymywać teoretyczne porównanie.

Co można zrobić, aby w końcu dalszego zwiększenia peformance byłoby użyć unordered_map, która jest O (1) w złożoności, zmniejszając swój problem złożoności O (P).

Answer 3

Jest jeszcze jedna opcja, która łączy w sobie to, co najlepsze. Biorąc pod uwagę funkcję jak ten (który jest adaptacją std::set_intersection):

template<class InputIt1, class InputIt2, 
     class Function, class Compare> 
void match(InputIt1 first1, InputIt1 last1, 
      InputIt2 first2, InputIt2 last2, 
      Function f, Compare comp) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (comp(*first1,*first2)) { 
      ++first1; 
     } else { 
      if (!comp(*first2,*first1)) { 
       f(*first1++,*first2); 
      } 
      ++first2; 
     } 
    } 
} 

Można go używać do przetwarzania wszystkich swoich właściwości w czasie O (N + M) czasowe. Oto przykład:

#include <map> 
#include <string> 
#include <functional> 
#include <cassert> 

using std::map; 
using std::string; 
using std::function; 

struct Property { 
    enum Type { UUID, STRING }; 
    Type type; 
    string value; 
}; 

int main() 
{ 
    map<string,Property> properties; 
    map<string,function<void(Property&)>> processors; 

    properties["id"] = Property{Property::UUID,"12345678"}; 
    properties["name"] = Property{Property::STRING,"name"}; 

    bool id_found = false; 
    bool name_found = false; 

    processors["id"] = [&](Property&){ id_found = true; }; 
    processors["name"] = [&](Property&){ name_found = true; }; 

    match(
     properties.begin(),properties.end(), 
     processors.begin(),processors.end(), 
     [](auto &a,auto &b){ b.second(a.second); }, 
     [](auto &a,auto &b) { return a.first < b.first; } 
    ); 

    assert(id_found && name_found); 
} 

processors mapa może być budowane oddzielnie i ponownie wykorzystane w celu zmniejszenia narzutu.