SkipList <T> vs Dictionary <TKey,TValue>

Question

He estado leyendo sobre Skip Lists últimamente.

Tengo una aplicación web que ejecuta consultas Sql bastante complejas contra datasets estáticos.

Quiero implementar un sistema de almacenamiento en caché mediante el cual genero un hash md5 de la consulta sql y luego devuelvo un conjunto de datos en caché para la consulta si existe en la colección.

¿Qué algoritmo sería mejor, Dictionary o SkipList? ¿Por qué?

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

Answer 1

Dictionary, sin duda. Dos razones:

• Dictionary<TKey, TValue> utiliza una tabla hash, haciendo la recuperación de O (1) (es decir la constante de tiempo), en comparación con O (log n ) en una lista de salto.

• Dictionary<TKey, TValue> ya está probado y optimizado, mientras que una clase de lista de omisiones no existe, por lo que tendría que implementar la suya propia, lo que requiere un esfuerzo para hacerlo bien y probarla a fondo.

El consumo de memoria es aproximadamente la misma para ambos (ciertamente la misma complejidad, es decir, O (n)).

Answer 2

La razón por la que usaría un SkipList<T> contra Dictionary<TKey,TValue> es que una lista de omisiones mantiene sus elementos en orden. Si regularmente necesita enumerar los elementos en orden, una lista de omisiones es buena porque puede enumerar en O (n).

Si usted quería ser capaz de enumerar en orden, pero no le importaba si la enumeración es O (n lg n), un SortedSet<T> (o más probablemente un SortedDictionary<TKey, TValue>) sería lo que se desea, ya que utilizan red- árboles negros (árboles binarios equilibrados) y ya están en la biblioteca estándar.

Dado que es extremadamente improbable que desee enumerar su caché en orden (o en absoluto), una lista de omisión (y también un árbol binario) es innecesaria.

Answer 3

Saltar lista proporciona un promedio de Log (n) en todas las operaciones del diccionario. Si se fija la cantidad de elementos, una tabla hash despojada de cerradura tendrá un excelente rendimiento. También es bueno un árbol de splay en la memoria, ya que el caché es la palabra. Los árboles de juego dan más rápido para el elemento de acceso reciente. Como tal en una operación de diccionario como find; [las listas de omisiones fueron lentas en comparación con el árbol desplegable, que de nuevo era lento en comparación con las tablas hash.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

Si se necesita localización en la estructura de datos, las listas de omisiones pueden ser útiles. Por ejemplo, encontrar vuelos alrededor de una fecha, etc. Pero, una memoria caché está en la memoria por lo que un juego es bueno. Los árboles Hashtable y splay no proporcionan localización.