- Environ un an de développement d’un autorouter PCB open source pour tscircuit a montré que des conceptions qui réduisent le problème de recherche, comme A*, la visualisation, la partition spatiale et le caching, sont au cœur des performances
- L’optimisation doit se concentrer sur la réduction du nombre d’itérations plutôt que sur le langage ou la vitesse d’une seule itération ; même en JavaScript, un algorithme plus intelligent et cacheable peut être plus rapide qu’une implémentation bas niveau
- Pour la recherche spatiale, un Spatial Hash Index peut être plus simple et plus rapide qu’un arbre générique comme un QuadTree, mais un mauvais choix de taille de cellule peut entraîner un coût fixe élevé à chaque requête
- Un pipeline d’autorouting complexe doit visualiser les entrées et sorties de chaque étape et vérifier le processus itératif via des animations ; les fonctions récursives et les approches Monte Carlo sont défavorables pour le débogage, l’optimisation et le déterminisme
- Avec Weighted A*, on peut sacrifier une partie de l’optimalité via un Greedy Multiplier pour obtenir un gain de vitesse important ; chaque étape doit réduire la probabilité d’échec afin de laisser aux étapes suivantes un problème plus facile à résoudre
Faire de A* l’outil de recherche par défaut
- A* n’est pas un algorithme réservé aux grilles 2D ; c’est un algorithme de base utilisable pour diverses formes de recherche informée (informed search)
- BFS explore tous les nœuds adjacents, tandis que A* explore d’abord les nœuds les plus proches de la destination
- Il utilise une métrique de distance extérieure au graphe ; c’est donc bien une recherche informée
- Les algorithmes récursifs ressemblent davantage à une recherche en profondeur (DFS), et les boucles qui explorent sans trier les candidats ou les voisins se rapprochent d’un BFS
- Remplacer un code existant de type BFS ou DFS par A* apporte souvent un gain de performance important
- Dans un autorouter, on utilise plusieurs niveaux de A* pour trouver les hyperparamètres adaptés au problème
- Chaque configuration de l’autorouter est exécutée comme un candidat
- Les configurations qui commencent à réussir le routage avec un bon coût se voient attribuer davantage d’itérations
- Cela revient à une forme de méta-A* où le coût de distance et le coût d’itération servent ensemble de pénalité
L’algorithme compte plus que le langage
- L’autorouter de tscircuit est écrit en JavaScript, et dans les discussions sur les performances, le langage est souvent le premier point mis en cause
- L’optimisation algorithmique se divise en gros en deux axes
- Réduire le nombre d’itérations nécessaires pour rendre l’algorithme plus intelligent
- Augmenter la vitesse d’exécution de chaque itération
- Se concentrer excessivement sur la vitesse d’une seule itération revient souvent à exécuter plus vite une mauvaise approche
- Par exemple, transformer tout en grille pour faire des tests de recouvrement peut être lent, quel que soit le langage
- Un algorithme intelligent en JavaScript peut être plus rapide qu’un algorithme simple optimisé en assembleur bas niveau
- Il vaut mieux consacrer 95 % du temps de développement à réduire le nombre d’itérations, et choisir un langage qui permet d’arriver vite à l’algorithme le plus intelligent et le plus facilement cacheable
Un Spatial Hash Index peut être préférable à un arbre
- Dans l’optimisation spatiale multidimensionnelle, le QuadTree revient souvent, mais les structures d’arbres génériques peuvent être lentes
- Le QuadTree est connu comme une structure de données qui réduit les recherches d’objets proches en espace 2D ou 3D de
O(N)àO(log(N)), mais un arbre n’est pas une représentation informée des données - Un Spatial Hash Index ne hache pas l’objet lui-même, mais sa position pour le stocker dans des cellules ou des buckets d’objets proches
- Cette approche applique aux données spatiales un accès rapide basé sur le hachage, dans l’esprit de HashSet ou HashMap
- Si le hash spatial est moins populaire, c’est parce qu’il faut choisir une taille de cellule appropriée
- Si la taille est mal ajustée, chaque requête peut entraîner un coût fixe élevé
- En pratique, choisir une taille de cellule raisonnable n’est pas si difficile
La partition spatiale et le caching changent les performances
- Une carte électronique comme l’intérieur d’un iPhone peut contenir environ 10 000 à 20 000 traces, et même avec les meilleurs outils EDA, une équipe peut passer plusieurs mois à la router
- Dans un problème d’autorouting, une idée simple mais importante est que ce qui a déjà été routé l’a souvent déjà été auparavant
- Les développeurs de jeux précuisent les navigation meshes, et les LLM compressent Internet dans leurs poids pour la recherche
- La prochaine génération d’autorouters pourra découper le problème spatialement et exploiter de grands caches contenant des solutions déjà résolues
- Si 99 % du problème d’autorouting est déjà résolu dans le cache, la vitesse brute de l’algorithme devient moins importante
- Beaucoup d’algorithmes actuels ne mettent pas assez l’accent sur la réutilisabilité du cache et la partition spatiale
- Le coût du stockage et du caching semble baisser plus vite que les gains de vitesse de calcul n’augmentent ; utiliser 1 Go de cache pour rendre un autorouter 50 % plus rapide ne semble pas être un gros problème
Voir directement le problème grâce à la visualisation et au profiling
- Le principe selon lequel on ne peut pas résoudre un problème sans visualisation est important
- Déboguer en ne regardant que des chiffres est difficile ; créer une visualisation pour chaque petit sous-problème permet de comprendre beaucoup plus vite
- Dans le développement d’un autorouter, il arrive souvent que la résolution d’un problème commence par sa visualisation
- Même le sous-algorithme de recherche de chemins à 45 degrés a été visualisé ; il est utilisé dans la phase de simplification de chemin, presque à la toute fin de l’autorouter
- Les outils de profiling JavaScript montrent le temps total consommé sur chaque ligne de code, en millisecondes
- Il suffit d’exécuter le JavaScript dans le navigateur et d’ouvrir l’onglet Performance
- On y trouve aussi un flame chart et des fonctions de suivi de l’usage mémoire
- Courte vidéo associée : youtube short
Éviter la récursion et Monte Carlo
- Mieux vaut éviter les fonctions récursives dans du code orienté performance
- Elles fonctionnent presque toujours de manière synchrone, ce qui rend difficile l’interruption en cours d’exécution pour une animation
- Par nature, elles relèvent du DFS et se convertissent difficilement en A*
- Il n’est pas facile d’y suivre le nombre d’itérations
- La mutabilité y est peu naturelle, alors qu’elle peut être importante pour les performances
- Une implémentation itérative peut être plus rapide, car elle maintient un ensemble
visitedNodeset permet de vérifier les nœuds avant l’exploration - Les algorithmes Monte Carlo approchent la solution via l’aléatoire, mais comme ils ne sont pas déterministes, ils sont difficiles à déboguer et rarement optimaux face à de bonnes heuristiques
- Quand on sait évaluer les candidats sans savoir comment atteindre la solution, une approche Monte Carlo peut aider à acquérir de l’intuition
- Dès qu’on dispose de quelque chose de proche d’une fonction de coût, il vaut mieux utiliser une méthode supérieure aux techniques aléatoires comme Monte Carlo ou Simulated Annealing
- Si l’on est sensible aux minima locaux, on peut envisager des hyperparamètres ou une fonction de coût plus complexe
- De même qu’un concepteur PCB ne trace pas des lignes au hasard sur une carte, on peut trouver dans ce domaine de meilleures heuristiques
Garder les algorithmes intermédiaires dans le même système de coordonnées
- L’autorouter est actuellement un pipeline composé de 13 étapes et d’environ 20 sous-algorithmes
- On mesure le nombre d’itérations dans des tâches comme les décisions de partition spatiale ou la simplification de chemin aux frontières de zones autoroutées indépendamment
- Visualiser en superposition les entrées et les sorties de chaque étape aide à comprendre le contexte du problème en cours de résolution
- Les problèmes des étapes downstream, en particulier la phase de high density routing, se résolvent souvent en améliorant la sortie des étapes précédentes
- Lorsqu’on crée un sous-algorithme, il est tentant d’isoler le problème sous sa forme la plus simple et de normaliser les coordonnées autour de
(0, 0) - Mais la normalisation ou les transformations complexes peuvent rendre plus difficile l’observation rapide de l’effet des premiers résultats sur les étapes suivantes
- Il est avantageux de conserver un espace de coordonnées cohérent pendant tout le cycle de vie de l’algorithme
- Examiner chaque étape dans l’ordre, puis zoomer, aide à identifier celle qui provoque un Design Rule Check en échec
Animer les itérations et éviter les grilles
- Comme il est crucial de réduire le nombre d’itérations, animer les itérations d’un algorithme permet de repérer intuitivement les explorations gaspillées
- L’animation est particulièrement utile pour ajuster le Greedy Multiplier
- Un cas où une trace simple, qui aurait dû échouer immédiatement, continuait à tenter indéfiniment une résolution vers l’extérieur aurait été difficile à repérer sans animation
- Il existe deux grandes façons de déterminer si deux traces A et B se chevauchent
- Examiner chaque segment de A et de B pour vérifier s’ils se croisent
- Marquer la grille occupée par B, puis vérifier si B est présent dans les cellules traversées par A
- L’approche par grille peut facilement être 1000 fois plus lente
- Avec des maths vectorielles rapides, le produit scalaire nécessaire pour décider si deux segments se croisent peut être plus rapide qu’un accès mémoire pour vérifier une seule case de grille
- Strictement parlant, il faut utiliser un calcul de distance entre segments pour garantir une marge appropriée ; c’est un peu plus complexe qu’un simple test d’intersection, mais pas fondamentalement différent
Probabilité d’échec et Weighted A*
- Dans les étapes de partition spatiale, on peut mesurer la probabilité d’échec de résolution de chaque étape comme indicateur avancé
- Unravel Autorouter suit cette probabilité d’échec pour chaque Capacity Node à chaque grande étape du pipeline
- Chaque étape se concentre sur la réduction de cette probabilité via la reconfiguration des nœuds adjacents ou le reroutage
- La probabilité d’échec peut réellement être mesurée, et les prédictions peuvent être améliorées à mesure que l’algorithme évolue
- Chaque étape peut ainsi agir de manière à réduire la probabilité d’échec des étapes suivantes
- Mieux vaut privilégier la résolvabilité plutôt que d’imposer trop de contraintes d’un coup
- Une fois la carte résolue, il est souvent plus facile de travailler à partir d’une solution existante que de générer d’emblée une solution optimale
Compromis entre vitesse et optimalité avec le Greedy Multiplier
- A* classique garantit une solution optimale, mais si la vitesse compte davantage, on peut modifier légèrement
f(n)et utiliser Weighted A* - A* classique :
f(n) = g(n) + h(n) - Weighted A* :
f(n) = g(n) + w * h(n) - Weighted A* résout le problème de manière plus gloutonne et fonctionne généralement bien plus vite
- Cette méthode joue le rôle de Greedy Multiplier, en échangeant une partie de l’optimalité contre un fort gain de performance pour A*
- Pour en savoir plus sur Weighted A* et d’autres variantes de A*, voir weighted A* and other A* variants here
- Les développeurs de jeux rencontrent beaucoup de problèmes similaires à ceux des développeurs d’autorouters ; pour trouver des recherches pertinentes, on peut consulter les publications du game development
Un autorouter bientôt disponible
- L’autorouter pour tscircuit approche de sa sortie
- Le travail sera proposé en open source sous licence MIT
- Résoudre l’autorouting pourrait ouvrir d’importantes innovations dans le monde physique et constituer une pièce essentielle pour rendre possible le “vibe-building” des produits électroniques
- Compte associé : follow me on twitter.
1 commentaires
Avis sur Hacker News
En général, je ne fais pas confiance aux autorouteurs, et c’est pareil pour les outils d’IA qui arrivent dans ce domaine, mais il est difficile de nier qu’il existe une grosse opportunité pour créer rapidement une partie du layout en eCAD
Je pense que j’utiliserais plutôt des outils de co-création que des outils entièrement automatiques. Au début d’une conception, le placement des composants n’est souvent pas figé, et le placement a une grande influence sur le routage. Je n’ai pas vu sur la page si le placement est inclus dans l’algorithme. J’utilise déjà des outils comme le push-and-shove, ou parfois l’autocomplétion
Ce marché est petit, les outils sont fragmentés, les acteurs historiques sont de grosses entreprises peu agiles, et les utilisateurs sont des passionnés exigeants. Impossible pour moi de lâcher KiCad, même mort. Je n’ai pas d’avis très tranché sur le fait que l’autorouteur soit écrit en JavaScript, mais je me demande s’il est prévu de s’intégrer aux éditeurs de CAD ou à l’écosystème des outils open source, ou s’il s’agit encore d’un nouvel écosystème vers lequel attirer les gens
Si c’est cache-friendly, déplacer des composants et essayer d’autres layouts devient beaucoup plus rapide. JavaScript est désormais assez portable, avec même de petits runtimes comme QuickJS ou Proffor, et je pense qu’on peut l’exécuter en local tout en construisant directement de gros caches
Le lock-in et la fragmentation des écosystèmes en EDA devraient inquiéter tout le monde, mais tscircuit et cet autorouteur sont des technologies sous licence permissive MIT, ce qui est rare en EDA et permet de les rendre interopérables avec tout le monde
Une fois les footprints, le placement, les contraintes et les nets routés manuellement verrouillés, on pouvait itérer très vite
Depuis que Cadence a acquis SPECCTRA dans les années 90, les autorouteurs PCB ont pas mal stagné, donc c’est réjouissant de voir quelqu’un s’y remettre. Les créateurs de SPECCTRA sont, de mémoire, partis vers le VLSI et ne sont jamais revenus ; c’est là que se trouvaient la reconnaissance et l’argent, semble-t-il. Il y a peut-être eu un champ de mines de brevets pendant un moment, et c’est peut-être encore le cas
Le placement automatique était déjà un problème totalement difficile à maîtriser à l’époque, et il semble toujours l’être, mais une approche par IA générative pourrait bien convenir. Un bon premier placement de composants basé sur l’IA générative pourrait réduire le temps total. Le plus gros problème sera de convaincre les gens obstinés que, même sans être parfait, cela peut être assez bon
Les tentatives de faire des schémas sous forme de code me laissent un peu perplexe. Comme format backend, ce serait bien que cela fonctionne, et les progrès qui consistent à encoder dans les modèles de composants des règles de conception du niveau des notes d’application et des datasheets, en particulier du côté de jitx, semblent prometteurs. Lire toutes les datasheets au niveau requis pour une conception commerciale représente beaucoup plus de travail qu’on ne l’imagine, et faire acquérir ce processus à des ingénieurs juniors aussi ; l’automatisation est donc utile
Cela dit, ces approches semblent enracinées dans l’idée que le schéma est une entrée de données pour le layout, une sorte de code source. Un schéma est aussi un document de conception doté d’un langage visuel soigneusement élaboré, qui doit rester accessible aux personnes n’ayant pas installé toute une suite EDA. Ceux qui ont appris en déchiffrant des schémas au style Adafruit/Sparkfun/Shenzhen, où le câblage explicite est réduit au minimum, ne perçoivent peut-être pas la valeur d’un bon schéma
Autre point : il y a une tendance à trop s’appuyer sur l’analogie pour faire ressembler la conception au niveau PCB à la conception VLSI. Je ne pense pas que ce soit totalement impossible. Avec de meilleurs outils de DRC et de vérification, la conception au niveau des composants pourrait se rapprocher davantage du VLSI. Mais les liens entre conception, EDA/CAM/simulation, vérification, fabricants, assembleurs, fournisseurs de composants et organismes de réglementation/certification sont si lâches que réussir correctement ne serait-ce qu’un coin de tout cela serait déjà un gros résultat
Aujourd’hui, la tendance est de faire la conception UHF à impédance contrôlée avec des outils de simulation spécialisés par domaine. On route donc d’abord manuellement les pistes critiques, on crée des îlots de masse, puis on traite les connexions d’alimentation en dernier
Le layout KiCad est un peu mieux que rien, mais vouloir en faire un énième outil de simulation approximatif paraît ridicule
Il s’agit de la prise en charge des bases de données et de la fonction outjob. Pour le reste, c’est surtout une question d’adoption et de manière dont les utilisateurs exploitent ces fonctionnalités ; les bases de données s’accompagnent généralement de davantage de bureaucratie interne autour de l’organisation des données
Du point de vue d’un workflow qui accélère le layout, j’ai l’impression que KiCad va déjà en partie dans cette direction. Par exemple, il y a la fonction « autocomplétion de piste » arrivée vers la 7.0. Dans pcbnew, il me semble que c’était le raccourci F : elle pose la piste du track en cours de placement. Utilisée avec le raccourci E, « router depuis l’autre extrémité de la piste », elle augmente fortement la productivité quand on travaille entre deux grilles de breakout différentes
Dans la version 9, le fait de pouvoir faire glisser des bus ou plusieurs pistes peut encore accélérer ce flux
Honnêtement, si l’on peut arriver à un placement satisfaisant et donner à l’autorouteur des contraintes sur l’emplacement du routage, je pense qu’on peut lui confier une part importante de la conception. Par exemple, l’an dernier, j’ai fait une carte avec un NXP iMX8MP et de l’eMMC : le breakout autour du processeur correspondait bien au breakout de l’eMMC, donc il suffisait d’aligner les puces et de tracer les lignes. Si l’autorouteur avait simplement su qu’il fallait garder le bus de données sur la couche supérieure, il aurait fait en quelques secondes ce qui a pris 10 minutes
Les projets d’autorouteur ont un problème de critère de réussite. Ils semblent considérer qu’ils doivent pouvoir traiter tout ce qui se trouve sur la carte pour être « terminés », mais en tant qu’ingénieur électricien en pratique, ce n’est pas ce que je veux. Je veux un autorouteur qui traite avec moi de petits blocs de la conception, un par un, me laisse le temps de vérifier, puis passe au bloc suivant
Si l’on peut aussi fournir des contraintes traversant les couches, c’est puissant. Par exemple : « garde tous les nets nommés D0-7 sur les couches 1 et 3, aligne leurs longueurs à 5 mm près, et utilise D0 comme référence de longueur ». Si cela est possible, cela revient à résoudre le réglage des longueurs DRAM, et des conceptions d’une complexité bien plus grande deviennent accessibles aux utilisateurs ordinaires
Si j’ai le temps, j’aimerais faire une démo pour montrer ce que je veux dire
Au point 8, écarter trop vite la méthode de Monte-Carlo était une grosse erreur
L’intérêt de Monte-Carlo est qu’on peut échanger de la précision contre de la vitesse. Plus on laisse tourner l’algorithme longtemps, plus il devient précis
Ce qui est encore plus intéressant, c’est que la réciproque est souvent exploitable aussi. On peut obtenir très rapidement un résultat très imprécis. Par exemple en n’explorant qu’un seul chemin choisi au hasard au lieu de parcourir tous les chemins
Cette approche brille quand on la place dans la boucle imbriquée la plus interne de l’algorithme. Par exemple, pour entraîner un réseau de neurones à apprendre le routage automatique, la boucle externe met à jour les paramètres du réseau, et la boucle interne calcule un chemin à travers le graphe
Avec Monte-Carlo, s’il n’y a pas de biais, on peut réduire cette boucle interne qui contrôle la précision à une seule itération. La variance augmentera et ralentira la boucle externe, mais le machine learning peut « en théorie » apprendre
On peut ainsi créer une politique qui choisit intuitivement les bonnes décisions, comme aux échecs ou au go. Dans des variantes de recherche arborescente Monte-Carlo comme AlphaGo Zero, AlphaChess Zero ou AlphaRouter Zero, même sans la partie recherche, l’immense cache encodé dans les paramètres du réseau de neurones peut, après apprentissage, calculer la meilleure estimation de chemin en un seul passage dans le réseau, donc en temps constant. Cette constante permet d’échanger facilement mémoire et vitesse en augmentant le nombre de paramètres ou en entraînant plus longtemps
MC est un algorithme qui garde les pieds sur terre. Il est lent, mais presque toujours très simple à implémenter, et fiable pour revérifier avec une très grande confiance qu’on n’est pas parti complètement dans le décor
C’est une excellente discussion sur le routage automatique, mais la conclusion parlant de « pièce maîtresse qui rend possible le vibe-building de l’électronique » m’a fait un peu mal
Le routage en lui-même est facile. Cela devient complexe dès qu’il faut arracher ce qui a déjà été routé pour ajouter une nouvelle piste, et l’explosion combinatoire arrive
L’ancien autorouteur de KiCad me manque. Il avait été retiré pour des raisons floues de propriété intellectuelle, parce que son auteur avait travaillé dans une entreprise d’autoroutage. Aux utilisateurs qui demandaient son retour, on répondait en gros : « les vrais hommes n’utilisent pas d’autorouteur »
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
J’espère que cet autorouteur, ainsi que les outils qui suivront, permettront à des gens de lancer leur premier produit électronique sans beaucoup de repères ni de formation formelle
Bien sûr, un bon autorouteur devrait aussi être utile aux experts, donc j’espère qu’il aidera aussi de ce côté-là
Mais en tant que vieux grincheux qui n’a pas très envie de voir KiCad consacrer trop d’efforts aux autorouteurs, les autorouteurs PCB ont toujours été une plaie et n’ont jamais vraiment bien fonctionné
Pour comprendre pourquoi, il suffit de regarder les autorouteurs VLSI. Les autorouteurs VLSI aussi étaient une plaie et ne fonctionnaient pas bien. Puis le VLSI s’est retrouvé avec énormément de couches, au point de pouvoir réserver des couches au routage vertical, des couches au routage horizontal, des couches à l’alimentation, tout en gardant encore quelques couches pour les connexions verticales globales, les connexions horizontales globales et l’alimentation globale
Le problème fondamental du routage automatique de PCB, c’est qu’un PCB comporte beaucoup plus d’obstacles qu’une puce VLSI. Premièrement, les composants eux-mêmes sont à la fois des obstacles et des goulots d’étranglement. Deuxièmement, les vias de PCB bloquent presque toujours toutes les couches de la carte, alors que les vias VLSI ne bloquent que les deux couches qu’ils relient. Troisièmement, les vias de PCB sont généralement plus larges que la largeur du métal de routage. Quatrièmement, les PCB utilisent beaucoup moins de couches que le VLSI. Le cas courant est 4 couches, dont seulement 2 sont réellement utilisables pour le routage général ; pour des raisons de coût, les cartes 2 couches sont aussi nombreuses et encore plus difficiles à router automatiquement, tandis que les 6 couches restent très minoritaires
Résultat : le routage automatique de PCB est une tâche bien plus complexe que le routage automatique VLSI
Le fait que l’article insiste particulièrement sur la visualisation et les effets de cache est une bonne chose
Mais certains points me gênent. Dire qu’« un algorithme récursif est une recherche en profondeur, et qu’une boucle qui explore les candidats ou les voisins sans les trier est une recherche en largeur » est faux, ou passe à côté de l’intuition. DFS et BFS peuvent tous deux s’écrire avec des boucles ou avec de la récursion ; la vraie différence est de savoir si l’on retire le prochain candidat du haut ou du bas de la pile, autrement dit si l’on utilise une pile (FILO) ou une file (FIFO)
Dire qu’A* est la meilleure base pour toute recherche guidée par l’information demande aussi du contexte. C’est utile pour la recherche de chemin lorsqu’il existe une notion de « distance » jusqu’à l’objectif facile à calculer, et que l’on ne lance que quelques requêtes sur le même graphe. Si l’on prévoit de lancer de nombreuses requêtes sur un graphe presque statique, comme un réseau routier, un algorithme de prétraitement comme les contraction hierarchies peut être meilleur. Si l’on optimise sans objectif fixé, comme dans le problème du voyageur de commerce, d’autres heuristiques de recherche locale comme 2-opt peuvent être préférables
« BFS explore tous les nœuds adjacents et A* privilégie les nœuds proches de la destination » est bien une différence, mais la différence la plus importante est qu’A* est un algorithme dynamique. Il peut donc s’arrêter tôt avec la certitude d’avoir trouvé le plus court chemin. BFS peut ne pas avoir cette certitude avant d’avoir exploré tout le graphe, qui peut être énorme
Dans la plupart des langages, c’est plus facile à exprimer ainsi que de raisonner avec une pile externe. Donc, en pratique, quand on voit de la récursion dans du code, il y a de fortes chances que ce soit plus proche de DFS, mais ce n’est pas une règle stricte
BFS utilise une file FIFO, DFS une pile LIFO, et A* une file de priorité, généralement implémentée avec un tas
C’est l’un des invariants fondamentaux qui rendent BFS correct, donc on peut s’arrêter tôt une fois tous les objectifs atteints
La différence entre A* et BFS est que BFS ne cherche pas le plus court chemin entre deux points, mais les plus courts chemins depuis un point de départ unique vers tous les points du graphe. A* accepte de répondre à une question plus faible en échange d’une accélération des requêtes individuelles
Si la structure du problème le permet, remplacer des milliers d’appels à A* par un seul appel à BFS ou à Dijkstra peut déjà apporter un gros gain de performance. Une autre différence importante est que BFS ne fonctionne que sur les graphes dont toutes les arêtes ont la même longueur, tandis qu’A* prend en charge des longueurs d’arêtes différentes. Ils ne sont pas interchangeables, tout comme chercher l’élément minimal d’une liste ne remplace pas le tri de cette liste
Dire que « les quadtrees et toutes les structures de données arborescentes génériques sont follement lentes », que « les arbres ne sont pas une représentation contenant de l’information sur les données », ou qu’« à chaque fois qu’on utilise un arbre, on remplace un algorithme de hachage en O(~1) par un algorithme plus complexe en O(log N) » va franchement dans la mauvaise direction
Une approche par hachage convient si les points sont uniformément répartis et si les requêtes portent sur des zones proches du découpage fixe choisi. Sinon, ce O(1) peut s’effondrer en O(n)
Quand on ne connaît pas la distribution des données, un arbre est une représentation porteuse d’information
Les algorithmes aléatoires sont du même ordre. Que faire si l’espace de recherche contient des milliers de milliards d’éléments ou de possibilités, voire davantage ? Et s’il n’y a même pas d’heuristique ? Dans une situation où la force brute est impossible et où l’on ne peut pas employer d’algorithme intelligent, les algorithmes aléatoires deviennent une planche de salut
Cette application précise n’en a peut-être pas besoin, mais mieux vaut éviter les affirmations généralisées
Plus sérieusement, les algorithmes basés sur des arbres ont tendance à être surestimés, et les gens semblent se focaliser tellement sur le comportement en notation grand O qu’ils oublient que les facteurs constants restent très importants même avec des centaines de milliers d’éléments. Il en va de même pour la localité des données. Parfois, un simple balayage séquentiel est plus rapide que toute la comptabilité liée à une structure plus complexe
Globalement, mieux vaut encapsuler les opérations dans de petits wrappers, commencer par une implémentation simple, puis décider à partir des mesures
Dans le pire des cas, il faudra réécrire tout le programme autour d’une autre structure pour obtenir de meilleures performances, mais d’après mon expérience, réécrire un fichier depuis zéro apporte aussi pas mal d’améliorations gratuites
Je n’ai pas encore trouvé de méthode satisfaisante pour stocker des points 2D ou 3D et interroger les points voisins. Les k-d trees sont bien, mais je veux pouvoir ajouter des points au fil de l’eau, plutôt que construire la structure à partir d’un ensemble fixe
Presque tout correspond à mes heuristiques de développement de jeux. Le choix de JavaScript se comprend aussi
Je suis en train de créer un framework de modding de jeu qui fonctionne actuellement avec des S-expressions à la Lisp, et je me rends compte que l’optimisation qui réduit le temps d’itération créative est plus importante que tout
A*, l’algorithme de Lee, tout ça est excellent. Ne pas accompagner n’importe quel type de flood fill d’une visualisation frôle le crime. C’est un tel gâchis de dopamine
En lisant cet article, je me demande si des techniques que je n’ai pas lues mais qui gravitent autour du développement de jeux pourraient aussi être utiles à ce genre de problème. Je ne dois pas être le premier à penser qu’un routeur à base de boids serait assez amusant. Plus sérieusement, un champ de distance signée basé sur le jump flooding pourrait donner beaucoup de puissance
En particulier, ce qui est dit sur le hachage spatial correspond à mon expérience. En presque 20 ans, j’ai rarement vu des structures en arbre valoir le temps qu’elles demandaient. Il y a une exception : l’éditeur de texte lovecraftien que j’ai créé utilise beaucoup un trie pour le traitement réactif. C’était une bonne façon de transformer 45 000 mots en machine à états compressée pour le traitement d’événements
J’ai déjà écrit sur un autorouteur à motifs récursifs ; l’espace des solutions y est petit, donc il est assez facile à prédire avec des algorithmes de machine learning classiques. Il reste énormément de territoires intéressants et inexplorés dans l’autoroutage
Je ne connaissais pas le jump flooding. Pour les autres : c’est un algorithme qui approxime rapidement et en parallèle des champs de distance. Ça pourrait clairement être intéressant, merci de me l’avoir signalé
Les arbres se prêtent aussi bien aux algorithmes récursifs, et comme l’auteur dit avoir des raisons de préférer les algorithmes itératifs aux récursifs, ces conseils s’imbriquent
Plus largement, la distinction entre « récursif » et « non récursif » est quelque peu artificielle. La vraie question est : « le contrôle du flux est-il assuré par un algorithme préconçu aux règles strictes, ou par moi ? » Si l’on se soucie beaucoup des performances, la réponse devrait être : par moi. Et quand l’état d’exécution est abstrait dans la pile fournie par l’environnement d’exécution, au point de devenir difficile à modifier de façon inhabituelle au runtime, cela commence à être un obstacle
Dire que « 95 % de la concentration doit être consacrée à réduire le nombre d’itérations, donc le langage n’a pas d’importance » est vrai dans une certaine mesure. Mais si, après avoir conçu un excellent algorithme performant dans un langage interprété, abstrait, lent, ludique et expressif, les performances comptent encore, il suffit de réécrire la même chose dans un langage bas niveau performant, puis d’écrire de l’assembleur spécifique à l’architecture si nécessaire
Ce n’est pas pour rien que numpy, pandas, OpenCV, TensorFlow ne sont pas écrits en pur Python. Python sert à orchestrer des opérations implémentées en C++/assembleur/CUDA hautes performances, etc.
On peut être très fier d’avoir exploré l’espace du problème, trouvé un algorithme efficace et écrit un billet de blog dessus ; si l’on avait insisté pour tout écrire uniquement en Python pur ou en JavaScript pur, il aurait été difficile d’en faire une bibliothèque de calcul numérique populaire
L’article est intéressant, mais si les intuitions algorithmiques de l’auteur avaient fait passer un encodeur HEVC en JavaScript pur d’un jour par frame à trois heures par frame, je pense qu’il aurait été difficile d’arriver à la même conclusion
Je vois plein de mots-clés dont je me souvenais de l’université. J’aimerais avoir l’occasion d’utiliser des algorithmes célèbres et élégants
En réalité, je ne fais que créer des composants UI et des API REST pour afficher des résultats Elasticsearch. Toutes les choses intéressantes sont enfouies dans des boîtes noires
Dans le développement de jeux, il y a beaucoup d’algorithmes inévitables ; si vous voulez en concevoir, essayez de faire quelque chose comme un tower defense, vous manipulerez beaucoup d’algorithmes classiques
À tout le moins, je pense qu’il faut découper l’actuel diplôme d’informatique. La belle partie mathématique devrait devenir un diplôme séparé, éventuellement fusionné avec un nouveau diplôme lié à l’IA. La théorie des bases de données et des réseaux devrait aussi devenir un diplôme distinct, tout comme l’assembleur bas niveau. Le fonctionnement des composants électroniques, des portes NAND, de l’algèbre booléenne, etc., devrait relever de l’électronique
Pour les personnes dont le marché a le plus besoin, capables de produire des applications CRUD à la chaîne, si l’on tient absolument à dire qu’un savoir académique est nécessaire, il faut en faire un diplôme séparé ou le déplacer vers la formation professionnelle
En parallèle, il faut aussi traiter juridiquement le filtrage des exigences de recrutement. On devrait empêcher les entreprises d’exiger des diplômes qui n’ont presque rien à voir avec le poste réel. Aujourd’hui, on fait perdre aux jeunes des années de leur vie et on les endette de montants à cinq ou six chiffres en dollars, uniquement pour faciliter le tri des candidats par les entreprises
Je ne traite pas directement de problèmes spatiaux 2D/3D, mais la plus grande leçon est la valeur de la visualisation
Les humains sont très doués pour comprendre et analyser des images. Une autre idée est d’utiliser d’abord des méthodes probabilistes ou la force brute pour saisir la forme du problème, puis de choisir une meilleure méthode en conséquence, et pas seulement sur la base d’une compréhension purement théorique
Dire que « le langage d’implémentation n’a pas d’importance » est peut-être vrai dans ce domaine, mais appliqué au génie logiciel en général, je pense que l’hypothèse selon laquelle le choix du langage n’affecte ni la vitesse ni le nombre d’itérations nécessaires est largement fausse
Si l’on en est à contrôler des termes exponentiels ou polynomiaux, la différence entre Rust ou de l’assembleur codé en dur, et JavaScript ou VisualBasic, peut devenir assez insignifiante