Integer Map Algorithm [closed]

Ho guardato il codice sorgente del dizionario e ho notato l'uso di "secchi". Non sono esattamente sicuro di come un dizionario ordina gli oggetti in bucket, ma è un compito semplice con numeri interi.

Il problema principale, ho logizzato, è la conversione dell'ingresso in un indice che è il più piccolo possibile ma che non collide con gli indici degli altri input per rendere l'array in cui le uscite sono archiviate il più piccolo possibile, che è dove arrivano i secchi.

Se l'input è 255, l'array non può essere così grande da memorizzare l'output nell'indice di 255. Invece, le operazioni vengono eseguite sul numero per determinare dove viene memorizzato il suo output.

Ecco la mia implementazione. È ottimizzato per il mio uso particolare perché la chiave più grande è 255.

public class FastMap {
    //8 buckets because the maximum key is 255
    public int[][] Buckets = new int[][8];

    public void Add (int input, int output)
    {
        //Finding out which bucket output will be assigned in
        int bucketIndex = input % 32;
        //Finding out the index inside of the bucket the output will be assigned to
        int innerIndex = input / 32;
        //Dropping output into the necessary bucket
        int[] bucket = Buckets[bucketIndex];
        if (bucket == null) 
        {
            bucket = new int[8];
            Buckets[bucketIndex] = bucket;
        }
        bucket[innerIndex] = output;
    }
    public int GetValue (int input)
    {
        return (Buckets[input % 32][input / 32]);
    }
}

Ho intenzione di giocare con questo di più, ma già, la mia implementazione supera Dictionary<int,int> sia nell'uso della memoria sia nelle prestazioni.

Questa risposta è semplicemente fornita per ridurre la frustrazione. In generale, si consiglia a una persona di imparare come condurre il benchmarking delle prestazioni correttamente prima di fare una domanda del genere.

Se le "chiavi" consistono esclusivamente di numeri interi consecutivi, puoi usare un array intero. Gli interi consecutivi basati su zero possono essere utilizzati come indice di matrice così com'è. Gli interi consecutivi non a base zero possono richiedere una rettifica del valore dell'indice prima di utilizzarlo con un array.

Anche se le chiavi non sono strettamente consecutive, in quanto vi sono una piccola quantità di buchi (valori interi non utilizzati tra le chiavi minima e massima), potrebbe essere comunque vantaggioso usare le prestazioni in un array.

Ricorda che l'utilizzo di un array rende il tuo codice fragile (più facilmente interrotto) alle modifiche. Pertanto, analizza attentamente le esigenze attuali e future del tuo progetto e documenta le limitazioni all'interno dei commenti del codice, o in qualche modo rendili evidenti agli utenti del tuo progetto.

Se ci sono alcune funzioni matematiche magiche che mappano le tue chiavi intere nei tuoi valori di ricerca, prova a vedere se sarà più veloce.

Se il dizionario è costruito in modo incrementale (aggiungendo le chiavi una per una), considera di utilizzare il costruttore Dictionary con l'opzione di preallazione della dimensione, con una stima della dimensione massima necessaria. Ciò riduce il tempo speso per la riallocazione e il rehashing.

Come indicato nei commenti di altri, puoi eseguire il benchmark con SortedDictionary (docs) , che è tipicamente, ma non è garantito che sia un albero di ricerca binario.

Se sai che la distribuzione delle tue chiavi integer può avere caratteristiche di distribuzione statistica insolite (ad esempio, tutte le tue chiavi hanno numeri pari e così via), potresti dover implementare una soluzione alternativa:

• A seconda dell'implementazione Dictionary , una soluzione alternativa potrebbe non essere necessaria se è già implementata dall'interno.
• Altrimenti, dovrai applicare una "funzione di diffusione chiave / valanga" alle tue chiavi intere e usare la chiave modificata come indice della tabella hash all'interno di una tipica tabella hash "modulo-N".
  • Una tipica buona scelta (per le tabelle hash) è la funzione MurmurHash3.

Un dizionario int-int ordinato, inizializzato in anticipo e mai modificato, può essere riorganizzato come una matrice di coppie di numeri interi e la ricerca può essere eseguita con la ricerca binaria.

Se la mappatura int-int proviene da alcune funzioni matematiche con tendenze monotone, potrebbe essere possibile eseguire la ricerca della tabella più velocemente della ricerca binaria.