J'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 souhaite mettre en place un système de mise en cache dans lequel je génère un hasch MD5 de la requête SQL puis de retourner un jeu de données mis en cache pour la requête s'il existe dans la collection.
Quel algorithme serait meilleur, dictionnaire ou skilist? Pourquoi?
3 Réponses :
La consommation de mémoire est à peu près la même pour les deux (certainement la même complexité, à savoir O ( n )). Dictionnaire , définitivement. Deux raisons:
Dictionnaire Dictionnaire
La raison pour laquelle vous utiliseriez un Si vous vouliez pouvoir être en mesure d'énumérer dans l'ordre mais que je ne m'en souciais pas si l'énumération est O (n LG N), un Comme il est extrêmement improbable que vous souhaitiez énumérer votre cache dans l'ordre (ou du tout), une liste de sauts (et également un arbre binaire) est inutile. Lisklist Dictionnaire triède (ou plus probablement a trioddiction ) serait ce que vous" Je veux parce qu'ils utilisent des arbres noirs rouges (arbres bassins équilibrés) et ils sont déjà dans la bibliothèque standard.
Selon la source de recherche, une skilist correctement implémenté peut souvent surperformer une RBTREE, sans oublier que les ressources nécessaires à une skilist sont beaucoup moins que les exigences de ressources RBTREE. J'aimerais voir une comparaison entre skilist et typeDictionnaire ...
DboRarman: Avez-vous une de ces recherches? Si tel est le cas, vous pouvez peut-être commenter sur Stackoverflow. com / questions / 4118109 / ...
La liste de saut donne une moyenne de log (n) sur toutes les opérations de dictionnaire. Si le nombre d'éléments est fixé, une table de hachage enroulée verrouille fera grandement. Une arborescence en mémoire de mémoire est également bonne puisque le cache est le mot. Les arbres de l'épissage donnent plus vite à l'article récemment consulté. Comme tel dans une opération de dictionnaire tel que trouver; [Les listes de saut ont été lentes par rapport à l'arborescence de l'épissure qui étaient à nouveau lentes que les tables de hachage.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dicalay.html
Si la localisation dans la structure de données est nécessaire, les listes de saut peuvent être utiles. Par exemple, trouver des vols autour d'une date, etc. Mais, une cache est en mémoire de sorte qu'une spelie convient. Hashtable et les arborescons d'espoir ne fournissent pas la localisation.
Sur un Sidenote, je me sens obligé de mentionner Memcached.
Suggesting Memcached n'est pas tout ce qui serviable sans un moyen de l'utiliser dans .net sourceforge.net/projects/memcacheddotnet < / a>
Chaque fois que je vois vs je sens la comparaison est défectueuse. Juste pas des pommes aux oranges.