- La experiencia de desarrollar durante cerca de 1 año un autorouter de PCB open source para tscircuit muestra que los diseños que reducen el problema de búsqueda, como A*, la visualización, la partición espacial y el caché, son la clave del rendimiento
- El enfoque de la optimización está en reducir la cantidad de iteraciones más que en el lenguaje o la velocidad de una sola iteración, y aun en JavaScript un algoritmo más inteligente y cacheable puede ser más rápido que una implementación de bajo nivel
- En búsquedas espaciales, un Spatial Hash Index puede ser más simple y rápido que árboles genéricos como QuadTree, aunque si se elige mal el tamaño de celda puede haber un alto costo fijo en cada consulta
- Un pipeline de autorouter complejo requiere visualizar la entrada y salida de cada etapa y revisar el proceso iterativo con animaciones, y las funciones recursivas y los enfoques Monte Carlo son desventajosos para depuración, optimización y determinismo
- A* puede sacrificar parte de la optimalidad con el Greedy Multiplier de Weighted A* para aumentar mucho la velocidad, y cada etapa debe reducir la probabilidad de fallo para dejar un estado más fácil de resolver a las etapas posteriores
Usar A* como herramienta de búsqueda base
- A* no es un algoritmo exclusivo para rejillas 2D, sino un algoritmo base que puede usarse en varias formas de búsqueda informada (informed search)
- BFS explora todos los nodos vecinos, pero A* prioriza la exploración de los nodos más cercanos al destino
- Como usa una métrica de distancia externa al grafo, se considera una búsqueda informada
- Los algoritmos recursivos se parecen más a una búsqueda en profundidad (DFS), y los bucles que exploran sin ordenar candidatos o vecinos se parecen más a BFS
- Cambiar código existente con forma de BFS o DFS a A* suele dar grandes mejoras de rendimiento
- En un autorouter se usan varios niveles de A* para encontrar los hiperparámetros adecuados para el problema
- Se ejecuta cada configuración del autorouter como candidata
- A las configuraciones que empiezan a resolver el enrutamiento con buen costo se les asignan más iteraciones
- Es una forma de meta-A* que usa tanto el costo de distancia como el costo de iteración como penalización
El algoritmo importa más que el lenguaje
- El autorouter de tscircuit está escrito en JavaScript, y en discusiones de rendimiento muchas veces lo primero que se cuestiona es el lenguaje
- La optimización algorítmica se divide en dos ejes principales
- Reducir la cantidad de iteraciones necesarias para hacer el algoritmo más inteligente
- Aumentar la velocidad de ejecución de cada iteración
- Si uno se enfoca demasiado en mejorar la velocidad de una sola iteración, puede terminar solo ejecutando más rápido un enfoque equivocado
- Por ejemplo, convertir todo a una rejilla para comprobar superposiciones puede volverse lento sin importar el lenguaje
- Un algoritmo inteligente en JavaScript puede ser más rápido que un algoritmo simple en ensamblador optimizado de bajo nivel
- Conviene dedicar el 95% del tiempo de desarrollo a reducir la cantidad de iteraciones, y un buen lenguaje es el que te ayuda a llegar rápido al algoritmo más inteligente y cacheable
Spatial Hash Index puede ser mejor que un árbol
- En optimización espacial multidimensional, QuadTree aparece con frecuencia, pero las estructuras de árbol de propósito general pueden ser lentas
- QuadTree es conocido como una estructura que reduce la búsqueda de objetos cercanos en espacios 2D o 3D de
O(N)aO(log(N)), pero un árbol no es una representación informada de los datos - Un Spatial Hash Index no hace hash del objeto en sí, sino de su posición, y lo guarda en una celda o en un bucket de elementos cercanos
- Este enfoque aplica el acceso rápido basado en hash, como en HashSet o HashMap, a datos espaciales
- La razón por la que el hash espacial es menos popular es que hay que elegir un tamaño de celda adecuado
- Si el tamaño de celda está mal ajustado, cada consulta puede tener un alto costo fijo
- En la práctica, no parece tan difícil elegir un tamaño de celda razonable
La partición espacial y el caché cambian el rendimiento
- Una placa como el interior de un iPhone puede tener aproximadamente entre 10,000 y 20,000 traces, y hasta con herramientas EDA de primer nivel un equipo puede pasar meses enrutándola
- Una idea simple e importante en el problema de autorouting es que lo que ya fue enrutado probablemente ya fue enrutado antes
- Los desarrolladores de juegos hornean con antelación las mallas de navegación, y los LLM comprimen internet en pesos para búsqueda
- La siguiente generación de autorouters podrá dividir el problema espacialmente y aprovechar un gran caché con soluciones ya resueltas
- Si el 99% del problema de autorouting ya está resuelto en caché, la velocidad del algoritmo en sí importa menos
- Muchos algoritmos actuales no ponen suficiente énfasis en la reutilización de caché y la partición espacial
- El costo de almacenamiento y caché parece bajar más rápido que el aumento en velocidad de cómputo, así que usar 1 GB de caché para hacer un autorouter 50% más rápido no parece un gran problema
Ver el problema directamente con visualización y profiling
- Es importante el principio de que sin visualización no se puede resolver el problema
- Mirar solo números dificulta la depuración, y crear visualizaciones para cada subproblema pequeño ayuda a entenderlo mucho más rápido
- En el desarrollo del autorouter, muchas veces la resolución del problema empieza por la visualización
- Incluso se visualizó el subalgoritmo para encontrar rutas a 45 grados, que se usa en la fase de simplificación de rutas, casi al final del autorouter
- Las herramientas de profiling de JavaScript muestran el tiempo total consumido en cada línea de código en milisegundos
- Basta con ejecutar JavaScript en el navegador y abrir la pestaña Performance
- También ofrecen flame charts y funciones de uso de memoria
- Video corto relacionado: youtube short
Evitar recursión y Monte Carlo
- Conviene evitar las funciones recursivas en código orientado al rendimiento
- Casi siempre funcionan de forma síncrona, por lo que es difícil interrumpirlas a mitad para animación
- Por naturaleza se parecen a DFS y no es fácil convertirlas a A*
- No es sencillo rastrear la cantidad de iteraciones
- En una función recursiva, la mutabilidad es poco natural, pero para el rendimiento puede ser importante
- Las implementaciones iterativas pueden ser más rápidas porque mantienen un conjunto
visitedNodesy permiten comprobar nodos antes de explorarlos - Los algoritmos Monte Carlo se acercan a la solución con aleatoriedad, pero al no ser deterministas son difíciles de depurar y rara vez parecen óptimos frente a heurísticas
- Cuando se sabe cómo evaluar candidatos pero no cómo llegar a la solución, un enfoque Monte Carlo puede ayudar a ganar intuición
- Una vez que se tiene algo parecido a una función de costo, conviene usar métodos mejores que técnicas aleatorias como Monte Carlo o Simulated Annealing
- Si hay sensibilidad a mínimos locales, se pueden considerar hiperparámetros o una función de costo más compleja
- Así como un diseñador de PCB no dibuja líneas al azar sobre la placa, en este dominio parece posible encontrar mejores heurísticas
Mantener los algoritmos intermedios en el mismo sistema de coordenadas
- El autorouter actualmente es un pipeline compuesto por 13 etapas y alrededor de 20 subalgoritmos
- Se mide la cantidad de iteraciones en tareas como decisiones de partición espacial o simplificación de rutas en los bordes de zonas autorouteadas de forma independiente
- Superponer y visualizar la entrada y salida de cada etapa ayuda a entender el contexto del problema que se está resolviendo
- Los problemas de etapas downstream, en especial la etapa de high density routing, muchas veces se resuelven mejorando la salida de etapas anteriores
- Al crear un subalgoritmo, existe la tentación de aislar el problema en su forma más simple y normalizar coordenadas alrededor de
(0, 0) - La normalización o las transformaciones complejas pueden dificultar ver rápidamente cómo los resultados de una etapa inicial afectan a las etapas posteriores
- Es ventajoso mantener un espacio de coordenadas consistente a lo largo de todo el ciclo de vida del algoritmo
- Ver cada etapa en orden y hacer zoom ayuda a encontrar qué etapa causó un Design Rule Check fallido
Animar iteraciones y evitar rejillas
- Como es importante reducir la cantidad de iteraciones, ver las iteraciones del algoritmo en animación ayuda a detectar de forma intuitiva la exploración desperdiciada
- La animación es especialmente útil al ajustar el Greedy Multiplier
- Hubo casos en que un trace simple, en una situación donde debía fallar de inmediato, no fallaba sino que seguía intentando resolver hacia afuera indefinidamente, algo difícil de detectar sin animación
- Hay dos formas generales de determinar si dos traces A y B se superponen
- Revisar cada segmento de A y B para ver si se cruzan
- Marcar la rejilla donde existe B y luego comprobar si A pasa por una rejilla donde está B
- El enfoque de rejilla puede volverse fácilmente 1000 veces más lento
- Con matemática vectorial rápida, un dot product para detectar la intersección de dos segmentos puede ser más rápido que un acceso a memoria para revisar una sola celda de rejilla
- Estrictamente hablando, para garantizar el margen adecuado hay que calcular la distancia entre segmentos, lo cual es un poco más complejo que detectar intersecciones, pero no tan diferente
Probabilidad de fallo y Weighted A*
- En la etapa de partición espacial, la probabilidad de fallo de resolución en cada etapa puede medirse como un indicador adelantado
- Unravel Autorouter rastrea la probabilidad de fallo de cada Capacity Node en cada etapa principal del pipeline
- Cada etapa se enfoca en reducir la probabilidad de fallo mediante reconstrucción de nodos vecinos o rerouting
- La probabilidad de fallo puede medirse de verdad, y las predicciones también pueden mejorar si cambia el algoritmo
- Cada etapa puede actuar de manera que reduzca la probabilidad de fallo de etapas posteriores
- En lugar de meter demasiadas restricciones de una sola vez, conviene priorizar la capacidad de resolver
- Una vez que la placa se resuelve, muchas veces es más fácil trabajar sobre una solución existente que generar una solución óptima desde cero
Compensar velocidad y optimalidad con Greedy Multiplier
- A* básico garantiza una solución óptima, pero si se prioriza más la velocidad se puede modificar un poco
f(n)y usar Weighted A* - A* normal:
f(n) = g(n) + h(n) - Weighted A*:
f(n) = g(n) + w * h(n) - Weighted A* resuelve el problema de forma más codiciosa y por lo general funciona mucho más rápido
- Este método actúa como un Greedy Multiplier que mejora mucho el rendimiento de A* a cambio de renunciar a parte de la optimalidad
- Puedes ver más sobre Weighted A* y otras variantes de A* en weighted A* and other A* variants here
- Los desarrolladores de juegos enfrentan muchos problemas parecidos a los de quienes desarrollan autorouting, así que al buscar investigación relacionada vale la pena revisar papers de desarrollo de videojuegos
Autorouter próximo a publicarse
- El autorouter para tscircuit se está acercando a su lanzamiento
- El trabajo se ofrecerá como open source bajo licencia MIT
- Resolver el autorouting puede abrir una gran ola de innovación en el mundo físico, y se considera una pieza clave para hacer posible el “vibe-building” de productos electrónicos
- Cuenta relacionada: follow me on twitter.
1 comentarios
Opiniones en Hacker News
En general, no confío en los autorouters, y lo mismo con las herramientas de IA que están entrando en este campo, pero es difícil negar que hay una gran oportunidad para crear rápidamente partes del layout en eCAD.
Creo que usaría más herramientas de co-creación que herramientas totalmente automáticas. En las primeras etapas del diseño, muchas veces la ubicación de los componentes no está definida, y esa ubicación influye mucho en el ruteo. No vi en la página si la colocación está incluida en el algoritmo. Ya uso herramientas como push-and-shove o, a veces, autocompletado.
Este mercado es pequeño, las herramientas están fragmentadas, los proveedores existentes son gigantes lentos y los usuarios son entusiastas exigentes. A KiCad no lo suelto ni muerto. No tengo una opinión muy fuerte sobre el hecho de que el autorouter esté escrito en JavaScript, pero me pregunto si el plan es integrarse con proveedores de CAD o con el ecosistema de herramientas open source, o si quieren atraer a la gente a otro ecosistema nuevo.
Si es amigable con la caché, mover componentes y probar otros layouts se vuelve mucho más rápido. JavaScript ahora tiene runtimes pequeños como QuickJS o Proffor, así que es bastante portable, y creo que se podrá ejecutar localmente y construir una caché enorme directamente.
El lock-in y la fragmentación del ecosistema en EDA son cosas que deberían preocuparnos a todos, pero tscircuit y este autorouter son tecnologías con licencia permisiva MIT, algo raro en EDA, por lo que pueden hacerse interoperables con todos.
Una vez fijados los footprints, la colocación, las restricciones y las nets ruteadas manualmente, se podía iterar muy rápido.
Desde que Cadence compró SPECCTRA en los 90, los autorouters de PCB quedaron bastante estancados, así que da gusto ver que alguien vuelva a abordar este tema. Según recuerdo, quienes hicieron SPECCTRA se fueron hacia VLSI y no volvieron; parece que ahí estaban el prestigio y el dinero. También pudo haber sido un campo minado de patentes durante un tiempo, y quizá todavía lo sea.
La colocación automática ya era un problema totalmente difícil de manejar en esa época y parece que sigue siéndolo, pero un enfoque de IA generativa podría encajar bien. Una buena colocación inicial de componentes basada en IA generativa podría reducir el tiempo total. El mayor problema es convencer a gente testaruda de que algo puede ser suficientemente bueno aunque no sea perfecto.
Los intentos de hacer esquemáticos como código me resultan un poco desconcertantes. Como formato backend, ojalá funcione bien, y en particular se ven bien avances como los de jitx, donde se codifican reglas de diseño a nivel de app notes y datasheets dentro de los modelos de componentes. Leer todos los datasheets al nivel necesario para un diseño comercial requiere mucho más trabajo de lo que parece, y lograr que un ingeniero junior aprenda ese proceso también, así que automatizarlo es útil.
Sin embargo, esos enfoques parecen estar arraigados en la idea de ver el esquemático como entrada de datos para el layout, una especie de código fuente. Un esquemático también es un documento de diseño con un lenguaje visual cuidadosamente evolucionado, que debería ser accesible incluso para personas que no tienen instalada una suite EDA. Quienes aprendieron descifrando esquemáticos con cableado explícito mínimo al estilo Adafruit/Sparkfun/Shenzhen quizá no aprecien el valor de un buen esquemático.
Otra cosa es la tendencia a apoyarse demasiado en la analogía e intentar hacer que el diseño a nivel de PCB se parezca al diseño VLSI. No creo que sea totalmente imposible. Si las herramientas de DRC y verificación mejoran, el diseño a nivel de componentes también puede acercarse más al VLSI. Pero el acoplamiento entre diseño, EDA/CAM/simulación, verificación, fabricantes, ensambladores, proveedores de componentes y organismos regulatorios/de certificación es tan flojo que lograr hacer bien una sola esquina de todo eso ya sería un gran resultado.
Hoy en día, el flujo es hacer diseños UHF con control de impedancia junto con herramientas de simulación específicas del dominio. Por eso primero se rutean manualmente las trazas importantes, se crean islas y planos, y al final se manejan las conexiones de alimentación.
El layout de KiCad es un poco mejor que no tener nada, pero intentar convertirlo en otra herramienta de simulación a medias parece ridículo.
Son el soporte de bases de datos y las funciones de outjob. Más allá de eso, se trata más bien de adopción y de cómo los usuarios aprovechan esas funciones; las bases de datos normalmente traen consigo más burocracia interna relacionada con el ordenamiento de datos.
Desde la perspectiva de flujos de trabajo para acelerar el layout, creo que KiCad ya va en cierta medida en esa dirección. Por ejemplo, está la función de “autocompletar trazas”, que creo que entró alrededor de la 7.0. En pcbnew, creo que era el atajo F, y coloca la traza del track que estás ruteando en ese momento. Si se usa junto con el atajo E de “rutear desde el otro extremo del track”, la productividad sube mucho cuando trabajas entre dos grids de ballout distintos.
En la versión 9, poder arrastrar buses o varios tracks podría acelerar aún más este flujo.
Sinceramente, si se puede llegar a una colocación satisfactoria y darle al autorouter restricciones sobre dónde rutear, creo que una parte considerable del diseño se le podría dejar al autorouter. Por ejemplo, el año pasado hice una placa con un NXP iMX8MP y eMMC, y el ballout alrededor del procesador encajaba bien con el ballout de la eMMC, así que bastaba con alinear los chips y trazar líneas. Si el autorouter solo hubiera sabido que debía mantener el bus de datos en la capa superior, habría hecho en segundos un trabajo que tomó 10 minutos.
Hay un problema con los criterios de éxito que enfrentan los proyectos de autorouters. Parece que consideran que solo están “terminados” si pueden manejar todo en la placa, pero como ingeniero eléctrico en la práctica, eso no es lo que quiero. Quiero un autorouter que trabaje conmigo en pequeños bloques del diseño, uno por uno, me dé tiempo para revisar y luego pase al siguiente bloque.
Si además se le pueden dar restricciones que crucen capas, sería potente. Por ejemplo: “mantén todas las nets llamadas D0-7 en las capas 1 y 3, iguala sus longitudes dentro de 5 mm entre sí y usa D0 como referencia de longitud”. Si puede hacer eso, básicamente resuelve el ajuste de longitudes de DRAM, y diseños de mucha mayor complejidad se vuelven posibles para usuarios comunes.
Cuando tenga tiempo, me gustaría mostrar en una demo a qué me refiero.
En el punto 8, fue un gran error descartar demasiado rápido el método de Monte Carlo
La clave de Monte Carlo es que permite intercambiar precisión por velocidad. Mientras más tiempo se ejecute el algoritmo, más preciso se vuelve.
Lo más interesante es que el recíproco también se puede usar a menudo: se puede obtener muy rápido un resultado muy impreciso. Por ejemplo, en vez de explorar todas las rutas, se explora solo una ruta elegida al azar.
Este enfoque brilla cuando se coloca en el bucle anidado más interno del algoritmo. Por ejemplo, para entrenar una red neuronal que aprenda autoruteo, el bucle externo actualiza los parámetros de la red neuronal y el bucle interno calcula una ruta a través del grafo.
Con Monte Carlo, si no hay sesgo, ese bucle interno que controla la precisión puede reducirse a una sola iteración. La varianza aumentará y el bucle externo se volverá más lento, pero el aprendizaje automático “en teoría” podrá aprender.
Así se puede crear una política que elija de forma intuitiva las decisiones correctas, como en ajedrez o Go. En variantes de búsqueda de árboles Monte Carlo como AlphaGo Zero, AlphaChess Zero o AlphaRouter Zero, incluso sin la parte de búsqueda, una enorme caché codificada en los parámetros de la red neuronal puede, después del entrenamiento, calcular la mejor ruta estimada con una sola pasada por la red neuronal, es decir, en tiempo constante. Ese constante puede ajustarse fácilmente intercambiando memoria y velocidad, aumentando los parámetros o entrenando durante más tiempo.
MC es un algoritmo que te mantiene con los pies en la tierra. Es lento, pero casi siempre es muy simple de implementar, y es confiable para volver a comprobar con mucha confianza que no te fuiste por completo a cualquier lado.
Es una excelente discusión sobre autoruteo, pero me dolió un poco que terminara diciendo que es “la pieza clave que permite el vibe-building de productos electrónicos”
El ruteo en sí es fácil. Se vuelve complejo en el momento en que hay que arrancar lo que ya estaba colocado para meter una nueva pista, y ahí llega la explosión combinatoria.
Extraño el autorouter que antes tenía KiCad. Se quitó por razones medio ambiguas de propiedad intelectual, porque su autor había trabajado en una empresa de autoruteo. A los usuarios que pedían que lo volvieran a incluir les respondían algo como “los hombres de verdad no usan autorouters”.
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
Espero que este autorouter y las demás herramientas que vengan después ayuden a que la gente pueda lanzar su primer producto electrónico sin mucho mapa ni educación formal.
Por supuesto, un buen autorouter también debería ser útil para expertos, así que espero que también ayude en ese sentido.
Pero como uno de esos viejos quisquillosos a los que no les entusiasma ver que KiCad dedique esfuerzos al autoruteo, los autorouters para PCB siempre son un dolor de cabeza y no funcionan bien.
Para entender por qué, basta con mirar los autorouters de VLSI. Los autorouters de VLSI también eran un dolor de cabeza y no funcionaban bien. Luego VLSI pasó a tener muchísimas capas, al punto de poder asignar capas separadas para ruteo vertical, ruteo horizontal y alimentación, y aun así tener varias capas adicionales para conexiones verticales globales, conexiones horizontales globales y alimentación global.
El problema fundamental del autoruteo de PCB es que una PCB tiene muchos más obstáculos que un chip VLSI. Primero, los propios componentes son obstáculos y cuellos de botella. Segundo, las vías de PCB casi siempre bloquean todas las capas de la placa, mientras que las vías de VLSI solo bloquean las dos capas que conectan. Tercero, las vías de PCB suelen ser más grandes que el ancho del metal de las pistas. Cuarto, la cantidad de capas que se usan en PCB es mucho menor que en VLSI. Lo común son 4 capas, de las cuales solo 2 se usan realmente para ruteo general; por costos también hay muchas de 2 capas, que son aún más difíciles de autorutear, y las de 6 capas son una minoría muy pequeña.
En consecuencia, el autoruteo de PCB es una tarea mucho más compleja que el autoruteo de VLSI.
Me gustó que el texto le diera especial importancia a la visualización y al efecto de la caché.
Pero hay algunas cosas que me hacen ruido. Decir que “un algoritmo recursivo es una búsqueda en profundidad, y un bucle que explora candidatos o vecinos sin ordenarlos es una búsqueda en anchura” parece incorrecto, o al menos pierde la intuición. Tanto DFS como BFS pueden escribirse con bucles o con recursión; la diferencia real es si sacas el siguiente candidato de la parte superior o inferior de la pila: es decir, si usas una pila (FILO) o una cola (FIFO).
También hace falta contexto para decir que A* es la mejor base para toda búsqueda basada en información. Es útil para encontrar caminos cuando existe una noción de “distancia” hasta el objetivo que sea fácil de calcular y cuando solo vas a hacer unas pocas consultas sobre el mismo grafo. Si planeas hacer muchas consultas sobre un grafo casi estático, como una red vial, quizá convenga más un algoritmo de preprocesamiento como contraction hierarchy. Si estás optimizando sin un objetivo fijo, como en el problema del viajante, quizá funcionen mejor otras heurísticas de búsqueda local como 2-opt.
“BFS explora todos los nodos adyacentes y A* prioriza los nodos cercanos al destino” sí es una diferencia, pero la diferencia más grande es que A* es un algoritmo dinámico. Por eso puede terminar antes, con la certeza de haber encontrado el camino más corto. BFS quizá no pueda estar seguro hasta explorar todo el grafo, y el grafo puede ser enorme.
En la mayoría de los lenguajes, es más fácil expresarlo así que pensar en una pila externa. Por eso, si ves recursión en código real, es muy probable que esté más cerca de DFS, pero no es una regla estricta.
BFS usa una cola FIFO, DFS usa una pila LIFO, y A* suele usar una cola de prioridad implementada con un heap.
Esta es una de las invariantes básicas que hacen que BFS dé resultados correctos, así que puede terminar antes cuando ya se llegó a todos los objetivos.
La diferencia entre A* y BFS es que BFS no busca el camino más corto entre dos puntos, sino los caminos más cortos desde un único punto de partida hasta todos los puntos del grafo. A* es un compromiso: responde una pregunta más débil a cambio de acelerar consultas individuales.
Si la estructura del problema lo permite, solo reemplazar miles de llamadas a A* por una sola llamada a BFS o Dijkstra puede dar una gran mejora de velocidad. Otra diferencia importante es que BFS solo funciona en grafos donde todas las aristas tienen la misma longitud, mientras que A* admite aristas con longitudes distintas. No son intercambiables, del mismo modo que buscar el elemento mínimo de una lista no reemplaza ordenar la lista.
Decir que “los quadtree y todas las estructuras de árbol de propósito general son increíblemente lentos”, que “los árboles no son una representación que contenga información sobre los datos” y que “cada vez que usas un árbol estás usando un algoritmo O(log N) más complejo en lugar de un algoritmo de hash O(~1)” va bastante mal encaminado.
Un enfoque con hashing está bien cuando los puntos están distribuidos uniformemente y solo consultas regiones cercanas a la partición fija que elegiste. Si no, ese O(1) puede colapsar a O(n).
Cuando no conoces la distribución de los datos, un árbol sí es una representación con información.
Con los algoritmos aleatorios pasa algo parecido. ¿Qué haces si el espacio de búsqueda tiene billones o más de elementos o posibilidades? ¿Y si tampoco tienes heurísticas? Cuando no puedes usar fuerza bruta ni un algoritmo inteligente, los algoritmos aleatorios se vuelven salvadores.
Puede que no sean necesarios para esta aplicación específica, pero es mejor evitar afirmaciones generalizadas.
Más en serio, los algoritmos basados en árboles tienden a estar sobrevalorados, y creo que la gente se obsesiona demasiado con el comportamiento Big O y olvida que los factores constantes siguen importando muchísimo incluso con cientos de miles de elementos. Lo mismo pasa con la localidad de datos. A veces es más rápido recorrer todo con un escaneo secuencial que llevar la contabilidad de una estructura más compleja.
En general, es mejor envolver las operaciones en wrappers pequeños, hacer primero una implementación sencilla y luego decidir con mediciones.
En el peor caso tendrás que reescribir todo el programa para adaptarlo a otra estructura buscando mejor rendimiento, pero por experiencia, cuando reescribes un archivo desde cero también suelen aparecer bastantes mejoras gratis.
Todavía no encontré una forma satisfactoria de almacenar puntos 2D o 3D y consultar puntos cercanos. Los kD-tree están bien, pero quiero poder ir agregando puntos a medida que avanzo, no construir la estructura a partir de un conjunto fijo.
Casi todo coincide con mis heurísticas de desarrollo de juegos. También entiendo la elección de JavaScript.
Ahora estoy creando un framework de modding de juegos que funciona con expresiones S al estilo Lisp, y me di cuenta de que lo más importante es optimizar para reducir el tiempo de iteración creativa.
Cosas como A* y el algoritmo de Lee son geniales. No crear una visualización junto con cualquier tipo de flood fill es casi un crimen. Es desperdiciar demasiada dopamina.
Al leer este artículo, me da curiosidad si técnicas que no he leído pero que están cerca del desarrollo de juegos también servirían para este tipo de problemas. Seguro que no soy la primera persona a la que se le ocurre que un router boids sería bastante divertido. Más en serio, creo que un campo de distancia con signo basado en jump flooding podría aportar mucho poder.
En especial, lo de hashing espacial coincide con mi experiencia. En casi 20 años, no he visto muchos casos en los que las estructuras de árbol valieran el tiempo invertido. Hay una excepción: el editor de texto lovecraftiano que hice usa bastante un trie para manejar reactividad. Fue una buena forma de convertir 45.000 palabras en una máquina de estados comprimida para procesar eventos.
Hace tiempo escribí sobre un autorouter de patrones recursivos, y como el espacio de soluciones es pequeño, suele ser fácil de predecir con algoritmos de aprendizaje automático existentes. Todavía hay muchas áreas interesantes sin explorar en el autorouting.
No conocía jump flooding. Para quienes no lo sepan: es un algoritmo para aproximar rápidamente campos de distancia en paralelo. Sin duda podría ser interesante; gracias por mencionarlo.
Los árboles también encajan bien con algoritmos recursivos, y el autor dijo que hay motivos para preferir algoritmos iterativos a los recursivos, así que estos consejos se conectan entre sí.
En términos generales, la distinción entre “recursivo” y “no recursivo” es algo artificial. La verdadera pregunta es: “¿un algoritmo prefabricado con reglas estrictas se encarga del control de flujo, o me encargo yo?”. Si te importa mucho el rendimiento, la respuesta debería ser que te encargues tú; cuando el estado de ejecución queda abstraído dentro de la pila que ofrece el entorno de ejecución y se vuelve difícil modificarlo de formas extrañas en runtime, empieza a estorbar.
La frase “el 95% del enfoque debe ponerse en reducir el número de iteraciones; por eso el lenguaje no importa” es cierta hasta cierto punto, pero si después de crear un algoritmo excelente y de buen rendimiento en un lenguaje interpretado, abstracto, lento, expresivo y divertido, el rendimiento sigue siendo importante, puedes reescribir lo mismo en un lenguaje de bajo nivel con buen rendimiento e incluso escribir ensamblador específico por arquitectura si hace falta.
Hay una razón por la que numpy, pandas, OpenCV, TensorFlow no están escritos en Python puro. Python se encarga de dirigir operaciones implementadas en C++/ensamblador/CUDA de alto rendimiento, etc.
Por mucho orgullo que uno sienta por haber explorado el espacio del problema, encontrado un algoritmo eficiente y escrito un blog al respecto, si hubiera insistido en escribirlo solo en Python puro o JavaScript, difícilmente se habría convertido en una biblioteca popular de cómputo numérico.
Es un artículo interesante, pero si las ideas algorítmicas del autor hubieran reducido un codificador HEVC en JavaScript puro de 1 día por cuadro a 3 horas por cuadro, creo que sería difícil llegar a la misma conclusión.
Veo un montón de palabras clave que recordaba de la universidad. Ojalá tuviera ocasión de usar algoritmos famosos y geniales.
En la práctica, solo hago componentes de UI y APIs REST para mostrar resultados de Elasticsearch. Todo lo interesante está enterrado dentro de cajas negras.
En desarrollo de juegos hay muchos algoritmos inevitables, así que si quieres crear algoritmos, prueba hacer algo como un tower defense y terminarás tratando con muchos algoritmos clásicos.
Como mínimo, creo que el título de ciencias de la computación actual debería dividirse. La parte de matemáticas elegantes debería ser un título aparte y quizá combinarse con un nuevo título relacionado con IA. La teoría de bases de datos y redes también debería ser un título aparte, y lo mismo el ensamblador de bajo nivel. Cómo funcionan los componentes electrónicos, las compuertas NAND, el álgebra booleana, etc., debería pasar a ingeniería electrónica.
Si se insiste en que quienes el mercado más necesita —personas capaces de producir aplicaciones CRUD— requieren conocimientos académicos, entonces debería crearse un título separado para eso, o trasladarlo a la formación técnica/profesional.
Al mismo tiempo, las barreras en los requisitos de contratación también deberían abordarse por ley. No debería permitirse exigir títulos que casi no tienen relación con el trabajo real. Hoy se hace que los jóvenes desperdicien años de su vida y se endeuden por montos de cinco o seis cifras en dólares, solo para que a las empresas les resulte más fácil filtrar gente.
No trato directamente con problemas espaciales 2D/3D, pero la mayor lección es el valor de la visualización.
Los humanos somos muy buenos entendiendo y analizando imágenes. Otra idea valiosa es usar métodos probabilísticos o fuerza bruta para entender primero la forma del problema y luego elegir un método mejor en función de eso, no solo a partir de una comprensión puramente teórica.
Puede que en este campo sea cierto que “el lenguaje de implementación no importa”, pero si se aplica a la ingeniería de software en general, creo que la suposición de que la elección del lenguaje no afecta la velocidad ni la cantidad de iteraciones necesarias está muy equivocada.
Si estás en la etapa de controlar términos exponenciales o polinómicos, la diferencia entre Rust o ensamblador hardcodeado y JavaScript o VisualBasic puede volverse bastante irrelevante.