Skip Lists - les avez-vous déjà utilisées?

StackOverflow https://stackoverflow.com/questions/234560

Question

Je me demande si quelqu'un ici a déjà utilisé une ignorer la liste . Il semble avoir à peu près les mêmes avantages qu'un arbre binaire équilibré mais est plus simple à mettre en œuvre. Si oui, avez-vous écrit la vôtre ou utilisez-vous une bibliothèque pré-écrite (et si oui, quel était son nom)?

Était-ce utile?

La solution

Il y a des années, j'ai mis en œuvre le mien pour une classe d'algorithmes probabilistes. Je ne suis au courant d'aucune implémentation de bibliothèque, mais cela fait longtemps. C'est assez simple à mettre en œuvre. Si je me souviens bien, ils possédaient de très bonnes propriétés pour les grands ensembles de données et évitaient certains problèmes de rééquilibrage. Je pense que la mise en œuvre est aussi plus simple que les essais binaires en général. Il y a une bonne discussion et un exemple de code c ++ ici:

http://www.ddj.us/cpp/184403579?pgno=1

Il existe également une applet avec une démonstration en cours. La brillance de Java mignonne des années 90 ici:

http://www.geocities.com/siliconvalley/network/1854 /skiplist.html

Autres conseils

D'après ce que j'ai compris, ils ne constituent pas une alternative utile à les arbres binaires (par exemple, les arbres rouge-noir), mais plutôt à les arbres B pour l'utilisation de la base de données. afin que vous puissiez limiter le nombre de niveaux au minimum réalisable et traiter les journaux avec base-K plutôt que les journaux base-2 pour obtenir des caractéristiques de performance. Les algorithmes pour les listes de probabilité probabilistes sont (IMHO) plus faciles à obtenir que les algorithmes B-tree correspondants. De plus, il y a de la littérature sur des listes de sauts sans verrouillage. J’ai envisagé de les utiliser il ya quelques mois, mais j’ai abandonné l’effort de découverte de la bibliothèque HDF5 .

littérature sur le sujet:

Articles de Bill Pugh:

articles non académiques / tutoriels:

En fait, pour l’un de mes projets, je mets en œuvre ma propre STL complète. Et j’ai utilisé un skipliste pour implémenter mon std :: map . La raison pour laquelle je l’ai choisi est qu’il s’agit d’un algorithme simple, très proche des performances d’un arbre équilibré, mais qui offre beaucoup des capacités d’itération plus simples.

En outre, le QMap de Qt4 était également un skipliste qui a inspiré à l'origine mon utilisation dans mon std :: map .

Java 1.6 (Java SE 6) a présenté ConcurrentSkipListSet et ConcurrentSkipListMap au cadre des collections. Donc, je suppose que quelqu'un les utilise vraiment.

Les skiplistes ont tendance à proposer beaucoup moins de conflits pour les verrous dans une situation multithread et ont (de manière probabiliste) des performances similaires à celles des arbres.

Voir l'article original [pdf] par William Pugh.

Il y a quelques années, j'ai implémenté une variante que j'ai appelée liste de sauts inversée pour un moteur de règles. De la même manière, mais les liens de référence partent du dernier élément.

Cela s'explique par le fait qu'il était plus rapide d'insérer des éléments triés qui se trouvaient le plus probablement dans le fond de la collection.

Il a été écrit en C # et a pris quelques itérations pour fonctionner correctement.

Les listes de sauts sont faciles à mettre en œuvre. Mais, en ajustant les pointeurs sur une liste à sauter en cas d’insertion et de suppression, vous devez faire attention. Je n'ai pas utilisé cela dans un vrai programme, mais j'ai déjà fait du profilage à l'exécution. Les listes de sauts sont différentes des arbres de recherche. La similitude est que, il donne la moyenne log (n) pour une période d'opérations de dictionnaire, tout comme l'arbre splay. C'est mieux qu'un arbre de recherche non équilibré mais ce n'est pas mieux qu'un arbre équilibré.

Chaque nœud de la liste de saute a des pointeurs de transfert qui représentent les connexions actuelles - > next () aux différents niveaux de la liste de sauts. En règle générale, ce niveau est limité à un maximum de ln (N). Donc, si N = 1 million, le niveau est 13. Il y aura autant de pointeurs et en Java, cela signifie deux fois le nombre de pointeurs pour la mise en oeuvre de types de données de référence. où comme un arbre de recherche équilibré a moins et donne le même temps d'exécution !!.

SkipList vs Splay Tree Vs Hash

Non affilié à StackOverflow
scroll top