Árvores falsas: usar indentação para uma UI mais simples

 (ratfactor.com)
4 pontos por GN⁺ 2024-01-01 | 1 comentários | Compartilhar no WhatsApp
  • Mesmo que uma UI hierárquica pareça necessária, a primeira coisa a verificar é se os dados realmente precisam ter uma relação pai-filho ou se só precisam parecer assim
  • Se uma árvore real não for necessária, é possível representar a estrutura visual usando apenas a ordem de classificação absoluta da lista inteira e um valor de indent, em vez de um ID de pai
  • O editor de jogos Hiss ordena nomes como banana.eat e depois recua o que vem após o ponto (.), criando uma UI que parece namespace
  • Essa abordagem fica mais próxima de uma edição no estilo processador de texto, em que o usuário move itens para cima e para baixo e aumenta ou reduz o recuo, reduzindo a carga de uma estrutura de dados em árvore
  • Se for necessário consultar ou manter de fato a relação entre os itens, será preciso um modelo de árvore real em vez de hacks com indentação ou símbolos em strings

Uma lista que não é árvore, mas parece

  • Ao tentar mostrar uma lista dinâmica como Foo, Bar em uma visão em árvore dentro de um aplicativo, normalmente se pensa em uma estrutura que liga cada item ao seu item pai
  • Em um banco de dados relacional, por exemplo, dá para salvar o ID do pai em uma coluna parent
    • O parent de Foo é null
    • O parent de Foo 1 é Foo
    • O parent de Foo 1.a é Foo 1
  • Para buscar esses dados em árvore com SQL, pode ser necessário usar algo como uma CTE recursiva
  • Mas em muitas listas, pode ser mais importante ter uma aparência organizada para humanos do que uma relação real entre os itens

Salvar o valor de indentação como dado

  • Se a relação pai-filho real não for necessária, a lista pode ser salva apenas com os campos abaixo
    • id
    • sort
    • indent
    • name
  • sort representa a ordem absoluta da lista inteira, não a ordem interna de subitens
  • indent representa diretamente a quantidade de espaço antes do item, o que simplifica a renderização na tela
  • A UI de edição também pode ficar mais simples do que manipular uma árvore
    • O usuário pode mover itens para cima e para baixo
    • O usuário pode aumentar ou reduzir o recuo dos itens
    • Se necessário, é possível adicionar regras simples para forçar uma indentação válida
  • No fim, a experiência fica mais próxima de editar uma lista em um processador de texto do que de manipular diretamente uma estrutura de dados de livro-texto de ciência da computação

O falso namespace baseado em ponto (.) do Hiss

  • O editor de jogos de aventura em texto Hiss mostra nomes como banana, banana.eat, banana.peel como se fossem hierárquicos na UI
  • Isso não significa que o HissScript implemente um recurso real de namespace
  • A implementação é simples
    • Ordena os nomes dos objetos em ordem alfabética
    • Se houver um ponto (.) no nome, corta a parte da frente
    • Exibe o restante com recuo
  • A lógica principal do código de exemplo segue o mesmo fluxo
    • Ordena things.keys
    • Se cada nome tiver um ponto, exibe com recuo e removendo a parte antes do ponto
    • Se não houver ponto, exibe o nome como está
  • Depois, são adicionadas mais algumas linhas para verificar se existe um item “pai” com o prefixo dado
  • Também seria possível adicionar aninhamento com profundidade arbitrária, mas isso está sendo deixado para quando houver necessidade real
  • Essa UI que parece namespace é importante para quem organiza o jogo, mas não tem significado especial para o editor nem para o jogador
    • Um nome com ponto continua sendo apenas um nome
    • A parte que parece namespace serve apenas para manter os nomes únicos

