Liste de saut simultané fonctionnelle Purement

Question

Ignorer les listes (Pugh, 1990) fournissent des dictionnaires triés par ordre logarithmique opérations -time comme des arbres de recherche, mais listes de saut sont beaucoup plus disposés à en même temps des mises à jour .

Est-il possible de créer une liste de saut concurrente purement fonctionnelle efficace? Sinon, est-il possible de créer une sorte de dictionnaire efficace concurrente purement fonctionnelle Sorted?

Answer 1

La propriété des listes de saut qui fait les bons pour les mises à jour simultanées (à savoir que la plupart des additions et des soustractions sont locaux) rend également mauvais pour immuabilité (à savoir que beaucoup d'éléments précédents dans le point de la liste par la suite aux articles plus tard, et devrait être changé).

Plus précisément, les listes de saut de structures se composent qui ressemblent à ceci:

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

Maintenant, si vous avez une mise à jour, par exemple, supprime NODE2b ou NODE1b, vous pouvez prendre soin très localement: vous suffit de pointer 2a à 2c ou 1a à 2a respectivement, et vous avez terminé. Malheureusement, parce que la feuille noeuds tous les points un à l'autre, ce n'est pas une bonne structure pour une mise à jour fonctionnelle (immuable).

Ainsi, les structures d'arbres sont mieux pour immuabilité (comme les dégâts est toujours limitée localement - juste le nœud que vous aimez et ses parents, directement à travers la racine de l'arbre)

.

Mises à jour simultanées ne fonctionnent pas bien avec les structures de données immuables. Si vous pensez à ce sujet, une solution fonctionnelle a une mise à jour de A comme f(A). Si vous voulez deux mises à jour, l'une donnée par f et celle donnée par g, vous avez à peu près à faire f(g(A)) ou g(f(A)), ou vous devez intercepter les requêtes et créer une nouvelle h = f,g opération que vous pouvez appliquer en une seule fois (ou vous doivent faire diverses autres choses très intelligent).

Cependant, en même temps se lit bien le travail fantastiquement avec des structures de données immuables puisque vous êtes assuré d'avoir aucun changement d'état. Si vous ne supposez pas que vous pouvez avoir une boucle de lecture / écriture qui résout avant toute autre écriture peut interrompre, alors vous ne devez verrouiller lecture.

Ainsi, écriture lourdes structures de données sont probablement mieux mis en œuvre mutably (et avec quelque chose comme une liste de saut où il vous suffit de verrouiller localement), alors que les structures de données en lecture lourdes sont probablement mieux mises en œuvre immuablement (où un arbre est un plus structure de données naturelle).

Answer 2

La solution d'Andrew McKinlay est le véritable « vraie » solution fonctionnelle pour une vraie liste de saut, mais il a un inconvénient. Vous payez le temps logarithmique pour accéder à un élément, mais maintenant une mutation au-delà de l'élément de tête devient sans espoir. La réponse que vous voulez est enterré dans d'innombrables copies chemin!

Peut-on faire mieux?

Une partie du problème, il est qu'il ya plusieurs chemins de -infinity à votre article.

Mais si vous pensez à travers les algorithmes de recherche d'un skiplist, vous utilisez jamais ce fait.

On peut penser à chaque nœud dans l'arbre comme ayant un lien préféré, le plus en haut lien depuis la gauche, dans un certain sens peut être considéré comme « posséder » cette entrée.

Maintenant, on peut considérer la notion d'un « doigt » dans une structure de données, ce qui est une technique fonctionnelle qui vous permet de vous concentrer sur un élément particulier, et fournir un retour de chemin à la racine.

Maintenant, nous pouvons commencer par un simple saut-list

-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16

L'expansion par niveau:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8 --------> 16
  |          |            |
  v          v            v
-inf -> 4 -> 8 -> 12 --> 16

Strip tout sauf les pointeurs préférés:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8           16
  |          |            |
  v          v            v
-inf -> 4    8 -> 12     16

Ensuite, vous pouvez déplacer un « doigt » à la position 8 en suivant tous les conseils que vous auriez à retourner pour y arriver.

-inf ------------------> 16
   ^                      |
   |                      v
-inf <------ 8           16
   |         |            |
   v         v            v
-inf -> 4    8 -> 12     16

De là, il est possible de supprimer 8, pousser le doigt quelque part ailleurs, et vous pouvez continuer à naviguer dans la structure avec le doigt.

Regarda cette façon, nous pouvons voir que les chemins privilégiés dans une liste de saut forment un arbre couvrant!

Déplacement 1 étape avec le doigt est un O (1) opération si vous avez seulement des pointeurs privilégiés dans l'arbre et l'utilisation des « nœuds maigres » comme celui-ci. Si vous avez utilisé des noeuds gras, puis un mouvement de doigt vers la gauche / droite serait potentiellement plus cher.

Toutes les opérations restent O (log n) et vous pouvez utiliser une structure de liste ou d'un saut à répartition aléatoire déterministe comme d'habitude.

Cela dit, quand nous rompons la skiplist en une idée d'un chemin préféré nous obtenons qu'un skiplist est juste un arbre avec quelques liens non préférés redondants on n'a pas besoin d'insérer / search / supprimer, de telle sorte que la longueur de chacun de ces chemins de la partie supérieure droite est O (log n) soit avec une forte probabilité ou garantis en fonction de votre stratégie de mise à jour.

Même sans le doigt vous pouvez maintenir O (log n) prévu par insertion / suppression / mise à jour dans un arbre avec cette forme.

Maintenant, le mot clé de votre question qui n'a pas de sens est « concurrente ». Une structure de données purement fonctionnelle ne dispose pas d'une notion de mutation en place. Vous produisez toujours une chose nouvelle. Dans un certain sens des mises à jour fonctionnelles simultanées sont faciles. Tout le monde a sa propre réponse! Ils ne peuvent pas voir les uns les autres.

Answer 3

Pas une liste de saut, mais semble correspondre à la description du problème: persistants arbres rouge-noir de Clojure (voir PersistentTreeMap.java ). La source contient cet avis:

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

Ces arbres maintiennent l'ordre des éléments et sont « persistants » dans le sens où Rich Hickey utilise le mot (et immuable en mesure de maintenir leurs garanties de performance que les versions mises à jour sont construits).

Si vous voulez jouer avec eux, vous pouvez construire des instances dans le code Clojure avec la fonction sorted-map.

Answer 4

Si vous ne devez contre sur le devant de la liste de saut, alors il devrait être possible de faire une persistante la version immuable.

L'avantage de ce genre de liste saut serait l'accès « au hasard ». par exemple. Vous pouvez accéder à l'élément n'th plus rapide que vous pourriez dans une liste unique liée régulière.