Perché i FingerTrees non sono sufficientemente utilizzati per avere un'implementazione stabile?

Question

Qualche tempo fa, ho incontrato an article on FingerTrees (Vedi anche an accompanying Stack Overflow Question) e ho archiviato l'idea. Ho finalmente trovato una ragione per farne uso.

Il mio problema è che il Data.FingerTree package sembra avere un po 'di marcatura attorno ai bordi. Inoltre, Data.Sequence nel pacchetto Containers che utilizza la struttura dati re-implements una versione (possibilmente migliore), ma non la esporta.

Come teoricamente utile come sembra essere questa struttura, non sembra avere molto uso o attenzione. Le persone hanno scoperto che i FingerTrees non sono utili come questione pratica, o che questo non è un caso sufficiente?

---

ulteriori spiegazioni:

Sono interessato a costruire un testo che tiene struttura dati che ha buone proprietà di concatenazione. Pensa a costruire un documento HTML da vari frammenti. La maggior parte delle soluzioni pre-costruite usano gli effetti di estrapolazione, ma voglio davvero qualcosa che si occupi correttamente del testo Unicode. Il mio piano al momento è quello di stratificare i frammenti Data.Text in un FingerTree.

Vorrei anche prendere in prestito il trucco da Data.Vector di prendere le fette senza copiare usando (offset, lunghezza) la manipolazione. Data.Text.Text ha questo incorporato nel tipo di dati, ma lo usa solo per efficienti uncons e unsnoc opperations. In FingerTree questa informazione potrebbe facilmente diventare il v o l'annotazione dell'albero.

Answer 1

Per rispondere alla tua domanda sugli alberi da dito in particolare, penso che il problema sia che hanno costi costanti relativamente elevati rispetto agli array e sono più complessi di altri modi per ottenere una concatenazione efficiente. Un Builder ha un'interfaccia più efficiente per l'aggiunta di blocchi, e di solito sono prontamente disponibili (vedi i link nella risposta di @ informatikr). Supponiamo che Data.Text.Lazy sia implementato con un elenco collegato di blocchi e che tu stia creando un Data.Text.Lazy da un costruttore. A meno che tu non abbia molti pezzi (probabilmente più di 50), o stia accedendo ripetutamente ai dati vicino alla fine della lista, probabilmente il costo elevato e costante di un albero delle dita non ne vale la pena.

L'implementazione Data.Sequence è specializzata per motivi di prestazioni e non è generale come l'interfaccia completa fornita dal pacchetto fingertree. Ecco perché non viene esportato; non è davvero possibile usarlo per qualcosa di diverso da un Sequence.

Sospetto anche che molti programmatori non siano in grado di utilizzare effettivamente l'annotazione monoidale, poiché si trova dietro una barriera di astrazione piuttosto significativa. Così tante persone non lo userebbero perché non vedono come possa essere utile rispetto ad altri tipi di dati.

non ho davvero capito fino a quando ho letto il blog di serie Chung Shan-Chieh su word numbers (part2, part3, part4). Questa è la prova che l'idea può essere sicuramente utilizzata nel codice pratico.

Nel tuo caso, se hai bisogno di ispezionare i risultati parziali e avere un'appendice efficiente, usare un fingter potrebbe essere meglio di un costruttore. A seconda dell'implementazione del builder, si può finire per fare un sacco di lavoro ripetuto mentre si converte in Text, aggiungere altro materiale al builder, convertire nuovamente in Text, ecc. Dipende comunque dal proprio modello di utilizzo.

Potresti essere interessato al mio pacchetto splaytree, che fornisce splay tree con annotazioni monoidali, e diverse strutture diverse si basano su di esse. A parte lo splay tree stesso, i moduli Set e RangeSet hanno API più o meno complete, il modulo Sequence è principalmente uno scheletro che ho usato per i test. Non è una soluzione "batterie incluse" per quello che stai cercando (ancora una volta, la risposta di @ informatikr fornisce quelle), ma se vuoi sperimentare le annotazioni monoidali potrebbe essere più utile di Data.FingerTree. Siate consapevoli che uno splay tree può diventare sbilanciato se si attraversano tutti gli elementi in sequenza (o continuamente si agganciano alla fine o simili), ma se le appendici e le ricerche sono interlacciate, le prestazioni possono essere eccellenti.

Answer 2

