hashing di tabulazione e N3980

Question

Ho problemi ad adattare la proposta C++ 1z in sospeso N3980 da @HowardHinnant per lavorare con tabulation hashing.

Ab initio computing un hash di tabulazione funziona come per l'algoritmo di hash (Spooky, Murmur, ecc.) Descritto in N3980. Non è così complicato: basta serializzare un oggetto di qualsiasi tipo definito dall'utente tramite hash_append() e lasciare che la funzione hash aggiorni un puntatore in una tabella di numeri casuali mentre procedete.

Il problema inizia quando si tenta di implementare una delle buone proprietà dell'hash di tabulazione: molto economico per calcolare gli aggiornamenti incrementali nell'hash se un oggetto è mutato. Per gli hash di tabulazione "fatti a mano", si ricalcola l'hash dei byte interessati dell'oggetto.

La mia domanda è: come comunicare aggiornamenti incrementali a un oggetto uhash<MyTabulationAlgorithm> funzione, mantenendo fedele al tema centrale del N3980 (Tipi non sanno #)?

per illustrare le difficoltà di progettazione: dire che ho un tipo definito dall'utente X con N membri dati xi di vari tipi Ti

struct X 
{ 
    T1 x1; 
    ... 
    TN xN; 
}; 

Creare ora un oggetto e calcolare il suo hash

X x { ... }; // initialize 
std::size_t h = uhash<MyTabulationAlgorithm>(x); 

Aggiornare un singolo membro e ricalcolare l'hash

x.x2 = 42; 
h ^= ...; // ?? I want to avoid calling uhash<>() again 

Potrei calcolare l'incremento aggiornamento ntale come qualcosa di simile

h ^= hash_update(x.x2, start, stop); 

dove [start, stop) rappresenta la gamma della tabella di numeri casuali che corrispondono all'elemento di dati x2. Tuttavia, al fine di incrementare (cioè a buon mercato!) L'hash per mutazioni arbitrarie, ogni membro di dati deve in qualche modo conoscere il proprio subrange nel flusso di byte serializzato della sua classe contenente. Questo non sembra lo spirito di N3980. Ad esempio, l'aggiunta di nuovi membri di dati alla classe contenente, cambierebbe il layout di classe e quindi gli offset nel flusso di byte serializzato.

Applicazione: l'hashing di tabulazione è molto vecchio, ed è stato recentemente dimostrato che ha proprietà matematiche molto belle (vedere il link di Wikipedia). È anche molto popolare nella comunità di programmazione di giochi da tavolo (scacchi per computer e go e.g.) dove va sotto il nome di Zobrist hashing. In questo caso, la posizione di una scheda assume il ruolo di X e si sposta il ruolo di un piccolo aggiornamento (spostare un pezzo dalla sua origine alla sua destinazione, ad esempio). Sarebbe bello se l'N3980 potesse essere adattato non solo a tale hashing di tabulazione, ma che potesse anche contenere gli economici aggiornamenti incrementali.

Answer 1

Sembra che si dovrebbe essere in grado di fare questo dicendo MyTabulationAlgorithm di ignorare i valori di tutti i membri della classe, tranne ciò che è cambiato:

x.x2 = 42; 
IncrementalHashAdaptor<MyTabulationAlgorithm, T2> inc{x.x2}; 
hash_append(inc, x); 
h ^= inc; 

Tutto IncrementalHashAdaptor ha a che fare è controllare l'intervallo di memoria è passato per vedere se x2 è incluso in esso:

template<class HashAlgorithm, class T> 
struct IncrementalHashAdaptor 
{ 
    T& t; 
    HashAlgorithm h = {}; 
    bool found = false; 
    void operator()(void const* key, std::size_t len) noexcept 
    { 
     if (/* t contained within [key, key + len) */) { 
      assert(!found); 
      found = true; 
      char const* p = addressof(t); 
      h.ignore(key, (p - key)); 
      h(p, sizeof(T)); 
      h.ignore(p + sizeof(T), len - (p - key) - sizeof(T)); 
     } 
     else { 
      h.ignore(key, len); 
     } 
    } 
    operator std:size_t() const { assert(found); return h; } 
}; 

Ovviamente, questo funziona solo per i membri la cui posizione è oggetto sia possibile determinare esternamente e corrisponde al blocco di memoria passata a l'algoritmo di hash; ma questo dovrebbe corrispondere alla stragrande maggioranza dei casi.

Probabilmente vorrai avvolgere hash_append e il seguente hash_append in un'utilità uhash_incremental; questo è lasciato come esercizio per il lettore.

C'è un punto interrogativo sulla prestazione; supponendo che HashAlgorithm::ignore(...) sia visibile al compilatore ed è semplice dovrebbe ottimizzarsi bene; se ciò non si verifica, è possibile calcolare l'indirizzo del flusso di byte di X::x2 all'avvio del programma utilizzando una strategia simile.