Casos parecidos com árvore tratados como lista plana

  • Dave Long propõe uma forma de salvar caminhos e informações em uma lista plana, chamando isso de “árvore real de baixa tecnologia”
  • A ideia tem uma percepção parecida com o exemplo de banana.eat
  • Dá para imaginar uma lista de caminhos no formato da saída do find, como
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Se for necessário percorrer em profundidade, basta fazer uma ordenação lexicográfica dos caminhos
  • Se for necessário percorrer em largura, é possível inverter os caminhos com base no separador, adicionar itens vazios para alinhar as profundidades e então ordenar
  • Esse exemplo serve para mostrar o conceito; na prática, o natural seria dividir as linhas pelo separador e tratar o resultado como arrays
  • Listas planas, no geral, são fáceis de lidar, e a preferência é usar essa abordagem de colocar os itens em plain old lists sempre que possível

A metáfora do scrapbook no chão

  • Em um scrapbook pessoal, dá para espalhar fotos, bilhetes, cartões-postais e ingressos pelo chão e formar grupos
  • Para uma pessoa, a relação entre os grupos pode parecer óbvia, mas o próprio chão não tem nenhum mecanismo físico que imponha essa relação
  • O ponto central dessa metáfora é que a relação representada e a relação estrutural real podem ser diferentes
  • Com listas em UI acontece o mesmo: uma disposição que parece hierárquica para humanos pode não significar uma hierarquia real no modelo de dados interno

Quando uma árvore real é necessária

  • Abordagens baseadas em indentação ou em símbolos dentro de strings exigem grandes adaptações conforme o contexto e, em contextos gerais de programação, podem acabar sendo vistas como hacks
  • Se for realmente necessário conhecer a relação entre os itens, é melhor usar uma estrutura de árvore real adequada ao modelo de dados, como ID de pai ou tabela de junção pai-filho
  • Se for preciso um nível de organização comparável a armários de arquivo físicos e pastas, como ao classificar grandes projetos de pesquisa, a “abordagem do chão” não é adequada
  • Em projetos nos quais será necessário conhecer de fato a relação entre os itens mais tarde, fingir a estrutura com indentação ou com a quantidade de símbolos em uma string tende a ser um caminho doloroso durante toda a vida útil e manutenção do projeto

Leituras relacionadas

