Frage Wann macht die Verwendung von std :: multimap Sinn?


Ich experimentiere gerade mit der Verwendung von STL-Datenstrukturen. Ich bin mir aber immer noch nicht sicher, wann ich welche Kombination verwenden soll und wann. Momentan versuche ich herauszufinden, wann ich ein std::multimap macht Sinn. Soweit ich sehen kann, kann man leicht seine eigene Multimap-Implementierung durch Kombination aufbauen std::map und std::vector. Somit bleibt mir die Frage, wann diese Datenstrukturen verwendet werden sollten.

  • Einfachheit: Ein std :: multimap ist definitiv einfacher zu benutzen, da man nicht mit der zusätzlichen Verschachtelung umgehen muss. Der Zugriff auf eine Reihe von Elementen als Bulk-Komponente kann jedoch erforderlich sein, um die Daten von den Iteratoren in eine andere Datenstruktur zu kopieren (z. B. a std::vector).
  • Geschwindigkeit: Die Lokalität des Vektors macht es wahrscheinlich sehr viel schneller über den Bereich des gleichen Elements zu iterieren, da die Cache-Nutzung optimiert ist. Aber ich vermute das std::multimaps haben auch viele Optimierungstricks hinter dem Rücken, um über gleiche Elemente so schnell wie möglich zu iterieren. Auch der Zugriff auf den richtigen Elementbereich könnte wahrscheinlich optimiert werden std::multimaps.

Um die Geschwindigkeitsprobleme auszuprobieren, habe ich einige einfache Vergleiche mit folgendem Programm durchgeführt:

#include <stdint.h>
#include <iostream>
#include <map>
#include <vector>
#include <utility>

typedef std::map<uint32_t, std::vector<uint64_t> > my_mumap_t;

const uint32_t num_partitions = 100000;
const size_t num_elements =     500000;

int main() {
  srand( 1337 );
  std::vector<std::pair<uint32_t,uint64_t>> values;
  for( size_t i = 0; i <= num_elements; ++i ) {
    uint32_t key = rand() % num_partitions;
    uint64_t value = rand();
    values.push_back( std::make_pair( key, value ) );
  }
  clock_t start;
  clock_t stop;
  {
    start = clock();
    std::multimap< uint32_t, uint64_t > mumap;
    for( auto iter = values.begin(); iter != values.end(); ++iter ) {
      mumap.insert( *iter );
    }
    stop = clock();
    std::cout << "Filling std::multimap: " << stop - start << " ticks" << std::endl;
    std::vector<uint64_t> sums;
    start = clock();
    for( uint32_t i = 0; i <= num_partitions; ++i ) {
      uint64_t sum = 0;
      auto range = mumap.equal_range( i );
      for( auto iter = range.first; iter != range.second; ++iter ) {
        sum += iter->second;
      }
      sums.push_back( sum );
    }
    stop = clock();
    std::cout << "Reading std::multimap: " << stop - start << " ticks" << std::endl;
  }
  {
    start = clock();
    my_mumap_t mumap;
    for( auto iter = values.begin(); iter != values.end(); ++iter ) {
      mumap[ iter->first ].push_back( iter->second );
    }
    stop = clock();
    std::cout << "Filling my_mumap_t: " << stop - start << " ticks" << std::endl;
    std::vector<uint64_t> sums;
    start = clock();
    for( uint32_t i = 0; i <= num_partitions; ++i ) {
      uint64_t sum = 0;
      auto range = std::make_pair( mumap[i].begin(), mumap[i].end() );
      for( auto iter = range.first; iter != range.second; ++iter ) {
        sum += *iter;
      }
      sums.push_back( sum );
    }
    stop = clock();
    std::cout << "Reading my_mumap_t: " << stop - start << " ticks" << std::endl;
  }
}

Wie ich vermutete hängt es hauptsächlich vom Verhältnis ab num_partitions und num_elementsdeshalb bin ich hier immer noch ratlos. Hier sind einige Beispielausgaben:

Zum num_partitions = 100000 und num_elements = 1000000

Filling std::multimap: 1440000 ticks
Reading std::multimap: 230000 ticks
Filling    my_mumap_t: 1500000 ticks
Reading    my_mumap_t: 170000 ticks

Zum num_partitions = 100000 und num_elements = 500000

Filling std::multimap: 580000 ticks
Reading std::multimap: 150000 ticks
Filling    my_mumap_t: 770000 ticks
Reading    my_mumap_t: 140000 ticks

Zum num_partitions = 100000 und num_elements = 200000

Filling std::multimap: 180000 ticks
Reading std::multimap:  90000 ticks
Filling    my_mumap_t: 290000 ticks
Reading    my_mumap_t: 130000 ticks

Zum num_partitions = 1000 und num_elements = 1000000

Filling std::multimap: 970000 ticks
Reading std::multimap: 150000 ticks
Filling    my_mumap_t: 710000 ticks
Reading    my_mumap_t:  10000 ticks

