Inicializando uma estrutura de árvore de dedo

Depois de trabalhar com 2-3 árvores de dedos, fiquei impressionado com a velocidade deles na maioria das operações. No entanto, o único problema que encontrei é a grande sobrecarga associada à criação inicial de uma grande árvore de dedos. Como a construção é definida como uma sequência de operações de concatenação, você acaba construindo um grande número de estruturas de árvores de dedo desnecessárias.

Devido à natureza complexa de 2 a 3 árvores de dedos, não vejo um método intuitivo para inicializá-las, e todas as minhas pesquisas ficaram vazias. Portanto, a pergunta é: como você pode iniciar uma árvore de 2-3 dedos com sobrecarga mínima?

Para ser explícito: dada uma sequência de comprimento conhecido gere a representação da árvore dos dedos de com operações mínimas.$S$$n$$S$

A maneira ingênua de realizar são chamadas sucessivas para a operação contras (na literatura, o operador ' '). No entanto, isso criará estruturas de árvore de dedo distintas, representando todas as fatias de para .n S [ 1 .. i $\triangleleft$$n$$S$$[1..i]$

GHC de Data.Sequence's replicatefunção constrói uma fingertree em tempo e espaço, mas isso é ativado por conhecer os elementos que entram na coluna direita da árvore dedo a partir do get-go. Esta biblioteca foi escrita pelos autores do artigo original em 2-3 dedos.$O(\lg n)$

Se você deseja construir uma árvore de dedos por concatenação repetida, poderá reduzir o uso de espaço transitório enquanto constrói, alterando a representação dos espinhos. Os espinhos em 2-3 árvores de dedos são inteligentemente armazenados como listas vinculadas individualmente sincronizadas. Se, em vez disso, você armazenar os espinhos como deques, poderá ser possível economizar espaço ao concatenar árvores. A idéia é que concatenar duas árvores da mesma altura ocupa espaço reutilizando os espinhos das árvores. Ao concatenar 2 a 3 árvores de dedos, como descrito originalmente, os espinhos internos à nova árvore não podem mais ser usados ​​como estão.$O(1)$

Kaplan e Tarjan, "Representações Puramente Funcionais de Listas Classificadas Catenable", descrevem uma estrutura de árvore de dedos mais complicada. Este artigo (na seção 4) também discute uma construção semelhante à sugestão de deque que fiz acima. Acredito que a estrutura que eles descrevem possa concatenar duas árvores de igual altura em tempo e espaço. Para a construção de árvores de dedos, isso economiza espaço suficiente para você?$O(1)$

NB: O uso da palavra "bootstrapping" significa algo um pouco diferente do uso acima. Eles significam armazenar parte de uma estrutura de dados usando uma versão mais simples da mesma estrutura.

Examinando a excelente resposta do jbapple em relação a replicate, mas usando replicateA(que replicateé construído sobre), eu vim com o seguinte:

--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(em uma versão ligeiramente mais eficiente) já está definido e usado internamente no Data.Sequencepara a construção de árvores de dedo que são resultados de tipos.

Em geral, a intuição para replicateAé simples. replicateAé construído sobre a função applicativeTree . applicativeTreepega um pedaço de uma árvore de um tamanho me produz uma árvore bem equilibrada contendo ncópias disso. Os casos para naté 8 (um único Deepdedo) são codificados. Qualquer coisa acima disso, e ela se invoca recursivamente. O elemento "aplicative" é simplesmente que ele intercala a construção da árvore com efeitos de encadeamento através de, como, no caso do código acima, estado.

A gofunção, replicada, é simplesmente uma ação que obtém o estado atual, retira um elemento da parte superior e substitui o restante. Em cada chamada, portanto, desce a lista fornecida como entrada.

Algumas notas mais concretas

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

Em alguns testes simples, isso resultou em uma troca interessante de desempenho. A função principal acima foi executada quase 1/3 mais baixa com myFromList do que com fromList. Por outro lado, myFromListusou um heap constante de 2 MB, enquanto o padrão fromListusou até 926 MB. Esses 926MB surgem da necessidade de manter a lista inteira na memória de uma só vez. Enquanto isso, a solução myFromListé capaz de consumir a estrutura de forma lenta e lenta. O problema da velocidade resulta do fato de que ele myFromListdeve executar aproximadamente o dobro de alocações (como resultado da construção / destruição do par da mônada do estado) quefromList. Podemos eliminar essas alocações mudando para uma mônada de estado transformada em CPS, mas isso resulta em reter muito mais memória a qualquer momento, porque a perda de preguiça exige que a lista seja percorrida de maneira não contínua.

Por outro lado, se em vez de forçar toda a sequência com um show, passo apenas para extrair a cabeça ou o último elemento, myFromListimediatamente apresenta uma vitória maior - extrair o elemento da cabeça é quase instantâneo e extrair o último elemento é 0,8s . Enquanto isso, com o padrão fromList, extrair a cabeça ou o último elemento custa ~ 2,3 segundos.

Isso são todos os detalhes e é uma consequência da pureza e da preguiça. Em uma situação com mutação e acesso aleatório, eu imaginaria que a replicatesolução é estritamente melhor.

No entanto, levanta a questão de saber se existe uma maneira de reescrever applicativeTreetal que myFromListseja estritamente mais eficiente. Acho que a questão é que as ações do aplicativo são executadas em uma ordem diferente da que a árvore é atravessada naturalmente, mas ainda não trabalhei completamente como isso funciona ou se existe uma maneira de resolver isso.

Enquanto você acaba com um grande número de estruturas intermediárias de árvores de dedos, elas compartilham a grande maioria de sua estrutura umas com as outras. No final, você aloca no máximo duas vezes mais memória que no caso idealizado e o restante é liberado com a primeira coleção. Os assintóticos são os mesmos que podem ser obtidos, pois você precisa de uma árvore digital cheia de n valores no final.

Você pode construir a árvore de dedos usando-os Data.FingerTree.replicatee usando-os FingerTree.fmapWithPospara procurar seus valores em uma matriz que desempenha o papel de sua sequência finita ou usando-os traverseWithPospara separá-los de uma lista ou outro contêiner de tamanho conhecido.

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

$O(\log n)$replicateAmapAccumL

TL; DR Se eu tivesse que fazer isso, provavelmente usaria:

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

e índice em uma matriz de tamanho fixo eu tinha acabado de fornecer (arr !)para facima.