1 comentários

 
GN⁺ 2024-01-01
Opiniões no Hacker News

  • A primeira abordagem, isto é, a que parece “claro que só pode ser assim”, é chamada de lista de adjacência (adjacency list).
    Não me lembro de já ter visto o segundo “método muito mais simples”; ele tem desvantagens óbvias, mas parece suficiente em alguns casos.
    O terceiro, de “namespacing”, é chamado de caminho materializado (materialized path), e também há outra forma de representar árvores, os conjuntos aninhados (nested sets): https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    Na época em que as pessoas levavam bancos de dados relacionais a sério, tudo isso era bem conhecido; há, por exemplo, artigos como http://www.dbazine.com/oracle/or-articles/tropashko4/.
    Hoje parece conhecimento esquecido.

    • Um dos momentos que eu mais odiava no meu antigo trabalho era quando eu me esforçava demais para explicar um problema e alguém reconhecia que aquilo era um conceito já existente, com nome e pesquisa em cima.
      Acho realmente difícil descobrir o nome já existente de um conceito enquanto você está identificando por conta própria as várias facetas do problema.
    • É verdade. Os recém-formados mais jovens que contratamos hoje tentam enfiar tudo em documentos NoSQL e quase não querem pensar em modelagem de dados.
      No fim, toda a lógica para exibir árvores é tratada no código, o que é uma pena, porque bancos de dados relacionais modernos e alguns CTEs já conseguem resolver muitos casos de uso de forma elegante e de graça.
    • É difícil dizer que seja conhecimento esquecido. Também existe o livro “Joe Celko's Trees and Hierarchies in SQL”.
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Se você se interessa por esse tema, recomendo começar procurando os livros de https://en.m.wikipedia.org/wiki/Joe_Celko.

  • O Postgres tem o tipo de dado ltree e operadores de busca que funcionam nativamente desse jeito: https://www.postgresql.org/docs/current/ltree.html
    Por exemplo, você pode inserir algo como CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy');
    e encontrar Top.Science e Top.Science.Astronomy com SELECT path FROM test WHERE path <@ 'Top.Science';.

    • Observação para programadores: uma peculiaridade do ltree é que, se você desenhar isso como uma árvore, os caminhos intermediários que seriam nós pais não precisam existir de fato.
      No exemplo acima, mesmo que você apague o registro Top.Science, o registro Top.Science.Astronomy não é cortado fora.
      Os rótulos de um valor ltree sugerem uma árvore lógica por meio de um caminho materializado, mas não obrigam que existam registros correspondentes a todos os nós pais implícitos.
      Dependendo da aplicação, isso pode ser exatamente o comportamento desejado, ou exatamente o oposto. Se for o segundo caso, é preciso ter algum mecanismo separado para manter a integridade.
    • Fico curioso se, para armazenar caminhos de arquivos, dá para usar / como separador.
    • Fico curioso se alguém tem experiência com desempenho. Parece envolver bastante processamento de regex.
    • O SQL Server também tem um recurso muito parecido[1] e, pelo que já usei, funciona bem.
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Fico curioso se seria possível fazer a mesma coisa com uma coluna JSON. Assim, os nós poderiam usar tipos de dados que não fossem strings.
      Mas me preocupa que índices JSON talvez não funcionem tão bem quanto índices ltree.

  • O problema aqui é que o valor dentro da estrutura geralmente não está em uma árvore para exibição, mas na hierarquia dos dados
    É bem provável que você acabe fazendo coisas como percorrer os dados, mostrar relações ou reordená-los
    Colocar informações visuais na estrutura de dados do banco parece perigoso e míope

    • O autor já deixou claro que “as pessoas sempre acham que precisam codificar formalmente a relação pai-filho, mas na prática nem sempre é assim, às vezes só precisam de uma exibição aninhada”, então essa reação parece meio estranha
      A resposta é “não, isso não pode ser verdade”?
      Há uma razão para YAGNI ser uma heurística de design famosa. “Assuma que sempre vai precisar” não está correto
    • Ironicamente, ainda se está usando ID do pai dentro dos dados
      Ele só foi colocado no começo da string de dados, em vez de ser armazenado em uma coluna dedicada com um tipo de dado otimizado
      Pode não ser um número e pode não ser uma coluna de ID, mas continua sendo um identificador que aponta para outro valor esperado, então mudar o formato não faz com que deixe de ser um ID do pai
    • Mesmo no esquema de codificação por ordem/indentação do texto original, a relação pai-filho deveria ser fácil de reconstruir
      Claro, é preciso garantir que uma indentação inválida, como um filho sem pai, não seja salva
      Por isso, acho que o caminho mais fácil é armazenar primeiro como ordem/profundidade e, quando for implementar as funcionalidades necessárias, migrar para um modelo pai/filho
      Só que “indentação” é melhor definida de forma mais abstrata, como a profundidade na árvore, e não como a quantidade de espaços a renderizar. Isso facilita encontrar dados inválidos, facilita uma migração posterior e também dá flexibilidade de renderização por usuário, como / aninhadas, tabs, 8 espaços, 4 espaços, 1 espaço etc.
    • Se houver uma estrutura de dados como struct item_t { char key[255]; char display_value[255]; }, e a chave tiver um separador de caminho consistente como a/b/c, encontrar pais e filhos é muito fácil
      No pior caso, basta fazer uma busca linear no array; se estiver ordenado, basta olhar os itens anteriores até chegar ao pai
    • Concordo muito. Desnormalização às vezes pode ser uma boa escolha, mas não vejo este caso como uma justificativa razoável

  • Já comecei uma empresa que tinha muitos dados em forma de árvore. Converter uma estrutura de árvore em uma lista indentada é possível em tempo O(n)
    Essa era uma das perguntas de entrevista na época, e há formas de armazenar isso em vários bancos SQL para buscar e renderizar partes de uma árvore rapidamente, mesmo sem consultas recursivas
    Depois que você entende esses conceitos, armazenar os dados corretamente como árvore tem muito mais vantagens do que esse tipo de indentação

    • Se você não precisa dessas vantagens, não importa muito

  • “Uma forma de buscar dados com estrutura de árvore em um banco de dados relacional usando uma consulta SQL é usar CTEs recursivas (Common Table Expressions), que são tão divertidas quanto o nome sugere”
    CTEs, mesmo incluindo CTEs recursivas, não são algo assustador, e garanto que, quando você se acostuma, elas são de fato divertidas

    • CTEs não são exatamente divertidas. Copiar e colar a torre inteira de CTEs em outra janela SQL para depurar a parte que me interessa não é o tipo de entretenimento que eu procuro
    • Ao montar dados de árvore a partir de uma representação normalizada, CTEs recursivas eram extremamente lentas
      Para montar o caminho de um nó com profundidade d na hierarquia, o tempo para obter o resultado da consulta ficava pelo menos d vezes mais lento
      A vantagem era que operações de edição da árvore eram baratas, mas elas aconteciam com muito menos frequência do que leituras
    • CTEs são ok. O autor também poderia ter criado uma view com o nome formatado usando uma CTE, em vez de embutir essa informação na tabela

  • Dá para ver a diferença entre HN e Reddit na ideia de que “as pessoas muitas vezes não querem nem precisam de uma árvore de verdade, só precisam de algo que pareça uma árvore”
    No HN, um comentário filho é o nextSibling do comentário pai, e somam 1 ao valor de indentação do pai para fazê-lo parecer uma árvore
    No Reddit, pelo menos no old.reddit.com, um comentário filho fica de fato aninhado dentro do comentário pai. Não sei como é no site novo

    • Você está falando da estrutura HTML, não da exibição real, certo? O visual na tela é quase idêntico
    • É difícil imaginar que isso seja realmente armazenado assim no backend
      Todas as operações sobre os dados virariam uma bagunça complexa de inferir a estrutura de árvore e depois traduzi-la de volta para um formato de árvore implícito
    • Se for assim, fico curioso sobre como funciona o recolhimento

  • A ideia central do texto é simples: usar a estrutura adequada ao problema
    Mas acho que a narrativa está errada. CTEs não são estritamente necessárias para buscar uma árvore em um banco de dados; dá para buscar uma lista plana e montar a árvore localmente. Para manipulações posteriores, é provável que você faça isso de qualquer forma
    Pela mesma lógica, também daria para dizer a alguém que usa um banco de dados relacional para armazenar uma lista que deveria salvá-la em um arquivo de texto. Por que pagar o custo de latência da rede?
    Por outro lado, na estrutura proposta, mover um ramo e alterar profundidades em uma árvore grande o suficiente não funciona bem, porque tem custo linear
    A intenção deveria ter sido declarada desde o início. Não explicar três exemplos e depois invalidá-los na conclusão com “se você precisa de uma árvore, use uma árvore”. Mas, se isso estivesse no começo do texto, teria sido muito menos caça-clique

  • Tive uma percepção parecida sobre OpenGL alguns anos atrás. Eu não precisava desenhar um mundo de objetos 3D hierárquicos; precisava desenhar uma lista ordenada de triângulos
    Essa ideia virou uma chave na minha cabeça, e várias otimizações ficaram muito fáceis

    • Sim. Em jogos 3D depois de 2000, a simplicidade se tornou uma grande força
      Mesmo em jogos com hierarquias complexas de entidades, ao colocá-las na fila de renderização muitas vezes é preciso achatá-las, por motivos como ordenação por transparência
      A “lista plana de coisas” também é a base de ECS/DOD

  • Há um livro inteiro sobre como lidar com esse tipo de trabalho em bancos de dados
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • Dizem que todo livro é para iniciantes, então ótimo

  • Outra forma de criar árvores falsas é armazenar um blob JSON
    Se os dados tiverem apenas relações internas, isso pode ser mais fácil do que tentar manter números de ordenação únicos e ordenados

    • Uma árvore representada como JSON aninhado pode até ser vista como uma árvore mais “real” do que uma árvore virtual obtida ao armazenar referências ao pai no banco de dados