Pular para o conteúdo
thiagoetipadrões

Contatos

apps/data-patterns/persistent-data-structure

099 · Dados & Persistência · ≈ 5 min de estudo

Persistent Data Structure

Uma estrutura persistente nunca muda no lugar: cada escrita devolve uma versão nova e reaproveita por referência tudo o que não tocou (structural sharing). Em vez de clonar a coleção inteira, só o caminho até o dado alterado é copiado, e todas as versões anteriores continuam válidas em memória. Use para undo/redo e comparação antes/depois sem custo de cópia.

passos
6
arquivos
5
teste
1
tecnologias
3
Lógica puraTypeScriptBunStryker
CenárioRelaçõesComparar
Baixar cartão

Cenário

Mesa de investimentos rebalanceia uma carteira ao longo do dia: compra, venda parcial, ativo novo. O gestor quer comparar qualquer versão com a anterior e desfazer o último rebalanceamento na hora. Copiar o array de posições a cada operação custa O(n); o vetor persistente copia altura + 1 nós.

Planta

Fluxo
8/8
v0 - carteira abertav1 - compra PETR4raiz v0raiz v1ramo 0 a 3ramo 4 a 7ramo 8 a 11folha PETR4, VALE3,ITUB4, BBDC4ramo 0 a 3 - clonadofolha com PETR4 novo - clonadacompartilhadocompartilhado
8

8 passos — reproduza para seguir o fluxo

Como funciona

6 passos

Nova versão sem alterar a anterior.

Esconde cada passo: lembre antes de tocar para revelar.

  1. 01

    PersistentVector guarda as posições num trie de 4 vias; o índice escolhe o filho por grupos de 2 bits

  2. 02

    set clona só os nós do caminho até a folha; os irmãos seguem sendo os mesmos objetos da versão anterior

  3. 03

    push num trie cheio cria uma raiz um nível acima com a raiz antiga como primeiro filho

  4. 04

    positionRebalance e positionAdd devolvem uma InterfacePortfolioVersion nova; a anterior não muda

  5. 05

    nodesNewSince conta por referência quantos nós a versão nova não compartilha com a anterior: sempre altura + 1

  6. 06

    Desfazer é voltar a usar uma versão guardada — nada é recalculado

Trade-offs

O que se ganha, o que se paga

3 vantagenscada ganho tem um preço3 custos

Vantagens

  • Versões antigas válidas sem recomputar

  • Escrita clona O(log n) nós

  • Undo e diff antes/depois de graça

Custos

  • Leitura O(log n) contra O(1) do array

  • Implementação maior que mutação direta

  • Só memória: não substitui persistência durável

apps/data-patterns/persistent-data-structure

5 arquivos

src/

  • persistent_vector.tsTrie de 4 vias com get, set, push por path copying
  • portfolio_version.tsPosições em centavos e versões da carteira
  • demo.tsdemoRebalanceamentos, histórico e undo
  • persistent_vector.test.tstesteImutabilidade, limites, nós clonados e crescimento

./

  • stryker.config.jsoninfraMutação sobre a aritmética do trie

Executar · só Bun

  1. bun install# dependências
  2. bun run demo# roda o cenário
  3. bun run test# testes unitários
  4. bun run test:mutation# mutação com Stryker
Requisitos
Bun

Relações

Onde ele se encaixa

Mapa
  1. Persistent / Immutable Data Structure
  • Combina com3

Por que se relacionam

Combina com

Teste rápido

Qual destes combina com Persistent / Immutable Data Structure?

Próximo projeto · Dados & PersistênciaOffline Locking
Esc

↑ ↓ navegarEnter abrir191 resultados