Schnelle Hash-Funktion für `std :: VECTOR`

Question

implementiert ich diese Lösung einen Hash-Wert aus vector<T> für immer:

namespace std 
{ 
    template<typename T> 
    struct hash<vector<T>> 
    { 
     typedef vector<T> argument_type; 
     typedef std::size_t result_type; 
     result_type operator()(argument_type const& in) const 
     { 
      size_t size = in.size(); 
      size_t seed = 0; 
      for (size_t i = 0; i < size; i++) 
       //Combine the hash of the current vector with the hashes of the previous ones 
       hash_combine(seed, in[i]); 
      return seed; 
     } 
    }; 
} 

//using boost::hash_combine 
template <class T> 
inline void hash_combine(std::size_t& seed, T const& v) 
{ 
    seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

Aber diese Lösung gar nicht maßstäblich: mit vector<double> von 10 Millionen Elementen ist es werde mehr als 2,5 s dauern (laut VS).

Gibt es eine schnelle Hash-Funktion für dieses Szenario?

Beachten Sie, dass das Erstellen eines Hash-Wertes aus der Vektorreferenz keine praktikable Lösung ist, da die zugehörige unordred_map in verschiedenen Läufen verwendet wird und zusätzlich zwei vector<double> mit demselben Inhalt, aber unterschiedliche Adressen werden anders gemappt (unerwünschtes Verhalten für Diese Anwendung).

Answer 1

HINWEIS:Asperthecomments, erhalten Sie ein 25-50x Speed-up mit Optimierungen kompilieren. Mach das zuerst. Dann, wenn es immer noch zu langsam ist, siehe unten.

---

Ich glaube nicht, dass Sie viel tun können. Sie haben, um alle Elemente zu berühren, und diese Kombinationsfunktion ist etwa so schnell wie es geht.

Eine Option kann die Parallelisierung der Hash-Funktion sein. Wenn Sie 8 Kerne haben, können Sie 8 Threads zu jedem Hash 1/8 des Vektors ausführen und dann die 8 resultierenden Werte am Ende kombinieren. Der Synchronisationsaufwand kann sich für sehr große Vektoren lohnen.

Answer 2

Der Ansatz, den MSVCs altes hashmap verwendet, war, weniger häufig zu samplen.

Dies bedeutet, dass isolierte Änderungen nicht in Ihrem Hash angezeigt werden, aber die Sache, die Sie vermeiden möchten, ist das Lesen und Verarbeiten der gesamten 80 MB Daten, um Ihren Vektor zu hashen. Einige Zeichen nicht zu lesen ist ziemlich unvermeidlich.

Das zweite, was Sie tun sollten, ist nicht std::hash auf allen vector s spezialisieren, kann dies Ihr Programm schlecht ausgebildet machen (wie durch einen Defekt Auflösung, deren Status vorgeschlagen, dass ich mich nicht erinnern), und zumindest ein schlechter Plan (wie die std ist sicher, sich selbst zu erlauben, Hash-Kombination und Hashing von Vektoren hinzuzufügen).

Wenn ich einen benutzerdefinierten Hash schreibe, verwende ich normalerweise ADL (Koenig Lookup), um es einfach zu erweitern.

namespace my_utils { 
    namespace hash_impl { 
    namespace details { 
     namespace adl { 
     template<class T> 
     std::size_t hash(T const& t) { 
      return std::hash<T>{}(t); 
     } 
     } 
     template<class T> 
     std::size_t hasher(T const& t) { 
     using adl::hash; 
     return hash(t); 
     } 
    } 
    struct hash_tag {}; 
    template<class T> 
    std::size_t hash(hash_tag, T const& t) { 
     return details::hasher(t); 
    } 
    template<class T> 
    std::size_t hash_combine(hash_tag, std::size_t seed, T const& t) { 
     seed ^= hash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
    } 
    template<class Container> 
    std::size_t fash_hash_random_container(hash_tag, Container const& c) { 
     std::size_t size = c.size(); 
     std::size_t stride = 1 + size/10; 
     std::size_t r = hash(hash_tag{}, size); 
     for(std::size_t i = 0; i < size; i += stride) { 
     r = hash_combine(hash_tag{}, r, c.data()[i]) 
     } 
     return r; 
    } 
    // std specializations go here: 
    template<class T, class A> 
    std::size_t hash(hash_tag, std::vector<T,A> const& v) { 
     return fash_hash_random_container(hash_tag{}, v); 
    } 
    template<class T, std::size_t N> 
    std::size_t hash(hash_tag, std::array<T,N> const& a) { 
     return fash_hash_random_container(hash_tag{}, a); 
    } 
    // etc 
    } 
    struct my_hasher { 
    template<class T> 
    std::size_t operator()(T const& t)const { 
     return hash_impl::hash(hash_impl::hash_tag{}, t); 
    } 
    }; 
} 

jetzt my_hasher ist ein universeller Hasher. Es verwendet entweder Hashes, die in my_utils::hash_impl (für std Typen) deklariert sind, oder freie Funktionen mit der Bezeichnung hash, die einen bestimmten Typ hashen, um Dinge zu hashen. Andernfalls versucht es std::hash<T> zu verwenden. Wenn das fehlschlägt, erhalten Sie einen Kompilierungsfehler.

Schreiben Sie eine kostenlose hash Funktion in den Namespace des Typs, den Sie Hash möchten tendenziell weniger lästig als zu gehen und öffnen std und spezialisieren std::hash in meiner Erfahrung.

Es versteht Vektoren und Arrays rekursiv. Das Ausführen von Tupeln und Paaren erfordert etwas mehr Arbeit.

Es tastet die Vektoren und Arrays ungefähr 10 mal ab.

. (Anmerkung: hash_tag ist sowohl ein bisschen wie ein Witz, und ein Weg, ADL zu zwingen und zu verhindern, mit den hash Spezialisierungen im hash_impl Namespace zukunfts zu erklären, weil diese Anforderung saugt)

Der Preis Sampling ist, dass Sie mehr Kollisionen bekommen könnten.

---

Ein weiterer Ansatz, wenn Sie eine große Menge von Daten haben, ist sie einmal Hash, und zu verfolgen, wenn sie geändert werden. Um diesen Ansatz zu verwenden, verwenden Sie eine Copy-on-Write-Monad-Schnittstelle für Ihren Typ, die verfolgt, ob der Hashwert aktuell ist. Jetzt wird ein Vektor einmal gehackt; Wenn Sie es ändern, wird der Hash verworfen.

Man kann weiter gehen und einen Random-Access-Hash haben (wo es leicht vorhersehbar ist, was passiert, wenn man einen gegebenen Wert hash-weise bearbeitet), und allen Zugriff auf den Vektor vermitteln. Das ist schwierig.

Sie könnten auch das Hashen multi-threading, aber ich würde vermuten, dass Ihr Code wahrscheinlich Speicherbandbreite gebunden ist, und Multithreading wird nicht viel helfen. Einen Versuch wert.

Sie könnten eine feinere Struktur als einen flachen Vektor (etwas baumähnlich) verwenden, bei dem Änderungen an den Werten in einer Hash-ähnlichen Weise zu einem Root-Hash-Wert übergehen. Dies würde einen lg (n) Overhead für alle Elementzugriffe hinzufügen. Auch hier müssten Sie die Rohdaten in Steuerelementen einschließen, die das Hashing auf dem neuesten Stand halten (oder verfolgen, welche Bereiche verschmutzt sind und aktualisiert werden müssen).

Schließlich, weil Sie mit 10 Millionen Elementen gleichzeitig arbeiten, ziehen Sie in Betracht, zu einer starken großen Speicherlösung überzugehen, wie Datenbanken oder was Sie haben. Die Verwendung von 80 Megabyte Schlüsseln in einer Karte erscheint mir seltsam.