SkipList vs Dictionnaire

Question

Je l'ai lu sur les listes de saut ces derniers temps.

J'ai une application Web qui exécute des requêtes SQL assez complexes contre des jeux de données statiques.

Je veux mettre en place un système de mise en cache dans lequel je produis un hachage md5 de la requête SQL puis retourner un ensemble de données en cache pour la requête si elle existe dans la collection.

Quel algorithme serait mieux, Dictionnaire ou SkipList? Pourquoi?

http://msdn.microsoft. com / fr-fr / bibliothèque / ms379573% 28VS.80% 29.aspx # datastructures20_4_topic4

Answer 1

Dictionary, sans aucun doute. Deux raisons:

• Dictionary<TKey, TValue> utilise une table de hachage, ce qui rend la récupération O (1) (temps constant), par rapport à O (log n ) dans une liste de saut.

• Dictionary<TKey, TValue> existe déjà et est bien testé et optimisé, alors qu'une classe de liste de saut n'existe pas à ma connaissance, de sorte que vous auriez à mettre en œuvre vos propres, ce qui demande beaucoup d'efforts pour obtenir ce droit et de le tester à fond .

La consommation de mémoire est de la même pour les deux (certainement la même complexité, à savoir O ( n )).

Answer 2

La raison pour laquelle vous devez utiliser un SkipList<T> vs Dictionary<TKey,TValue> est qu'une liste de saut conserve ses éléments dans l'ordre. Si vous avez besoin régulièrement d'énumérer les éléments dans l'ordre, une liste de saut est bon car il peut énumérer dans O (n).

Si vous voulez être en mesure d'énumérer, mais pour fichais si l'énumération est O (nlogn), un SortedSet<T> (ou plus probablement un

Ignorer la liste donne une moyenne de Log (n) sur toutes les opérations de dictionnaire. Si le nombre d'éléments est fixé alors une table de hachage dépouillé de verrouillage fera grand. Un arbre en mémoire de évasement est aussi bonne depuis le cache est le mot. arbres évasement donnent plus rapidement pour l'élément accédé récemment. En tant que tel dans une opération de dictionnaire comme trouver; [Sauter les listes ont été lents par rapport à l'arbre de évasement qui encore une fois ont été lents par rapport aux tables de hachage.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

Si la localisation dans la structure de données est nécessaire, alors ignorer les listes peuvent être utiles. Par exemple, trouver des vols autour d'une date, etc. Mais, un cache en mémoire si un évasement est très bien. Hashtable et arbres ébrasés ne fournissent pas la localisation.

Answer 3

Answer 4

Answer 5

Answer 6

Answer 7

Ignorer la liste donne une moyenne de Log (n) sur toutes les opérations de dictionnaire. Si le nombre d'éléments est fixé alors une table de hachage dépouillé de verrouillage fera grand. Un arbre en mémoire de évasement est aussi bonne depuis le cache est le mot. arbres évasement donnent plus rapidement pour l'élément accédé récemment. En tant que tel dans une opération de dictionnaire comme trouver; [Sauter les listes ont été lents par rapport à l'arbre de évasement qui encore une fois ont été lents par rapport aux tables de hachage.] [1] [1]: