SkipList <T> vs dizionario <TKey,TValue>

Question

Ultimamente ho letto su Skip Lists.

Possiedo un'applicazione Web che esegue query Sql piuttosto complesse con set di dati statici.

Desidero implementare un sistema di memorizzazione nella cache con cui generare un hash MD5 della query sql e quindi restituire un set di dati memorizzato nella cache per la query se esiste nella raccolta.

Quale algoritmo sarebbe meglio, Dizionario o SkipList? Perché?

http://msdn.microsoft.com/en-us/library/ms379573%28VS.80%29.aspx#datastructures20_4_topic4

Answer 1

Dictionary, sicuramente. Due ragioni:

• Dictionary<TKey, TValue> usa una tabella hash, rendendo recupero O (1) (cioè costante di tempo), rispetto a O (log n ) in una skip list.

• Dictionary<TKey, TValue> esiste già ed è ben testato e ottimizzato, mentre una classe skip list non esiste per la mia conoscenza, quindi è necessario implementare la propria, che richiede uno sforzo per farlo bene e testarlo a fondo.

Il consumo di memoria è circa lo stesso per entrambi (certamente la stessa complessità, ovvero O (n )).

Answer 2

Il motivo si utilizza un SkipList<T> vs Dictionary<TKey,TValue> è che una skip list mantiene le sue voci in ordine. Se hai regolarmente bisogno di enumerare gli articoli in ordine, un elenco dei salti è valido perché può essere enumerato in O (n).

Se si voleva essere in grado di elencare in ordine, ma non gli importava se enumerazione è O (n lg n), un SortedSet<T> (o più probabilmente un SortedDictionary<TKey, TValue>) sarebbe quello che ci vuole perché usano red- alberi neri (alberi binari bilanciati) e sono già nella libreria standard.

Poiché è estremamente improbabile che si desideri enumerare la cache in ordine (o non del tutto), una lista di salto (e allo stesso modo un albero binario) non è necessaria.

Answer 3

Skip List fornisce una media di Log (n) su tutte le operazioni del dizionario. Se il numero di elementi è stato risolto, un hash table spogliato del blocco andrà benissimo. Un albero di memoria in memoria è anche buono dato che la cache è la parola. Gli alberi di diffusione danno più velocemente per l'oggetto di recente accesso. Come tale in un'operazione di dizionario come find; [gli elenchi di salti erano lenti rispetto allo splay tree che era di nuovo lento rispetto alle tabelle hash.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

Se la localizzazione nella struttura dei dati è necessaria, saltare le liste può essere utile. Ad esempio, trovare voli intorno a una data, ecc. Ma una cache è in memoria quindi una splay va bene. Hashtable e splay tree non forniscono localizzazione.