Ignorer la Liste vs Arbre Binaire

Question

Je suis récemment tombé sur la structure de données appelée une Skip list. Ils semblent avoir un comportement très similaire à un arbre de recherche binaire... ma question est, pourquoi voudriez-vous jamais eu envie d'utiliser un saut de liste sur un arbre de recherche binaire?

Answer 1

Skip lists sont plus adaptés à l'accès simultané et/ou de modification. Herb Sutter a écrit un article à propos de la structure de données en simultané environnements. Il a plus de profondeur de l'information.

Le plus fréquemment utilisé pour la mise en œuvre d'une binaire de recherche est un arbre rouge-noir arbre. Les troubles concomitants quand l'arbre est modifié, il a souvent besoin de se rééquilibrer. Le rééquilibrage de l'opération peut affecter de grandes parties de l'arbre, qui aurait besoin d'un mutex lock sur un grand nombre de nœuds de l'arborescence. L'insertion d'un nœud dans une benne de la liste est beaucoup plus localisée, seuls les nœuds directement lié au nœud affecté doivent être verrouillées.

---

Mise à jour de Jon Harrops commentaires

J'ai lu Fraser et Harris dernier papier de la programmation Simultanée sans verrous. Vraiment un bon produit si vous êtes intéressé, sans verrouillage des structures de données. Le document met l'accent sur la Mémoire Transactionnelle et théorique de l'opération groupe de mots-compare-and-swap MCM. Ces deux sont simulés dans un logiciel comme pas de prise en charge matérielle. Je suis assez impressionnée de voir qu'ils ont réussi à construire MCM dans le logiciel.

Je n'ai pas trouver la la mémoire transactionnelle des trucs particulièrement convaincante car elle nécessite un garbage collector. Aussi le logiciel de la mémoire transactionnelle est en proie à des problèmes de performances. Cependant, je serais très heureux si la mémoire transactionnelle matérielle devient de plus en commun. À la fin c'est toujours de la recherche et ne sera pas de l'utiliser pour la production de code pour une autre décennie.

Dans la section 8.2, ils permettent de comparer la performance de plusieurs simultanées arbre implémentations. Je vais résumer leurs conclusions. Il vaut la peine de le télécharger au format pdf qu'il a une très instructif de graphiques sur les pages 50, 53 et 54.

• Verrouillage skip lists sont incroyablement rapide. Elles échelle incroyablement bien avec le nombre d'accès simultanés. C'est ce qui fait sauter des listes spéciales, d'autres de verrouillage basé sur des structures de données ont tendance à crever sous pression.
• Lock-gratuit skip lists sont systématiquement plus rapide que le verrouillage de sauter des listes, mais à peine.
• transactionnelle skip lists sont régulièrement 2 à 3 fois plus lent que le verrouillage et la non-fermeture des versions.
• verrouillage des arbres rouge-noir crever sous les accès concurrents. Leurs performances se dégradent de façon linéaire avec chaque nouvel utilisateur simultané. Les deux connus de verrouillage rouge-noir arbre implémentations, on a essentiellement un verrou global au cours de l'arbre de rééquilibrage. Les autres utilisations de fantaisie (et complexe) de verrouillage de l'escalade, mais ne fonctionne toujours pas de manière significative à effectuer le verrouillage global version.
• sans verrouillage des arbres rouge-noir n'existent pas (n'est plus vrai, voir mise à Jour).
• transactionnelle arbres rouge-noir sont comparables transactionnels skip-lists. C'était très surprenant et très prometteur. La mémoire transactionnelle, bien que plus lent, si bien plus facile à écrire. Il peut être aussi facile que rapide rechercher et remplacer sur le non-cumul version.

---

Mise à jour
Voici le papier de sans verrouillage des arbres: sans Verrouillage des Arbres Rouge-Noir à l'Aide de CAS.
Je n'ai pas regardé profondément, mais sur la surface, il semble solide.

Answer 2

Aussi, en plus des réponses données (facilité de mise en œuvre combinée avec des performances comparables à l'équilibre de l'arbre). Je trouve que la mise en œuvre dans l'ordre de la traversée (en avant et en arrière) est beaucoup plus simple car un skip-list a effectivement une liste liée à l'intérieur de sa mise en œuvre.

Answer 3

Dans la pratique, j'ai trouvé que le B-arbre de performance sur mes projets a travaillé meilleur que skip-lists. Skip lists ne semblent plus facile à comprendre, mais la mise en œuvre d'un B-arbre n'est pas que dur.

Le seul avantage que je sais, c'est que certains les gens intelligents ont travaillé sur la façon de mettre en œuvre un sans verrouillage simultané de sauter de la liste qui utilise uniquement des opérations atomiques. Par exemple, la version 6 de Java contient les ConcurrentSkipListMap classe, et vous pouvez lire le code source, si vous êtes fou.

Mais il n'est pas trop dur à écrire un concurrent B-tree variante non plus - je l'ai vu faire par quelqu'un d'autre - si vous préventivement diviser et fusionner les nœuds juste au cas où que vous marchez dans l'arbre, alors vous n'aurez pas à vous soucier de l'impasse et n'ont besoin que de placer un verrou sur deux niveaux de l'arbre à la fois. La synchronisation des frais généraux sera un peu plus élevé, mais le B-arbre est probablement plus rapide.

Answer 4

À partir de la Wikipedia article que vous avez cité:

Θ(n) opérations, ce qui nous force à visiter tous les nœuds dans l'ordre croissant (telles que l'impression de l'ensemble de la liste) offrent la possibilité d'effectuer une derrière-le-scènes derandomization de la structure de niveau du skip-list de façon optimale, portant le saut liste à O(log n) temps de recherche. [...] Un saut de liste, sur laquelle nous n'avons pas récemment, [une telle] Θ(n) opérations, n'a pas fournir le même pour le pire des cas des garanties de performance comme de plus en plus traditionnelle équilibrée de l'arbre de données les structures, parce qu'il est toujours c'est possible (avec une très faible probabilité) que les coin-flips utilisé pour construire le skip liste va produire un mal équilibré structure

EDIT: c'est donc un compromis à faire: Passer les Listes d'utiliser moins de mémoire, au risque qu'ils pourraient dégénérer en un déséquilibre de l'arbre.

Answer 5

Vous voudrez peut-être chercher à s'écartent des arbres. Ils sont aussi très facile à mettre en œuvre et tendent vers l'équilibre.

Je voudrais essayer d'éviter randomisés rapprochement des algorithmes (par exemple, skip lists) si vous allez écrire des tests unitaires pour la structure de données.