Amorçage d'une structure d'arbre à doigts

Après avoir travaillé avec 2-3 arbres à doigts pendant un bon moment, j'ai été impressionné par leur vitesse dans la plupart des opérations. Cependant, le seul problème que j'ai rencontré est la surcharge importante associée à la création initiale d'un grand arbre à doigts. Parce que la construction est définie comme une séquence d'opérations de concaténation, vous finissez par construire un grand nombre de structures d'arbre à doigts qui ne sont pas nécessaires.

En raison de la nature complexe des arbres à 2-3 doigts, je ne vois aucune méthode intuitive pour les amorcer, et toutes mes recherches sont vides. La question est donc de savoir comment démarrer un arbre à 2-3 doigts avec un minimum de frais généraux.

Pour être explicite: étant donné une séquence de longueur connue générez l'arborescence des doigts de avec des opérations minimales.$S$$n$$S$

La façon naïve d'accomplir est d'appeler successivement l'opération contre (dans la littérature l' opérateur ' '). Cependant, cela créera structures d'arbre à doigts distinctes représentant toutes les tranches de pour .$\triangleleft$$n$$S$$[1..i]$

De GHC Data.Sequencede replicatefonction construit une fingertree en le temps et l' espace, mais cette option est activée en connaissant les éléments qui vont sur la colonne vertébrale droite de l'arbre du doigt du get-go. Cette bibliothèque a été écrite par les auteurs de l'article original sur 2-3 arbres à doigts.$O(\lg n)$

Si vous souhaitez créer un arbre de doigt par concaténation répétée, vous pourrez peut-être réduire l'utilisation d'espace transitoire lors de la construction en modifiant la représentation des épines. Les épines sur les arbres à 2-3 doigts sont intelligemment stockées sous forme de listes synchronisées à lien unique. Si, au lieu de cela, vous stockez les épines en tant que deques, il peut être possible d'économiser de l'espace lors de la concaténation des arbres. L'idée est que la concaténation de deux arbres de même hauteur prend de l' espace en réutilisant les épines des arbres. Lors de la concaténation de 2-3 arbres à doigts, comme décrit à l'origine, les épines internes au nouvel arbre ne peuvent plus être utilisées telles quelles.$O(1)$

Les «Représentations purement fonctionnelles des listes triées caténables» de Kaplan et Tarjan décrivent une structure d'arbre à doigts plus compliquée. Cet article (dans la section 4) traite également d'une construction similaire à la suggestion deque que j'ai faite ci-dessus. Je crois que la structure qu'ils décrivent peut concaténer deux arbres de hauteur égale dans le temps et l'espace . Pour construire des arbres à doigts, est-ce assez d'espace pour vous?$O(1)$

NB: Leur utilisation du mot "bootstrapping" signifie quelque chose d'un peu différent de votre utilisation ci-dessus. Cela signifie stocker une partie d'une structure de données en utilisant une version plus simple de la même structure.

En me basant sur l'excellente réponse de jbapple concernant replicate, mais en utilisant replicateA(qui replicateest construit sur) à la place, j'ai trouvé ce qui suit:

--Unlike fromList, one needs the length explicitly. 
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
    where go = do
           (y:ys) <- get
            put ys
            return y

myFromList(dans une version plus légère efficace) est déjà défini et utilisé en interne dans Data.Sequencepour la construction d' arbres de doigts qui sont les résultats de toutes sortes.

En général, l'intuition de replicateAest simple. replicateAest construit au-dessus de la fonction applicativeTree . applicativeTreeprend un morceau d'arbre d'une taille met produit un arbre bien équilibré contenant des ncopies de celui-ci. Les cas pour njusqu'à 8 (un seul Deepdoigt) sont codés en dur. Tout ce qui est au-dessus de cela, et il s’invoque récursivement. L'élément "applicatif" est simplement qu'il entrelace la construction de l'arbre avec des effets de filetage à travers, comme, dans le cas du code ci-dessus, l'état.

La gofonction, qui est répliquée, est simplement une action qui obtient l'état actuel, fait apparaître un élément par le haut et remplace le reste. A chaque appel, il descend ainsi plus loin dans la liste fournie en entrée.

Quelques notes plus concrètes

main = print (length (show (Seq.fromList [1..10000000::Int])))

Sur certains tests simples, cela a donné un compromis intéressant sur les performances. La fonction principale ci-dessus a fonctionné presque 1/3 de moins avec myFromList qu'avec fromList. D'autre part, myFromListutilisé un tas constant de 2 Mo, tandis que la norme fromListutilisait jusqu'à 926 Mo. Ce 926 Mo découle de la nécessité de conserver la liste entière en mémoire à la fois. Pendant ce temps, la solution avec myFromListest capable de consommer la structure en mode streaming paresseux. Le problème de la vitesse résulte du fait qu'il myFromListdoit effectuer environ deux fois plus d'allocations (en raison de la construction / destruction de la paire de la monade d'État) quefromList. Nous pouvons éliminer ces allocations en passant à une monade d'état transformée par CPS, mais cela aboutit à conserver beaucoup plus de mémoire à un moment donné, car la perte de paresse nécessite de parcourir la liste de manière non continue.

D'un autre côté, si plutôt que de forcer toute la séquence avec un spectacle, je passe à l'extraction de la tête ou du dernier élément, myFromListprésente immédiatement un gain plus important - l'extraction de l'élément de tête est presque instantanée, et l'extraction du dernier élément est de 0,8 s . Pendant ce temps, avec la norme fromList, l'extraction de la tête ou du dernier élément coûte environ 2,3 secondes.

Ce ne sont que des détails et une conséquence de la pureté et de la paresse. Dans une situation de mutation et d'accès aléatoire, j'imagine que la replicatesolution est strictement meilleure.

Cependant, cela soulève la question de savoir s'il existe un moyen de réécrire applicativeTreece qui myFromListest strictement plus efficace. Le problème est, je pense, que les actions applicatives sont exécutées dans un ordre différent de celui de l'arbre qui est naturellement traversé, mais je n'ai pas complètement expliqué comment cela fonctionne, ou s'il existe un moyen de résoudre ce problème.

Alors que vous vous retrouvez avec un grand nombre de structures intermédiaires au bout des doigts, elles partagent la grande majorité de leur structure les unes avec les autres. À la fin, vous allouez au plus deux fois plus de mémoire que dans le cas idéal, et le reste est libéré avec la première collection. Les asymptotiques sont les mêmes que possible, car vous avez besoin d'un bout de doigt rempli de n valeurs à la fin.

Vous pouvez construire le bout des doigts en utilisant Data.FingerTree.replicateet en les utilisant FingerTree.fmapWithPospour rechercher vos valeurs dans un tableau qui joue le rôle de votre séquence finie, ou en les utilisant traverseWithPospour les décoller d'une liste ou d'un autre conteneur de taille connue.

$O(\log n)$$O(n)$$O(\log n)$

$O(\log n)$replicateAmapAccumL

TL; DR Si je devais le faire, j'utiliserais probablement:

rep :: (Int -> a) -> Int -> Seq a 
rep f n = mapWithIndex (const . f) $ replicate n () 

et à l' index dans un tableau de taille fixe que je venais de fournir (arr !)pour fci - dessus.