B-Tree no Factorio

 (razberry.substack.com)
4 pontos por GN⁺ 2023-11-17 | 1 comentários | Compartilhar no WhatsApp
  • Depois de ler o capítulo sobre B-Tree do clube do livro Database Internals, o autor implementou a estrutura de dados não em código, mas como estruturas de fábrica no Factorio, para validar visualmente o conceito
  • A BST só permite ramificações à esquerda e à direita quando as chaves podem ser ordenadas, e, se os valores se concentrarem em um lado, a eficiência da busca pode cair para o nível de uma lista linear
  • Em armazenamento baseado em disco, o custo de rebalanceamento da BST e a necessidade de ler várias páginas são um peso; a B-Tree reduz isso com uma estrutura que guarda várias chaves em um único nó
  • A implementação no Factorio usa baús de madeira e braços filtradores roxos para representar nós e operações de comparação, definindo uma ordem arbitrária de classificação dos itens para criar o caminho de busca
  • A versão com B-Tree usa 3 chaves e 4 ponteiros por nó, armazenando muito mais chaves em 2 níveis do que a BST, mas ainda restam os problemas de representação dos valores e ordenação manual

Diferença entre BST e B-Tree

  • A árvore binária de busca (BST) guarda uma chave em cada nó, enviando chaves menores para o nó da esquerda e maiores para o nó da direita
    • O exemplo começa com a chave raiz 8, 3 à esquerda e 10 à direita
    • Só funciona com valores ordenáveis, em que é possível comparar se uma chave é maior ou menor
  • Se muitos valores forem adicionados apenas de um lado, a BST perde o equilíbrio
    • No pior caso, ela fica quase igual a uma lista linear ordenada como 8 -> 10 -> 14
    • Dá para corrigir o desequilíbrio colocando 10 como raiz e posicionando 8 e 14 em cada lado
  • Em armazenamento baseado em disco, a BST leva desvantagem
    • Manter o rebalanceamento exige atualizações frequentes no disco e nos ponteiros
    • Nós vizinhos podem ficar armazenados em páginas diferentes, então uma única busca pode exigir a leitura de várias páginas
  • A B-Tree guarda várias chaves em um único nó e aponta para nós filhos com número de chaves + 1 ponteiros
    • No exemplo, o nó [17 | 24] se ramifica em três nós filhos: um com chaves menores que 17, outro com chaves entre 17 e 24, e outro com chaves maiores que 24

A árvore de busca implementada dentro do Factorio

  • Factorio é um jogo de construção de fábricas, e nesta implementação cada nó da árvore é representado por estruturas dentro do jogo
  • Primeiro, foi criada uma BST simples
    • Cada nó tem um baú de madeira que guarda uma chave e dois caminhos que levam a outros nós
    • Como não existe um método padrão de comparação entre materiais, foi definida uma ordem arbitrária: wood, coal, stone, brick, copper, iron, steel
    • Os braços filtradores roxos fazem o trabalho de comparação
      • No primeiro nó, um braço verifica se o item é igual a brick
      • O segundo braço testa se ele é menor que brick, como wood, coal, stone
      • O terceiro braço filtra valores maiores, como copper, iron, steel
    • No canto superior direito, também há um coletor de lixo para remover itens que entraram por engano na esteira transportadora
  • A implementação da B-Tree exige mais estruturas em cada nó
    • Cada nó tem 3 chaves, 3 braços filtradores, 3 baús de madeira e 4 ponteiros para filhos
    • Assim, ela consegue armazenar mais informação na mesma profundidade
    • Em 2 níveis, a BST guarda 2 chaves, enquanto a B-Tree guarda 12
    • Em 3 níveis, a B-Tree chega a 48 chaves
  • Como o autor não queria selecionar e ordenar manualmente 48 itens no Factorio, a B-Tree foi deixada vazia até encontrar uma forma melhor de representar os valores
  • O post compara BST e B-Tree lado a lado e também inclui um vídeo no YouTube

Leituras relacionadas