Ich bin mir nicht sicher, wie ich diese Ergebnisse interpretiere. Wie würden Sie sich für die richtige Datenstruktur entscheiden? Gibt es zusätzliche Einschränkungen für die Entscheidung, die ich vielleicht übersehen habe?


37
2017-12-01 13:54


Ursprung


Antworten:


Es ist schwer zu sagen, ob Ihre Benchmark das Richtige tut, daher kann ich die Zahlen nicht kommentieren. Aber ein paar allgemeine Punkte:

  • Warum multimap anstatt einer Karte von Vektoren: Maps, Multimaps, Sets und Multisets sind alle im Wesentlichen die gleiche Datenstruktur, und sobald Sie eine haben, ist es einfach, alle vier zu buchstabieren. Die erste Antwort lautet also: "Warum? nicht habe es"?

  • Wie ist es sinnvoll?: Multimaps sind eines der Dinge, die Sie selten brauchen, aber wenn Sie sie brauchen, brauchen Sie sie wirklich.

  • Warum nicht meine eigene Lösung rollen lassen? Wie gesagt, ich bin mir über diese Benchmarks nicht sicher, aber sogar ob Sie könnten etwas anderes machen, das nicht schlechter ist als das Standardcontainer (was ich in Frage stelle), dann sollten Sie die Gesamtbelastung in Betracht ziehen, es richtig zu machen, es zu testen und es zu erhalten. Stellen Sie sich eine Welt vor, in der Sie wären besteuert für jede Codezeile, die du geschrieben hast (das ist Stepanovs Vorschlag). Verwenden Sie nach Möglichkeit branchenübliche Komponenten.

Schließlich ist hier die typische Art, wie Sie eine Multimap wiederholen:

for (auto it1 = m.cbegin(), it2 = it1, end = m.cend(); it1 != end; it1 = it2)
{
  // unique key values at this level
  for ( ; it2 != end && it2->first == it1->first; ++it2)
  {
    // equal key value (`== it1->first`) at this level
  }
}

25
2017-12-01 14:08



Sie haben eine sehr wichtige Alternative vergessen: Nicht alle Sequenzen sind gleich.

Vor allem, warum a vector und nicht a deque oder ein list ?

Verwenden list

EIN std::map<int, std::list<int> > sollte ungefähr äquivalent zu a funktionieren std::multimap<int, int> schon seit list ist auch knotenbasiert.

Verwenden deque

EIN dequeist der Standardcontainer, den Sie verwenden können, wenn Sie nicht wissen, wohin Sie gehen und keine besonderen Anforderungen haben.

In Bezug auf die vector, Sie tauschen etwas Lesegeschwindigkeit (nicht viel) für schneller aus push und pop Operationen.

Verwendung einer deque stattdessen und einige offensichtliche Optimierungen, Ich bekomme:

const uint32_t num_partitions = 100000;
const size_t num_elements =     500000;

Filling std::multimap: 360000 ticks
Filling MyMumap:       530000 ticks

Reading std::multimap: 70000 ticks (0)
Reading MyMumap:       30000 ticks (0)

Oder im "schlechten" Fall:

const uint32_t num_partitions = 100000;
const size_t num_elements =     200000;

Filling std::multimap: 100000 ticks
Filling MyMumap:       240000 ticks

Reading std::multimap: 30000 ticks (0)
Reading MyMumap:       10000 ticks (0)

So ist das Lesen bedingungslos schneller, aber das Füllen ist auch viel langsamer.


8
2017-12-01 17:22



Eine Karte von Vektoren enthält den Speicheraufwand für die Kapazität jedes Vektors. std::vector In der Regel wird Platz für mehr Elemente zugewiesen, als Sie tatsächlich haben. Es ist vielleicht keine große Sache für Ihre Anwendung, aber es ist ein weiterer Kompromiss, den Sie nicht berücksichtigt haben.

Wenn Sie viele Lesevorgänge durchführen, wird die O (1) - Suchzeit von unordered_multimap könnte eine bessere Wahl sein.

Wenn Sie einen einigermaßen modernen Compiler haben (und die Anwesenheit des auto Stichwort, Sie tun) dann im Allgemeinen haben Sie eine schwierige Zeit haben, die Standard-Container in Bezug auf Leistung und Zuverlässigkeit zu schlagen. Die Leute, die sie geschrieben haben, sind Experten. Ich würde immer mit dem Standardcontainer beginnen, der am leichtesten ausdrückt, was Sie tun möchten. Profilieren Sie Ihren Code früh und häufig und wenn er nicht schnell genug läuft, suchen Sie nach Möglichkeiten, ihn zu verbessern (z. B. mithilfe der unordered_ Container beim Lesen meistens).

Um also Ihre ursprüngliche Frage zu beantworten, wenn Sie ein assoziatives Array von Werten benötigen, bei denen diese Werte nicht eindeutig sind, verwenden Sie std::multimap macht definitiv Sinn.


7
2017-12-01 14:57