SkipList diccionario vs

Question

He estado leyendo acerca de las listas Omitir últimamente.

Tengo una aplicación web que se ejecuta bastante complejas consultas SQL contra conjuntos de datos estáticos.

Quiero poner en práctica un sistema de almacenamiento en caché mediante el cual genero un hash MD5 de la consulta SQL y luego devolver un conjunto de datos en caché para la consulta si existe en la colección.

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

http://msdn.microsoft. com / es-es / 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, constante de tiempo), en comparación con O (log n ) en una lista de salto.

• Dictionary<TKey, TValue> ya existe y está bien probado y optimizado, mientras que una clase de lista de omisión no existe, que yo sepa, por lo que tendría que poner en práctica su propia, lo que requiere de un esfuerzo para hacerlo bien y probarlo 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 utilizaría un SkipList<T> vs Dictionary<TKey,TValue> es que una lista de salto mantiene sus elementos en orden. Si necesita regularmente para enumerar los elementos en orden, una lista de salto es bueno 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 árboles rojo-negro (árboles binarios balanceados) y ya está en la biblioteca estándar .

Ya que es muy poco probable que usted tendrá que enumerar la caché en orden (o en absoluto), una lista de salto (y del mismo modo un árbol binario) es innecesaria.

Answer 3

Lista Saltar da un promedio de log (n) en todas las operaciones del diccionario. Si el número de elementos se fija a continuación, una tabla hash de bloqueos despojado hará grande. Un árbol biselado en la memoria también es bueno ya que la memoria caché es la palabra. árbol biselado dan más rápido para el artículo se ha accedido recientemente. Como tal, en una operación de diccionario como hallazgo; [Omitir listas fueron lento en comparación con árbol biselado que de nuevo eran lentos en comparación con tablas hash.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

Si se necesita la localización en la estructura de datos entonces salte listas pueden ser útiles. Por ejemplo, la búsqueda de vuelos alrededor de una fecha, etc. Pero, una memoria caché está en la memoria por lo que un ensanchamiento está muy bien. Tabla hash y árbol biselado no proporcionan la localización.