1 comentários

 
GN⁺ 2023-11-17
Comentários do Hacker News

  • É um projeto ineficiente, mas implementar teoria da ciência da computação em Factorio inevitavelmente também significa jogar de um jeito não otimizado
    Factorio não foi feito para exibir uma B-Tree, e no fim as ferramentas também foram projetadas para jogar Factorio

    1. O ponto central de árvores autoequilibradas como árvores 2-3, árvores rubro-negras e B-Tree não é a estrutura de uma única árvore em si, mas a parte em que ela se reequilibra sozinha; como em Factorio não dá para fazer a árvore se reconfigurar por conta própria, sua maior característica fica de fora
    2. Do ponto de vista de otimização, inserters são mais lentos que correias. Mesmo usando 4 inserters por correia, eles movem só cerca de 12 itens por segundo, enquanto uma correia azul empurra 45 por segundo. Num projeto otimizado usando só correias, seria preciso um splitter operando a 45 por segundo
    3. Então o ponto de encontro entre splitters e ciência da computação em Factorio é o splitter do Factorio e a rede de Benes. Se quiser estudar redes feitas apenas com crossbars 2x2, vale começar por https://en.wikipedia.org/wiki/Clos_network. Uma rede de Benes é apenas uma rede de Clos com tamanho 2 entradas, 2 saídas, e redes de Clos podem ter tamanhos arbitrários como 5 por 7
      A meta que dá para encontrar em Factorio parece ser o design de “correia mista”
    • Numa forma mais específica, existe a sushi belt, em que uma única correia carrega vários materiais em equilíbrio e circula sobre si mesma
      Alguns projetos apenas aceitam novos itens em proporções fixas, enquanto outros realmente reequilibram quando a distribuição sai do lugar. Pessoalmente, este é o meu favorito: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Este exemplo usa lógica de circuito do jogo, mas os fóruns de Factorio também têm uma seção sem circuitos: https://forums.factorio.com/viewforum.php?f=202
      O engraçado é que o objeto “fish” de Factorio é um item de piada sem utilidade e, justamente por não ser usado em lugar nenhum, às vezes serve como valor nulo, flag de que a correia completou uma volta, ou ferramenta de depuração: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Fico pensando como seria ter uma extensão do Factorio como “Scriptorio”, que permitisse colocar JSON em cima de correias transportadoras, junto com uma fábrica de funções JavaScript ou Lua
      Aí seria possível mover não apenas os objetos a inserir e buscar, mas também a própria B-Tree com correias e inserters
      Também daria para escrever uma função de busca recursiva com um loop de correia passando pela fábrica, descascando a árvore nível por nível até alcançar a folha, interrompendo o loop e emitindo o resultado
      É um modelo de execução interessante, mais próximo de fluxo de dados do que de JavaScript padrão. Será que se deveria permitir “tunelamento quântico” ou “ação à distância”, fazendo diferentes correias, inserters e fábricas apontarem para o mesmo objeto JSON base por meio de várias referências? Pode ser útil, mas como Factorio tradicionalmente trata cada item físico como tendo uma identidade própria, talvez seja mais “realista” não dar suporte a múltiplas referências. Ou então, depois de pesquisar a tecnologia “Quantum Tunneling JSON”, talvez só a “JSON Reference Entangler Factory” pudesse criar várias referências
    • Dei uma passada rápida no artigo sobre redes de Clos e, se fosse possível montar uma rede dessas em Factorio, parece que também daria para fazer um projeto simples de rede neural como o mostrado aqui: [1]
      Também parece possível mudar a saída aplicando pesos à densidade dos recursos que chegam a posições específicas. Pelo mecanismo mostrado aqui [2], dá a impressão de que seria possível criar decisões ponderadas por densidade com mesclagem/separação e três velocidades de correia
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • Da próxima vez, quero ver se também dá para implementar o autoequilíbrio. Achei que bots seriam úteis aqui, mas não sei se dá para fazer bots construírem projetos dinamicamente
    • É por isso que não jogo Factorio. Esse nível de capacidade mental pode ser usado pela humanidade, e se você mostrar o resultado ainda consegue reação em redes sociais
      Jogos que exigem cérebro em troca de números na tela ficam no fim da minha lista. Eu quero aprender algo novo
      Pode haver um elemento de quebra-cabeça e podemos decidir que isso é divertido, mas não dá para decidir também que estudar é divertido?

  • Trabalho excelente
    Estou lendo “Database Internals” em um clube do livro, e esta semana foi o capítulo 2, que tratava de B-Tree
    Só como referência, as inscrições estão fechadas, mas se quiser você pode conseguir Database Internals e acompanhar em modo “somente leitura” pelo cronograma e pelas notas daqui: https://eatonphil.com/2023-database-internals.html

  • Os motivos pelos quais “árvores de busca binária não são boas para armazenamento em disco” também se aplicam a armazenamento em memória
    Procurar em um único nó de B-Tree é mais rápido do que seguir a mesma quantidade de ponteiros em uma árvore binária. Claro, a complexidade de implementação aumenta, mas, a menos que você esteja usando C, normalmente não vai implementar por conta própria um mapa baseado em árvore
    Também dá para fazer variações colocando mais itens nos nós internos e armazenando os valores apenas nas folhas. Isso se você não estiver fazendo apenas um conjunto em vez de um mapa. Se ainda ligar os nós vizinhos, isso na prática fica parecido com uma skip list

  • Não sei por que justamente conteúdo de Factorio apareceu aqui e me deu vontade de novo de afundar mais umas 100 horas nisso. Este ano já tem jogos bons demais para jogar

    • Como há uma grande reformulação e a expansão Space Age prevista para o fim do ano que vem, talvez não seja má ideia esperar até lá

  • Isso tudo também daria para fazer só com divisores, e talvez nem precisasse de baús nem de manipuladores com filtro. A explicação é boa

    • Não sei como
      Não é só uma questão de dividir a saída em várias linhas. Os baús aqui representam os itens armazenados naquele “nó” específico da B-Tree disposta em 2D
      Não tive tempo de ver o vídeo, mas pelo texto e pelas capturas de tela, há uma lógica acoplada aos manipuladores para mandar os itens pelo caminho do nó filho apropriado, de modo a manter a propriedade “ordenada” da árvore
      Pela escolha dos valores de chave no post original, até daria para dividir com divisores, mas, se bem me lembro, o divisor só aceita um filtro, então seriam necessários vários em cada ponto de ramificação. Ou seja, tantos quanto o número de itens naquele ponto. Como manipuladores com filtro aceitam vários filtros, aqui eles funcionam melhor, e isso também aparece na primeira captura de tela
      Claro, você poderia abandonar completamente o projeto de B-Tree e simplesmente ordenar em n baús com n divisores, mas isso não teria graça e aparentemente não é o que o autor original pretendia
    • Estão atribuindo vários itens a cada manipulador
      O filtro do divisor manda um único tipo de item para um lado e todo o resto para o outro. Mas neste exemplo, vários tipos vão para um lado e vários tipos vão para o outro, então é diferente
    • É preciso ordenar e filtrar vários itens. Por exemplo, no primeiro nó, madeira, carvão e pedra precisam ir para a esquerda, e metal para a direita, mas o filtro do divisor só consegue filtrar um item

  • Fico me perguntando se Factorio é mesmo tudo isso. Todo mundo fala bem, mas esse tema de construir fábricas parece meio entediante, e fico com receio de o jogo ser repetitivo demais

    • Antes de jogar eu também era bem cético e tinha a mesma preocupação. Aí, quando fui ver, já tinha colocado mais de 100 horas
    • Todos os jogadores de Factorio que eu conheço colocaram mais de 1.000 horas

  • É realmente muito legal, mas, falando como alguém que tenta escrever, acho bem distraente não usar maiúsculas no começo das frases

  • Achei que isso seria implementado com o sistema de circuitos do Factorio