Coisas que eu gostaria de saber antes de desenvolver um autorouter
(blog.autorouting.com)- A experiência de cerca de 1 ano desenvolvendo um autorouter de PCB open source para o tscircuit mostrou que projetos que reduzem o problema de busca, como A*, visualização, particionamento espacial e cache, são a chave do desempenho
- O foco da otimização está em reduzir o número de iterações, mais do que na linguagem ou na velocidade de uma única iteração; mesmo em JavaScript, um algoritmo mais inteligente e com cache pode ser mais rápido do que uma implementação de baixo nível
- Em busca espacial, um Spatial Hash Index pode ser mais simples e rápido do que árvores genéricas como QuadTree, mas uma escolha ruim do tamanho das células pode gerar um alto custo fixo em cada consulta
- Um pipeline complexo de autorouter precisa visualizar as entradas e saídas de cada etapa e verificar o processo iterativo com animações; funções recursivas e abordagens Monte Carlo são desvantajosas em depuração, otimização e determinismo
- Com Weighted A*, o Greedy Multiplier permite abrir mão de parte da otimalidade para ganhar muita velocidade, e cada etapa deve reduzir a probabilidade de falha para deixar o estado mais fácil para as etapas seguintes resolverem
Usar A* como ferramenta padrão de busca
- A* não é um algoritmo exclusivo para grades 2D, mas um algoritmo-base aplicável a várias formas de busca informada (informed search)
- O BFS explora todos os nós vizinhos, enquanto o A* prioriza os nós mais próximos do destino
- Como usa uma métrica de distância fora do grafo, ele se enquadra em busca informada
- Algoritmos recursivos tendem a se parecer mais com busca em profundidade (DFS), e loops que exploram sem ordenar candidatos ou vizinhos se aproximam de BFS
- Muitas vezes, trocar código existente em estilo BFS ou DFS por A* traz grandes ganhos de desempenho
- No autorouter, são usados vários níveis de A* para encontrar os hiperparâmetros adequados ao problema
- Cada configuração do autorouter é executada como candidata
- Configurações que começam a ter sucesso no roteamento com bom custo recebem mais iterações
- É uma forma de meta-A* que usa tanto custo de distância quanto custo de iteração como penalidade
O algoritmo importa mais do que a linguagem
- O autorouter do tscircuit está sendo escrito em JavaScript, e em discussões sobre desempenho muitas vezes a linguagem é o primeiro ponto levantado
- A otimização algorítmica se divide, em grande parte, em dois eixos
- Reduzir a quantidade de iterações necessárias, tornando o algoritmo mais inteligente
- Aumentar a velocidade de execução de cada iteração
- Focar demais em acelerar uma única iteração pode acabar apenas executando mais rápido uma abordagem errada
- Por exemplo, transformar tudo em grade para verificar sobreposições pode ficar lento independentemente da linguagem
- Um algoritmo inteligente em JavaScript pode ser mais rápido do que um algoritmo simples em assembly de baixo nível, mesmo altamente otimizado
- Vale mais a pena gastar 95% do tempo de desenvolvimento reduzindo o número de iterações, e uma boa escolha de linguagem é aquela que ajuda a chegar rapidamente ao algoritmo mais inteligente e com melhor potencial de cache
Spatial Hash Index pode ser melhor do que árvores
- Em otimização espacial multidimensional, QuadTree aparece com frequência, mas estruturas de árvore genéricas podem ser lentas
- O QuadTree é conhecido como uma estrutura que reduz buscas por objetos próximos em espaços 2D ou 3D de
O(N)paraO(log(N)), mas árvores não são uma representação informada dos dados - Um Spatial Hash Index não faz hash do objeto em si, mas da sua posição, armazenando-o em células ou buckets de elementos próximos
- Essa abordagem aplica acesso rápido baseado em hash, como em HashSet e HashMap, a dados espaciais
- A razão de hashes espaciais serem menos populares é a necessidade de escolher um tamanho de célula adequado
- Se o tamanho da célula for calibrado de forma errada, cada consulta pode ter um custo fixo alto
- Na prática, considera-se que escolher um tamanho de célula razoável não é tão difícil assim
Particionamento espacial e cache mudam o desempenho
- Placas de circuito como o interior de um iPhone podem ter algo entre 10.000 e 20.000 trilhas, e mesmo com ferramentas EDA de ponta uma equipe pode passar meses roteando
- Uma ideia simples e importante no problema de autorouting é que aquilo que já foi roteado provavelmente já foi roteado antes
- Desenvolvedores de jogos pré-processam navigation meshes, e LLMs comprimem a internet em pesos para fins de recuperação
- A próxima geração de autorouters pode dividir o problema espacialmente e aproveitar grandes caches contendo soluções já resolvidas
- Se 99% dos problemas de autorouting já estiverem resolvidos em cache, a velocidade do algoritmo em si se torna menos importante
- Muitos algoritmos atuais ainda não dão atenção suficiente à reutilização de cache e ao particionamento espacial
- O custo de armazenamento e cache parece cair mais rápido do que o ganho de velocidade computacional aumenta, então usar 1 GB de cache para deixar o autorouter 50% mais rápido não parece um grande problema
Visualização e profiling para enxergar o problema diretamente
- É importante seguir o princípio de que, sem visualização do problema, não dá para resolvê-lo
- Olhar apenas para números dificulta a depuração, e criar visualizações para pequenos subproblemas ajuda a entender muito mais rápido o que está acontecendo
- No desenvolvimento do autorouter, muitas vezes a solução de problemas começa justamente pela visualização
- Até o subalgoritmo de encontrar caminhos em 45 graus foi visualizado, e ele é usado na Path Simplification Phase, quase a etapa final do autorouter
- Ferramentas de profiling de JavaScript mostram, em milissegundos, o tempo total consumido em cada linha de código
- Basta executar JavaScript no navegador e abrir a aba Performance
- Também há recursos de flame chart e uso de memória
- Vídeo curto relacionado: youtube short
Evitar recursão e Monte Carlo
- Funções recursivas costumam ser melhor evitadas em código orientado a desempenho
- Quase sempre operam de forma síncrona, dificultando interromper no meio para animação
- São essencialmente DFS e não são fáceis de converter para A*
- Não é simples acompanhar a contagem de iterações
- Em funções recursivas, mutabilidade é algo menos natural, mas ela pode ser importante para desempenho
- Implementações iterativas podem ser mais rápidas porque mantêm um conjunto
visitedNodese permitem verificar nós antes da exploração - Algoritmos Monte Carlo se aproximam da solução com aleatoriedade, mas por não serem determinísticos são difíceis de depurar e raramente são considerados melhores do que heurísticas
- Quando se sabe como avaliar candidatos, mas não como chegar à solução, abordagens Monte Carlo podem ajudar a ganhar intuição
- Assim que existe algo próximo de uma função de custo, é melhor usar métodos superiores a técnicas aleatórias como Monte Carlo ou Simulated Annealing
- Se houver sensibilidade a mínimos locais, pode valer a pena considerar hiperparâmetros ou funções de custo mais complexas
- Assim como um projetista de PCB não desenha linhas aleatórias sobre a placa, a ideia é que neste domínio é possível encontrar heurísticas melhores
Manter os algoritmos intermediários no mesmo sistema de coordenadas
- O autorouter atualmente é um pipeline com 13 etapas e cerca de 20 subalgoritmos
- Mede-se o número de iterações em tarefas como decisões de particionamento espacial ou simplificação de caminhos nas fronteiras de regiões roteadas de forma independente
- Visualizar sobrepostos a entrada e a saída de cada etapa ajuda a entender o contexto do problema que está sendo resolvido naquele momento
- Problemas em etapas downstream, especialmente na etapa de high density routing, muitas vezes podem ser resolvidos melhorando a saída das etapas anteriores
- Ao criar subalgoritmos, existe a tentação de isolar o problema na forma mais simples possível e normalizar coordenadas ao redor de
(0, 0) - Normalizações ou transformações complexas podem dificultar enxergar rapidamente como o resultado das etapas iniciais afeta as etapas posteriores
- É vantajoso manter o espaço de coordenadas consistente ao longo de todo o ciclo de vida do algoritmo
- Observar cada etapa em sequência e dar zoom ajuda a encontrar qual etapa causou uma Design Rule Check com falha
Animação das iterações e evitar grades
- Como reduzir o número de iterações é importante, ver as iterações do algoritmo em animação ajuda a perceber intuitivamente buscas desperdiçadas
- A animação é especialmente útil ao ajustar o Greedy Multiplier
- Houve casos em que uma trilha simples, que deveria falhar imediatamente, em vez disso continuava tentando resolver infinitamente para fora; sem animação isso teria sido difícil de perceber
- Há duas formas principais de determinar se duas trilhas A e B se sobrepõem
- Verificar cada segmento de A e B e confirmar se há interseção
- Marcar a grade em que B existe e depois verificar se B está presente nas células da grade por onde A passa
- A abordagem por grade pode facilmente ser 1000 vezes mais lenta
- Com matemática vetorial rápida, um dot product para determinar a interseção entre dois segmentos pode ser mais rápido do que o acesso à memória para verificar uma única célula de grade
- Em termos rigorosos, para garantir a folga adequada, deve-se calcular a distância entre segmentos; isso é um pouco mais complexo do que interseção, mas não muito diferente
Probabilidade de falha e Weighted A*
- Na etapa de particionamento espacial, é possível medir a probabilidade de falha de resolução de cada etapa como indicador antecedente
- O Unravel Autorouter acompanha a probabilidade de falha de cada Capacity Node em cada etapa principal do pipeline
- Cada etapa se concentra em reduzir a probabilidade de falha por meio de reconfiguração de nós adjacentes ou rerroteamento
- A probabilidade de falha pode ser medida de fato, e as previsões também podem melhorar à medida que o algoritmo muda
- Cada etapa pode agir para diminuir a chance de falha das etapas seguintes
- Em vez de impor restrições demais de uma vez, é melhor priorizar a possibilidade de solução
- Depois que a placa é resolvida, em muitos casos fica mais fácil trabalhar sobre uma solução existente do que gerar a solução ótima desde o início
Compromisso entre velocidade e otimalidade com Greedy Multiplier
- O A* padrão garante a solução ótima, mas se a prioridade for mais velocidade, é possível alterar um pouco
f(n)e usar Weighted A* - A* comum:
f(n) = g(n) + h(n) - Weighted A*:
f(n) = g(n) + w * h(n) - O Weighted A* resolve o problema de forma mais gulosa e em geral roda muito mais rápido
- Essa abordagem funciona como um Greedy Multiplier que aumenta bastante o desempenho do A* em troca de abrir mão de parte da otimalidade
- É possível ver mais sobre Weighted A* e outras variantes de A* em weighted A* and other A* variants here
- Desenvolvedores de jogos lidam com muitos problemas parecidos com os de quem desenvolve autorouting, então vale consultar artigos da área de games ao procurar pesquisas relacionadas
Autorouter que será lançado em breve
- O autorouter para tscircuit está se aproximando do lançamento
- O trabalho será disponibilizado como open source sob licença MIT
- Resolver autorouting pode abrir grandes possibilidades de inovação no mundo físico e seria uma peça central para tornar possível o “vibe-building” de eletrônicos
- Conta relacionada: follow me on twitter.
1 comentários
Opiniões do Hacker News
Em geral, fico do lado de quem não confia em autorouters, e o mesmo vale para as ferramentas de IA que estão entrando nessa área, mas é difícil negar que há uma grande oportunidade para criar rapidamente partes do layout em eCAD
Acho que eu usaria mais ferramentas de cocriação do que ferramentas totalmente automáticas. No início do projeto, muitas vezes o posicionamento dos componentes ainda não está definido, e o posicionamento tem grande impacto no roteamento. Não vi na página se o posicionamento está incluído no algoritmo. Já uso ferramentas como push-and-shove ou, às vezes, autocompletar
Esse mercado é pequeno, as ferramentas são fragmentadas, os fornecedores existentes são corporações gigantes e lentas, e os usuários são entusiastas exigentes. Não abro mão do KiCad de jeito nenhum. Não tenho uma opinião forte sobre o fato de o autorouter ter sido escrito em JavaScript, mas fico curioso se o plano é se integrar aos fornecedores de CAD ou ao ecossistema de ferramentas open source, ou se a ideia é puxar as pessoas para mais um novo ecossistema
Sendo amigável a cache, fica muito mais rápido mover componentes e testar outros layouts. JavaScript hoje tem até runtimes pequenos como QuickJS ou Proffor, então é bastante portátil, e acredito que seja possível executá-lo localmente e criar caches enormes diretamente
Lock-in e fragmentação de ecossistema em EDA são preocupações para todos, mas o tscircuit e este autorouter são tecnologias sob licença permissiva MIT, algo raro em EDA, e podem ser feitos para interoperar com todo mundo
Depois de fixar footprints, posicionamento, restrições e nets roteadas manualmente, dava para iterar muito rapidamente
Desde que a Cadence adquiriu o SPECCTRA nos anos 90, os autorouters de PCB ficaram bastante estagnados, então é bom ver alguém voltar a tratar dessa área. Pelo que lembro, as pessoas que criaram o SPECCTRA foram para o lado de VLSI e não voltaram; aparentemente, era lá que estavam a reputação e o dinheiro. Talvez tenha sido um campo minado de patentes por um tempo, e talvez ainda seja
Autoposicionamento já era um problema completamente intratável na época e ainda parece ser, mas uma abordagem com IA generativa pode se encaixar bem. Um bom primeiro posicionamento de componentes baseado em IA generativa pode reduzir o tempo total. O maior problema é convencer pessoas teimosas de que algo pode ser bom o suficiente mesmo sem ser perfeito
As tentativas de fazer esquemáticos como código me parecem um pouco curiosas. Espero que funcionem bem como formato de backend, e em especial o avanço de codificar regras de projeto no nível de application notes e datasheets em modelos de componentes, como no jitx, parece bom. Ler todos os datasheets no nível necessário para um projeto comercial dá muito mais trabalho do que parece, e fazer um engenheiro júnior aprender esse processo também; então automatizar isso é benéfico
Ainda assim, essas abordagens parecem estar enraizadas na ideia de ver o esquemático como entrada de dados para layout, uma espécie de código-fonte. O esquemático também é um documento de projeto, com uma linguagem visual cuidadosamente evoluída, que deve ser acessível mesmo a pessoas que não tenham uma suíte EDA instalada. Quem aprendeu decifrando esquemáticos no estilo Adafruit/Sparkfun/Shenzhen, com fiação explícita mínima, talvez não entenda bem o valor de um bom esquemático
Outra coisa é a tendência de se apoiar demais em analogias e tentar tornar o projeto em nível de PCB parecido com projeto VLSI. Não acho totalmente impossível. Com DRC e ferramentas de verificação melhores, o projeto em nível de componentes pode ficar mais próximo de VLSI. Mas o acoplamento entre projeto, EDA/CAM/simulação, verificação, fabricantes, montadores, fornecedores de componentes e órgãos reguladores/de certificação é frouxo demais; fazer bem apenas um canto disso já seria uma grande conquista
Hoje em dia, a tendência é fazer projetos UHF com controle de impedância junto com ferramentas de simulação específicas de domínio. Por isso, primeiro roteia-se manualmente os traços importantes, criam-se ilhas de cobre e, por fim, cuidam-se das conexões de alimentação
O layout do KiCad é um pouco melhor do que nada, mas tentar transformá-lo em mais uma ferramenta de simulação meia-boca parece ridículo
Suporte a banco de dados e recursos de outjob. Fora isso, é mais uma questão de adoção e de como os usuários aproveitam esses recursos, e bancos de dados normalmente trazem junto mais burocracia interna em torno da organização dos dados
Do ponto de vista de um fluxo de trabalho para acelerar o layout, acho que o KiCad já está indo um pouco nessa direção. Por exemplo, há o recurso de “autocompletar traços”, que entrou por volta da versão 7.0. No pcbnew, acho que era o atalho F; ele desenha o traço da trilha que está sendo posicionada no momento. Usado junto com o atalho E, “rotear do outro lado da trilha”, a produtividade aumenta bastante ao trabalhar entre duas grades de breakout diferentes
Na versão 9, será possível arrastar barramentos ou várias trilhas, o que pode acelerar ainda mais esse fluxo
Sinceramente, se eu conseguir chegar a um posicionamento satisfatório e puder dar ao autorouter restrições sobre onde as trilhas devem passar, acho que uma boa parte do projeto poderia ser deixada para o autorouter. Por exemplo, no ano passado fiz uma placa usando um NXP iMX8MP e eMMC, e o breakout ao redor do processador combinava bem com o breakout da eMMC, então bastava alinhar os chips e traçar as linhas. Se ele soubesse apenas que devia manter o barramento de dados na camada superior, um autorouter teria feito em segundos algo que levou 10 minutos
Há um problema nos critérios de sucesso enfrentados por projetos de autorouter. Parece que eles só são considerados “prontos” se conseguem lidar com tudo na placa, mas, como engenheiro eletricista na prática, não é isso que eu quero. Quero um autorouter que trabalhe comigo em pequenos blocos do projeto, um de cada vez, me dê tempo para revisar e depois passe para o próximo bloco
Se também for possível definir restrições que atravessam camadas, isso é poderoso. Por exemplo: “mantenha todas as nets chamadas D0-7 nas camadas 1 e 3, iguale os comprimentos entre si dentro de 5 mm e use D0 como referência de comprimento”. Se conseguir fazer isso, você praticamente resolveu o ajuste de comprimento de DRAM, e projetos de complexidade muito maior ficam viáveis também para usuários comuns
Se eu tiver tempo, gostaria de mostrar em uma demo o que quero dizer
No item 8, foi um grande erro descartar o método de Monte Carlo rápido demais
O ponto central de Monte Carlo é que dá para trocar precisão por velocidade. Quanto mais tempo o algoritmo roda, mais preciso fica
O mais interessante é que o contrapositivo também pode ser usado com frequência. Dá para obter um resultado muito impreciso muito rapidamente. Em vez de explorar todos os caminhos, explora-se apenas um caminho escolhido aleatoriamente
Essa abordagem brilha quando colocada no laço aninhado mais interno do algoritmo. Por exemplo, para treinar uma rede neural que aprende roteamento automático, o laço externo atualiza os parâmetros da rede neural, e o laço interno calcula um caminho através do grafo
Com Monte Carlo, se não houver viés, dá para reduzir esse laço interno que controla a precisão a uma única iteração. A variância aumentaria e o laço externo ficaria mais lento, mas o aprendizado de máquina poderia aprender “em teoria”
Assim, como no xadrez ou no Go, dá para criar uma política que escolha decisões intuitivamente corretas. Em variantes de busca em árvore de Monte Carlo como AlphaGo Zero, AlphaChess Zero e AlphaRouter Zero, mesmo sem a parte de busca, um cache enorme codificado nos parâmetros da rede neural pode, depois do treinamento, calcular o melhor caminho estimado com uma única passagem pela rede neural, ou seja, em tempo constante. Essa constante pode ser facilmente trocada por memória e velocidade aumentando os parâmetros ou treinando por mais tempo
MC é um algoritmo que ajuda a manter um senso de realidade. É lento, mas quase sempre é muito simples de implementar, e é confiável para reconfirmar, com altíssima confiança, que você não saiu para um lugar completamente absurdo
É uma ótima discussão sobre roteamento automático, mas doeu um pouco terminar com “a peça central que possibilita o vibe-building de eletrônicos”
O roteamento em si é fácil. Fica complicado no momento em que é preciso arrancar algo já roteado para inserir uma nova trilha, e aí vem a explosão combinatória
Sinto falta do autorouter que existia antes no KiCad. Ele foi removido por motivos ambíguos de propriedade intelectual, porque o autor havia trabalhado em uma empresa de roteamento automático. Aos usuários que pediam para recolocá-lo, havia respostas do tipo “homens de verdade não usam autorouter”
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
Espero que este autorouter e as outras ferramentas que vierem depois permitam que as pessoas lancem seu primeiro produto eletrônico sem muitos mapas ou educação formal
Claro, um bom autorouter também deve ser útil para especialistas, então espero que ajude nesse aspecto também
Mas, como uma dessas pessoas antigas e exigentes que não querem muito ver o KiCad gastando energia com autorouters, autorouters de PCB sempre são uma dor de cabeça e não funcionam direito
Dá para entender o porquê olhando para autorouters de VLSI. Autorouters de VLSI também eram uma dor de cabeça e não funcionavam direito. Então o VLSI passou a ter muitas camadas, e tornou-se possível alocar camadas separadas para roteamento vertical, para roteamento horizontal e para alimentação, e ainda ter mais algumas camadas para conexões verticais globais, conexões horizontais globais e alimentação global
O problema fundamental do autorouting de PCBs é que uma PCB tem muito mais obstáculos do que um chip VLSI. Primeiro, os próprios componentes são obstáculos e gargalos. Segundo, as vias de PCB quase sempre bloqueiam todas as camadas da placa, enquanto as vias de VLSI bloqueiam apenas as duas camadas que conectam. Terceiro, as vias de PCB geralmente são maiores que a largura do metal das trilhas. Quarto, o número de camadas usado em PCBs é muito menor do que em VLSI. O comum são 4 camadas, das quais só 2 são realmente usadas para roteamento geral; por custo, também há muitas placas de 2 camadas, que são ainda mais difíceis de autorrotear, e placas de 6 camadas são uma minoria bem pequena
Como resultado, o autorouting de PCBs é uma tarefa muito mais complexa do que o autorouting de VLSI
Gostei do fato de o texto tratar visualização e efeitos de cache como especialmente importantes.
Mas alguns pontos me incomodam. A afirmação de que “algoritmos recursivos são busca em profundidade, e loops que exploram candidatos ou vizinhos sem ordená-los são busca em largura” parece errada ou deixa passar a intuição. Tanto DFS quanto BFS podem ser escritos com laços ou recursão; a diferença real é se o próximo candidato é retirado do topo ou da base da pilha, ou seja, se você usa uma pilha (FILO) ou uma fila (FIFO).
A afirmação de que A* é a melhor base para toda busca baseada em informação também precisa de contexto. Ele é útil para busca de caminhos quando há um conceito de “distância” até o objetivo que seja fácil de calcular e quando você vai executar apenas algumas consultas no mesmo grafo. Se você planeja rodar muitas consultas em um grafo quase estático, como uma malha viária, algoritmos de pré-processamento como contraction hierarchy podem ser melhores. Se você está otimizando algo sem um objetivo fixo, como no problema do caixeiro-viajante, outras heurísticas de busca local, como 2-opt, podem ser melhores.
“BFS explora todos os nós adjacentes, enquanto A* prioriza nós próximos do destino” é uma diferença, mas a diferença maior é que A* é um algoritmo dinâmico. Por isso, ele pode encerrar cedo, com confiança de que encontrou o caminho mais curto. BFS talvez não consiga ter certeza até explorar o grafo inteiro, e o grafo pode ser enorme.
Na maioria das linguagens, isso é mais fácil de expressar do que pensar trazendo uma pilha externa. Então, ao ver recursão em código real, é bem provável que ela esteja mais próxima de DFS, mas isso não é uma regra estrita.
BFS usa uma fila FIFO, DFS usa uma pilha LIFO, e A* normalmente usa uma fila de prioridade implementada com heap.
Essa é uma das invariantes básicas que fazem BFS produzir o resultado correto, então é possível encerrar cedo quando todos os objetivos forem alcançados.
A diferença entre A* e BFS é que BFS encontra os caminhos mais curtos de um único ponto inicial para todos os pontos do grafo, não apenas o caminho mais curto entre dois pontos. A* é um compromisso que acelera consultas individuais em troca de responder a uma pergunta mais fraca.
Se a estrutura do problema permitir, só trocar milhares de chamadas de A* por uma única chamada de BFS ou Dijkstra já pode trazer um grande ganho de velocidade. Outra diferença importante é que BFS só funciona em grafos em que todas as arestas têm o mesmo comprimento, enquanto A* suporta comprimentos de aresta diferentes. Os dois não são intercambiáveis, assim como encontrar o menor elemento de uma lista não substitui ordenar a lista.
Dizer que “quadtrees e todas as estruturas de árvore genéricas são absurdamente lentas”, que “árvores não são uma representação com informação sobre os dados” e que “toda vez que você usa uma árvore, está usando um algoritmo O(log N) mais complexo em vez de um algoritmo de hash O(~1)” vai bastante na direção errada.
Uma abordagem com hashing funciona bem quando os pontos estão distribuídos de forma uniforme e você consulta apenas regiões próximas da partição fixa escolhida. Caso contrário, esse O(1) pode desmoronar para O(n).
Quando você não conhece a distribuição dos dados, uma árvore é uma representação com informação.
Algoritmos aleatórios são parecidos. O que fazer quando o espaço de busca é composto por trilhões ou mais de itens ou possibilidades? E se não houver heurística? Em uma situação em que força bruta não serve e algoritmos inteligentes também não são aplicáveis, algoritmos aleatórios viram uma salvação.
Pode não ser necessário nesta aplicação específica, mas é melhor evitar afirmações generalizadas.
Falando mais seriamente, algoritmos baseados em árvores tendem a ser superestimados, e acho que as pessoas se prendem demais ao comportamento em notação Big O e esquecem que fatores constantes importam muito mesmo com centenas de milhares de elementos. O mesmo vale para localidade de dados. Às vezes, simplesmente varrer tudo com um scan sequencial é mais rápido do que fazer a contabilidade de uma estrutura mais complexa.
No geral, é melhor encapsular as operações em pequenos wrappers, começar com uma implementação fácil e decidir com base em medições.
No pior caso, você precisará reescrever o programa inteiro em torno de outra estrutura para buscar melhor desempenho, mas, pela minha experiência, reescrever um arquivo do zero costuma trazer também algumas melhorias “de graça”.
Ainda não encontrei uma forma satisfatória de armazenar pontos 2D ou 3D e consultar pontos próximos. kD-trees são bons, mas eu quero ir adicionando pontos conforme avanço, não construir a estrutura sobre um conjunto fixo.
Quase tudo bate com minhas heurísticas de desenvolvimento de jogos. Também entendo a escolha por JavaScript.
Estou criando agora um framework de modding de jogos que funciona com expressões S no estilo Lisp, e percebi que otimizações que reduzem o tempo de iteração criativa são mais importantes do que qualquer coisa.
Coisas como A* e o algoritmo de Lee são todas legais. Não criar uma visualização junto com qualquer tipo de flood fill chega perto de ser um crime. É desperdício demais de dopamina.
Lendo este texto, fiquei curioso se técnicas que não li, mas que ficam perto de desenvolvimento de jogos, também seriam úteis para esse problema. Não devo ser a primeira pessoa a achar que um roteador de boids seria bem divertido. Mais seriamente, acho que campos de distância com sinal baseados em jump flooding poderiam dar bastante força.
Em especial, o trecho sobre hashing espacial bate com minha experiência. Em quase 20 anos, vi poucos casos em que estruturas de árvore valeram o tempo investido. Há uma exceção: um editor de texto lovecraftiano que criei usa bastante tries para processamento reativo. Foi uma boa forma de transformar 45.000 palavras em uma máquina de estados compactada para tratamento de eventos.
Já escrevi antes sobre um autorroteador de padrões recursivos, e como o espaço de soluções é pequeno, ele é relativamente fácil de prever com algoritmos tradicionais de machine learning. Ainda há muitas áreas interessantes e pouco exploradas em autorroteamento.
Eu não conhecia jump flooding. Para quem mais estiver lendo: é um algoritmo para aproximar rapidamente, em paralelo, campos de distância. Com certeza pode ser interessante, e obrigado por avisar.
Árvores também combinam bem com algoritmos recursivos, e o autor disse que há motivos para preferir algoritmos iterativos aos recursivos, então esses conselhos se encaixam.
De forma mais ampla, a distinção entre “recursivo” e “não recursivo” é meio artificial. A verdadeira pergunta é: “um algoritmo pré-estruturado, com regras rígidas, controla o fluxo, ou eu controlo?”. Se você se importa muito com desempenho, a resposta deve ser que você controla; quando o estado de execução é abstraído para dentro da pilha fornecida pelo ambiente de execução, ficando difícil alterá-lo de maneiras estranhas em runtime, isso começa a atrapalhar.
A frase “95% do foco deve ser gasto em reduzir o número de iterações, portanto a linguagem não importa” é correta até certo ponto, mas se, depois de criar algoritmos excelentes e performáticos em uma linguagem interpretada/abstrata/lenta, lúdica e expressiva, desempenho ainda importar, basta reescrever a mesma coisa em uma linguagem de baixo nível performática e, se necessário, escrever até assembly específico por arquitetura.
Há um motivo para numpy, pandas, OpenCV, TensorFlow não serem escritos em Python puro. O papel do Python é comandar operações implementadas em C++/assembly/CUDA etc. de alto desempenho.
Por mais orgulho que alguém tenha de ter explorado o espaço do problema, encontrado algoritmos eficientes e escrito sobre isso em um blog, se tivesse insistido em escrever tudo apenas em Python puro ou JavaScript, dificilmente teria virado uma biblioteca popular de computação numérica.
O texto é interessante, mas se, com os insights algorítmicos do autor, um encoder HEVC em JavaScript puro tivesse passado de 1 dia por frame para 3 horas, acho que seria difícil chegar à mesma conclusão.
Vejo um monte de palavras-chave de que me lembrava da faculdade. Seria bom ter ocasiões para usar algoritmos famosos e legais.
Na prática, só fico criando componentes de UI e APIs REST para exibir resultados do Elasticsearch. As coisas interessantes estão todas enterradas dentro de caixas-pretas.
Em desenvolvimento de jogos há muitos algoritmos inevitáveis; então, se você quer criar algoritmos, tente fazer algo como um tower defense, e vai acabar lidando com muitos algoritmos clássicos.
No mínimo, acho que o atual diploma de ciência da computação deveria ser dividido. A parte da matemática elegante deveria virar um diploma separado, talvez combinado com um novo diploma relacionado a IA. Teoria de bancos de dados e redes também deveria ser um diploma separado, assim como assembly de baixo nível. Como componentes eletrônicos, portas NAND, álgebra booleana etc. funcionam deveria ir para engenharia elétrica.
As pessoas de que o mercado mais precisa, capazes de produzir apps CRUD em escala, se insistirem que conhecimento acadêmico é necessário, deveriam ter um diploma separado ou serem movidas para educação profissionalizante.
Ao mesmo tempo, o papel de porteiro dos requisitos de contratação também deveria ser tratado por lei. Não deveria ser permitido exigir diplomas quase sem relação com o trabalho real. Hoje isso faz jovens desperdiçarem anos de vida e assumirem dívidas de cinco a seis dígitos em dólares, só para facilitar às empresas filtrar pessoas.
Embora eu não lide diretamente com problemas espaciais 2D/3D, a maior lição é o valor da visualização.
Humanos são muito bons em entender e analisar imagens. Outra lição é a ideia de primeiro entender o formato do problema com métodos probabilísticos ou força bruta e, depois, escolher um método melhor com base nisso, não apenas em uma compreensão puramente teórica.
A frase “a linguagem de implementação não importa” talvez esteja correta nesta área, mas, aplicada à engenharia de software em geral, acho muito errada a suposição de que a escolha da linguagem não afeta a velocidade e o número de iterações necessárias.
Se você está na etapa de controlar termos exponenciais ou polinomiais, a diferença entre Rust ou assembly hardcoded e JavaScript ou VisualBasic pode se tornar bastante irrelevante.