Ho un set di funzioni C++. Voglio mappare queste funzioni in una tabella hash, ad esempio: unordered_map<function<ReturnType (Args...)> , SomethingElse>, dove SomethingElse non è rilevante per questa domanda.Generatore di funzioni di hash perfetto per funzioni
Questo set di funzioni è noto in precedenza, piccolo (diciamo meno di 50) e statico (non cambierà).
Poiché le prestazioni di ricerca sono fondamentali (devono essere eseguite in O(1)), desidero definire una funzione di hashing perfetta.
Esiste un generatore di funzioni di hash perfetto per questo scenario?
So che esistono generatori di funzioni di hashing perfette (come GPERF o CMPH) ma poiché non li ho mai usati, non so se sono adatti al mio caso.
MOTIVO:
Sto cercando di progettare un quadro in cui, dato un programma scritto in C++, l'utente può selezionare un sottoinsieme F delle funzioni definite in questo programma.
Per ogni f appartenente al F, il quadro implementa una strategia memoization: quando chiamiamo f con ingresso i, abbiamo memorizzare (i,o) all'interno di qualche struttura dati. Quindi, se chiameremo nuovamente f con i, restituiremo o senza eseguire nuovamente il calcolo (costoso nel tempo).
Il "risultati già calcolati" saranno condivise tra diversi utenti (forse sul cloud), quindi se l'utente u1 ha già calcolato o, utente u2 farà risparmiare tempo di calcolo chiamando f con i (utilizzando la stessa annotazione di prima) .
Ovviamente, abbiamo bisogno di memorizzare l'insieme delle coppie (f,inputs_sets) (dove inputs_sets è il risultati già calcolati set che ho parlato prima), che è la domanda iniziale: come faccio a farlo?
Quindi, utilizzando il "enumerazione trucco" proposto nei commenti a questo scenario potrebbe essere una soluzione, partendo dal presupposto che gli tutti gli utenti utilizzano il esattamente lo stesso enumerazione, che potrebbe essere un problema: supponiamo che il nostro programma ha f1 , f2, f3 cosa succede se u1 vuole Memoize solo f1 e f2 (così F={f1,f2}), mentre u2 vuole Memoize solo f3 (così F={f3})? Una soluzione di overkill potrebbe essere quella di enumerare tutte le funzioni definite nel programma, ma questo potrebbe generare un enorme spreco di memoria.
Le chiavi 'std :: function' non esporranno tutto ciò che è possibile utilizzare per implementare le funzioni di hashing e di uguaglianza necessarie per' unordered_map' - in pratica sei limitato a 'target_type' e' target'. Normalmente non vorrai o ti aspetteresti di limitare le funzioni ad avere diversi 'target_type's, che lascia [' target'] (http://en.cppreference.com/w/cpp/utility/functional/function/target) - un puntatore al bersaglio memorizzato. Mi sembra che possa variare da compilare a compilare, anche per le funzioni extern - difficile da estrarlo, eseguire gperf o simili, modificarlo nel codice e sapere che non sarà cambiato. –
Considerare l'inganno solo dichiarare un'enumerazione (con un valore enum per funzione) e un array const di funzioni e eseguire le 'ricerche' come ricerche di array, utilizzando i valori enum come chiavi? Penso che eviterei completamente il problema di hashing e ti fornisca prestazioni ottimali. –
Come intendi usare la tua mappa? Voglio dire - le tue ricerche sono eseguite solo con un nome esplicito, ad es. 'map.lookup (pippo)', dove 'pippo' è un nome di funzione reale o ci può essere un puntatore di funzione runtime passato come argomento? Se il primo è il caso, probabilmente vorrai che l'hashing sia eseguito anche in fase di compilazione, nel qual caso non è più time-critical. – CygnusX1