L'approccio utilizzato dalla vecchia hashmap di MSVC era di campionare meno spesso.
Ciò significa che le modifiche isolate non verranno visualizzate nel tuo hash, ma la cosa che stai cercando di evitare è la lettura e l'elaborazione dell'intero 80 mb di dati al fine di cancellare il tuo vettore. Non leggere alcuni personaggi è piuttosto inevitabile.
La seconda cosa da fare è non specializzarsi std::hash su tutti vector s, questo potrebbe rendere il vostro programma mal formati (come suggerito da una risoluzione del difetto il cui stato non ricordo), e per lo meno è un cattivo piano (dato che lo std si autorizzerà ad aggiungere una combinazione di hash e l'hashing dei vettori).
Quando scrivo un hash personalizzato, di solito utilizzo ADL (Koenig Lookup) per semplificare l'estensione.
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);
}
};
}
ora my_hasher è un hasher universale. Utilizza gli hash dichiarati in my_utils::hash_impl (per i tipi std) o le funzioni gratuite denominate hash che eseguiranno un hash di un determinato tipo per le hash. In caso contrario, tenta di utilizzare std::hash<T>. Se fallisce, ottieni un errore in fase di compilazione.
Scrivi hash funzione libera nello spazio dei nomi del tipo che si desidera hash tende ad essere meno fastidioso di dover andare fuori e aperto std e specializzarsi std::hash nella mia esperienza.
Comprende vettori e array, in modo ricorsivo. Fare tuple e coppie richiede un po 'più di lavoro.
Esso campiona i vettori e gli array circa 10 volte.
(Nota:. hash_tag è sia un po 'una barzelletta, e un modo per forzare ADL e evitare di dover inoltrare-dichiarare le hash specializzazioni nel hash_impl spazio dei nomi, perché tale obbligo fa schifo)
Il prezzo del il campionamento è che potresti ottenere più collisioni.
Un altro approccio se si dispone di una quantità enorme di dati è di hash loro volta, e tenere traccia di quando vengono modificati. Per fare questo approccio, usa un'interfaccia monad copy-on-write per il tuo tipo che tenga traccia di se l'hash è aggiornato. Ora un vettore ottiene hash una volta; se lo modifichi, l'hash viene scartato.
Uno può andare oltre e avere un hash ad accesso casuale (in cui è facile prevedere cosa succede quando si modifica un determinato valore in modo hash) e mediare tutti gli accessi al vettore. È difficile.
Si potrebbe anche eseguire il multi-thread dell'hashing, ma suppongo che il codice sia probabilmente limitato dalla larghezza di banda della memoria e il multi-threading non sarà di grande aiuto. Vale la pena provare.
È possibile utilizzare una struttura più elaborata di un vettore piatto (simile a una struttura ad albero), in cui le modifiche ai valori aumentano in modo analogo a un valore hash di radice. Ciò aggiungerebbe un overhead lg (n) a tutti gli accessi agli elementi. Ancora una volta, dovresti inserire i dati grezzi nei controlli che mantengono aggiornato l'hashing (o, tenere traccia di quali intervalli sono sporchi e devono essere aggiornati).
Infine, poiché stai lavorando con 10 milioni di elementi alla volta, puoi passare a una soluzione di archiviazione su larga scala, come i database o quello che hai. Usare le chiavi da 80 megabyte in una mappa mi sembra strano.
Utilizzate veramente i vettori di 'double' con 10 milioni di elementi come chiavi? In qualche modo ne dubito. – milleniumbug
Se è così, allora forse prova a calcolare i valori dell'hash prima di ricalcolarli ad ogni accesso chiave. – milleniumbug
@milleniumbug è totalmente possibile in uno scenario di carico elevato con molta RAM. Forse usa un contenitore sbagliato o dovrebbe esaminare le soluzioni non STL – strangeqargo