Vraag Waarom zou de kaart veel sneller zijn dan unordered_map?


Ik heb een zoekopdracht in cachegeheugen geïmplementeerd die bestaat uit sleutels van het type State (een klasse met 7 korte ints) en waarden van het type Socre (een klasse van 3 doubles.) Het gebruik van unordered_map was minimaal 20 keer langzamer dan de kaart. Waarom?

Bewerken: Verdorie! Mijn hash-functie was

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  // 1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

Ik vergat te return retval, dus het botste allemaal! Ik wens dat unordered_map een hash_function_quality () functie had die het gemiddelde aantal botsingen rapporteert.


12
2018-01-31 01:07


oorsprong


antwoorden:


De snelheid van ongeordende map is recht evenredig met de snelheid van je hash-functie. Het is nooit een ongecompliceerde relatie. Voorbeeld: als u de eenvoudigste hash-functie gebruikt:

std::size_t myHash(MyObjectType _object){ return 1; }

dan is wat je uiteindelijk krijgt een verzameling die zich gedraagt ​​als een lijst in plaats van een gehashte container. Alle items worden toegewezen aan een enkele emmer en je moet de hele emmer doorlopen totdat je bij het gewenste item bent (iets dat O (N) -tijd kan vergen).

Wat je moet doen, is naar twee dingen kijken:

  1. Welke hashing-functie gebruikt u? Kost het een belachelijke hoeveelheid tijd om te verwerken?
  2. Hoeveel botsingen produceert het? Dat wil zeggen, hoeveel unieke elementen worden toegewezen aan dezelfde hash-waarde?

Elk van deze alleen kan en zal de uitvoering doden.


16
2018-01-31 01:25



std::unordered_map is gewoonlijk traag voor een klein aantal elementen vanwege de hash-functie. Het kost een vaste (-ish) hoeveelheid tijd, maar misschien een aanzienlijke hoeveelheid tijd toch.

std::map aan de andere kant is eenvoudiger dan std::unordered_map. De tijd die het kost om toegang te krijgen tot een element hangt af van het aantal elementen, maar minder en minder naarmate het aantal elementen groeit. En de grote-oh-factor c voor een std: map is vaak ook heel klein, vergeleken met std::unordered_map.

Gebruik in het algemeen de voorkeur std::map over- std::unordered_map, tenzij je een specifieke reden hebt om te gebruiken std::unordered_map. Dit geldt vooral als u niet over een groot aantal elementen beschikt.


8
2018-01-31 01:16



unordered_map gebruikt een hash-tabel onder de motorkap, dus de meest voor de hand liggende reden waarom hash slecht presteert, is omdat je te veel botsingen hebt. U kunt overwegen om een ​​andere, niet standaard, hash-functie te gebruiken die betere resultaten oplevert voor uw type sleutels.


8
2018-01-31 01:24



Voor

Ik wens dat unordered_map een had   hash_function_quality () functie dat   rapporteert het gemiddelde aantal   botsingen.

Ik denk dat de volgende functie nuttig kan zijn.

unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.

Verlaag de load_factor, beter is de hash-functie.


0
2018-01-31 03:38