Ignorando la domanda dell'albero del dito e rispondendo solo alla tua ulteriore spiegazione: hai esaminato Data.Text.Lazy.Builder o, in particolare per la creazione di HTML, blaze-html?

Entrambi consentono una concatenazione rapida. Per affettare, se ciò è importante per risolvere il problema, potrebbero non avere prestazioni ideali.

Answer 3

Oltre alla risposta di John Lato, aggiungerò alcuni dettagli specifici sulle prestazioni degli alberi delle dita, poiché ho passato un po 'di tempo a guardarli in passato.

L'ampia sintesi è:

• Data.Sequence ha grandi fattori costanti e asintotica: è quasi veloce come [] quando si accede alla parte anteriore della lista (in cui entrambe le strutture di dati hanno O (1) asintotica) , e molto più velocemente altrove nella lista (dove gli asintotici logaritmici dello Data.Sequence sono asintotici lineari []).

• Data.FingerTree ha le stesse asintotica come Data.Sequence, ma è di circa un ordine di grandezza più lento.

Proprio come liste, alberi dita hanno alte spese generali di memoria per ogni elemento, per cui dovrebbero essere combinata con la suddivisione in blocchi per una migliore memoria e l'uso della cache. In effetti, alcuni pacchetti lo fanno (yi, trifecta, rope). Se Data.FingerTree potrebbe essere portato vicino a Data.Sequence in termini di prestazioni, mi auguro di vedere un tipo Data.Text.Sequence, che ha implementato un finger tree di valori Data.Text. Un tipo di questo tipo perderebbe il comportamento di streaming di,, ma trarrebbe beneficio da prestazioni migliorate di accesso casuale e concatenazione. (Allo stesso modo, vorrei vedere Data.ByteString.Sequence e Data.Vector.Sequence.)

L'ostacolo alla realizzazione questi ora è che nessuno efficiente e generica realizzazione di alberi delle dita esiste (vedi sotto dove ho discutere questo ulteriore). Per produrre implementazioni efficienti di Data.Text.Sequence è necessario reimplementare completamente le finger tree, specializzate in Text - proprio come Data.Text.Lazy elenchi di reimplementi completamente, specializzati in Text. Sfortunatamente, i finger tree sono molto più complessi degli elenchi (specialmente lo concatenation!), Quindi questa è una quantità considerevole di lavoro.

Così come la vedo io, la risposta è:

• alberi dita specializzati sono grandi, ma un sacco di lavoro per implementare
• Chunked alberi delle dita (per esempio Data.Text.Sequence) sarebbe grande, ma a presentare le scarse prestazioni di Data.FingerTree significa che non sono un'alternativa praticabile agli elenchi di blocchi nel caso comune
• I builder e le liste chunked ottengono molti dei vantaggi di un finger chunk e quindi sono sufficienti per il caso comune
• nel non comune caso in cui i builder e gli elenchi di blocchi non sono sufficienti, stringiamo i denti e sopportiamo gli scarsi fattori costanti degli alberi barrati (ad es. in yi e trifecta).

Ostacoli ad un albero dito efficiente e generico

Gran parte il divario di prestazioni tra Data.Sequence e Data.FingerTree è dovuta a due ottimizzazioni in Data.Sequence:

• Il tipo misura è specializzato per Int, quindi le misurazioni delle manipolazioni si compileranno in un aritmetico intero efficiente piuttosto

• The measure type is unpacked into the Deep constructor, che salva le deviazioni del puntatore nei loop interni delle operazioni dell'albero.

E 'possibile applicare queste ottimizzazioni nel caso generale di Data.FingerTree utilizzando data families for generic unpacking e sfruttando inliner e specialiser di GHC - vedere il mio fingertree-unboxed package, che porta generico prestazioni albero dito quasi fino a quella di Data.Sequence. Purtroppo, queste tecniche hanno alcuni problemi significativi:

• data families for generic unpacking is unpleasant for the user, perché devono definire un sacco di casi. Non esiste una soluzione chiara a questo problema.

• le barrette utilizzano la ricorsione polimorfica, che lo specialista di GHC non gestisce bene (1, 2). Ciò significa che, per ottenere una specializzazione sufficiente sul tipo di misura, abbiamo bisogno di molti pragmi INLINE, che fanno sì che GHC generi enormi quantità di codice.

A causa di questi problemi, non ho mai rilasciato il pacchetto su Hackage.