Autorouter geliştirmeden önce bilseydim dediğim şeyler

"Dünyanın en hızlı otomatik yönlendiricisini (Autorouter) yapmak için önemli dersler"

A* algoritmasını her yerde kullanmak

• A*, arama problemlerinde en güçlü ve esnek algoritmalardan biridir
• Yalnızca basit 2D gridlerde değil, çok çeşitli problemlerde kullanılabilir
• A*, BFS'ye göre daha hızlı ve verimli biçimde hedefe yakın düğümleri önceliklendiren bir 'bilgi tabanlı arama' yöntemidir
• Mevcut kodda kullanılan DFS veya BFS'nin büyük bölümü A* ile değiştirilebilir
• Performansı iyileştirmek için birden fazla A* örneği çalıştırıp, aralarından iyi performans gösteren ayarlara daha fazla kaynak ayırma tekniği kullanılabilir

Programlama dilinden daha önemli olan şey algoritmadır

• Autorouter'ı Javascript ile geliştirmek hiç sorun olmadı
• Optimizasyonun özü tekrar sayısını azaltmaktır
• Dil performansından çok, “ne kadar akıllı bir algoritmayı ne kadar hızlı geliştirebildiğiniz” daha önemlidir
• Javascript, hızlı iterasyondan ziyade akıllı algoritmalar geliştirmeye daha uygundur

Ağaç yapıları yerine Spatial Hash Indexing daha verimlidir

• Quadtree gibi ağaç tabanlı veri yapıları genelde yavaştır
• Spatial Hash Index, nesnelerin konumunu hash'leyerek uzamsal olarak yakın nesneleri birlikte işlemeye olanak tanır
• Hash tabanlı yapılar O(1)'e yakın arama performansı sunar
• Hücre boyutunu doğru seçmek gerekir; uygun boyutu belirlemek de o kadar zor değildir

Uzamsal bölümlendirme ve önbellek, algoritmadan 1000 kat daha önemlidir

• Karmaşık devre kartlarının çoğu yineleyen kalıplar içerir
• Oyun geliştirmede olduğu gibi, önceden hesaplanmış sonuçları önbelleğe alarak performans büyük ölçüde artırılabilir
• Önbelleklenebilir yapılar ve uzamsal bölümlendirme, gelecekteki autorouter'ların temelini oluşturacaktır
• Depolama alanı hızla ucuzluyor ve birkaç GB'lık önbellekle bile büyük performans artışı sağlanabilir

Görselleştirme olmadan problem çözmek mümkün değil

• Her problem için önce görselleştirme aracı yaparak işe başlandı
• Görselleştirme sayesinde hata ayıklama hızı 10 katın üzerinde artırılabildi
• Basit algoritma adımları bile görselleştirildiğinde sorunun kaynağı hızlıca bulunabiliyor

Javascript'in profilleme araçları çok kullanışlıdır

• Chrome geliştirici araçlarındaki Performance sekmesinde kod bazında harcanan süre görülebilir
• Ek bir framework olmadan da Flame Chart, bellek kullanımı gibi veriler kolayca analiz edilebilir
• Performans hata ayıklaması için son derece yararlı araçlardır

Özyinelemeli fonksiyonlar kullanmayın

• Özyinelemeli fonksiyonlar genellikle senkrondur ve A*'ya dönüştürülmeleri zordur
• İterasyon tabanlı uygulamalar daha hızlıdır ve ziyaret edilen düğümleri takip etmeyi kolaylaştırır
• Özyinelemeli fonksiyonlarda durumu değiştirmek zordur ve verimsizdir
• Mümkün olduğunca döngü tabanlı yazın

Monte Carlo algoritmalarından kaçının

• Rastgeleliğe dayalı algoritmalar belirleyici değildir ve hata ayıklaması zordur
• Alana özgü sezgiseller her zaman daha iyi performans sağlar
• Rastgele çizgi çizen bir PCB tasarımcısı yoktur → bu gerçekçi bir yaklaşım değildir
• Yine de başlangıçta fikir edinmek için yararlı olabilir

Algoritma adımlarını gerçek problem uzayına sabitleyin

• Alt algoritmaları orijine göre normalize etmek, genel akışı anlamayı zorlaştırır
• Her adımın giriş ve çıkışlarını görselleştirerek hangi aşamanın hataya yol açtığı anlaşılabilir
• Koordinat sistemini tutarlı koruyarak algoritma akışını sürdürmek önemlidir

İteratif süreci animasyonla görselleştirin

• Algoritmanın ne kadar verimsiz arama yaptığını görsel olarak fark etmek mümkündür
• Animasyon, yineleme sayısını azaltmak ve verimliliği artırmak için çok etkilidir
• Problemli durumlar kolayca yakalanabilir (ör. sonsuz döngüye giren arama gibi)

Grid olmadan da kesişim tespiti matematiği yeterlidir

• Grid kullanmak yerine vektör matematiğinden yararlanmak çok daha hızlıdır
• Bellek erişiminden daha hızlı olan matematiksel işlemler de sıkça vardır
• LLM sayesinde kesişim tespiti matematiğini uygulamak da kolaylaştı
• Gereksiz grid kullanımı performans düşüşüne neden olur

Her adımın başarısızlık olasılığını ölçerek çözüm önceliklerini belirleyin

• Her uzamsal bölümlendirme düğümünde başarısızlık olasılığı tahmin edilebilir
• Daha sonraki aşamalarda başarısız olma ihtimali yüksek düğümler öncelikli olarak yeniden yapılandırılabilir veya yeniden aranabilir
• Başarısızlık olasılığı açık biçimde ölçülebilir ve sezgisellerden daha fazla iyileştirme potansiyeli taşır
• Tüm çözüm olasılığını artırmak, optimizasyonu hedeflemekten daha etkili olabilir

Weighted A* ile hız 100 kat artırılabilir

• Temel A*, en iyi yolu garanti eder ama yavaştır
• Weighted A*, daha açgözlü arama yaparak hızı ciddi biçimde artırabilir
• Yalnızca f(n) = g(n) + w * h(n) ağırlığını ayarlayarak uygulanabilir
• Bir miktar optimallikten ödün verilse bile problem çok daha hızlı çözülebilir
• Oyun geliştirmede de sık kullanılan, incelenmeye değer bir tekniktir

[GN⁺]

Hacker News görüşleri

• Monte-Carlo yöntemini hızlıca göz ardı etmek büyük bir hata

  • Monte-Carlo yöntemlerinin ayırt edici özelliği, doğruluk ile hız arasında takas yapılabilmesidir
  • Algoritmayı ne kadar uzun süre çalıştırırsanız o kadar doğru hale gelir
  • Tersine, hızlı ama hatalı sonuçlar da elde edebilirsiniz
  • Tüm yolları araştırmak yerine, rastgele seçilmiş tek bir yolu araştırır
  • Algoritmanın en iç içe geçmiş döngüsünde Monte-Carlo kullanmak etkilidir
  • Örneğin, bir sinir ağını eğitirken dış döngü sinir ağı parametrelerini günceller ve iç döngü grafik üzerinden bir yol hesaplar
  • Monte-Carlo kullanırsanız iç döngünün doğruluğunu tek iterasyona indirebilirsiniz
  • Bu, sezgisel olarak her zaman doğru kararlar veren bir politika kurmayı mümkün kılar
  • Satranç veya Go'da, en iyi yolu hesaplamak için Monte-Carlo ağaç aramasının varyantları kullanılabilir

• "Otomatik router'a güvenme" tarafındayım

  • eCAD alanında yerleşim hızını artırmak için büyük bir fırsat var
  • Tam otomasyon araçlarından ziyade ortak yaratım araçlarının kullanılma olasılığı daha yüksek
  • Tasarımın başında yerleşim belirlenmediği için bu, routing'i büyük ölçüde etkiler
  • Sayfada, yerleşimin algoritmanın bir parçası olup olmadığını göremedim
  • JavaScript ile yazılmış AR için planın ne olduğunu merak ediyorum

• Yazı, görselleştirme ve cache etkileri hakkında önemli bir noktaya değiniyor

  • Özyinelemeli algoritmalar derinlik öncelikli aramadır
  • DFS ve BFS, iteratif ya da özyinelemeli olarak yazılabilir
  • A*, yol bulma için kullanışlıdır
  • BFS tüm komşu düğümleri araştırırken, A* hedefe daha yakın düğümleri öncelikli araştırır
  • A* dinamik bir algoritmadır; en kısa yolu güvenle erken sonlandırabilir

• Otomatik routing üzerine harika bir tartışma

  • Routing'in kendisi kolaydır
  • Yeni bir şeyi sığdırmak için zaten route edilmiş olanı kaldırmanız gerektiğinde iş karmaşıklaşır
  • KiCAD'in autorouter'ını özlüyorum

• Odağın %95'i iterasyon sayısını azaltmak üzerinde olmalı

  • Performans hâlâ önemliyse, düşük seviyeli bir dilde yeniden yazmanız gerekir
  • numpy, pandas, OpenCV, TensorFlow yüksek performanslı C++/assembly/CUDA ile uygulanmıştır

• QuadTree ve genel ağaç veri yapıları çok yavaş

  • Ağaç, verinin bilgi gösterimi değildir
  • Hashing yaklaşımı yalnızca noktalar eşit biçimde dağılmışsa uygundur
  • Rastgele algoritmalar, arama uzayı çok büyük olduğunda kullanışlıdır

• Neredeyse her şey oyun geliştirmedeki sezgisel yöntemlerle örtüşüyor

  • A*, Lee algoritması vb. harika
  • Görselleştirme olmadan flood fill yazmak resmen suç
  • Uzamsal hashing özellikle deneyimlerimle örtüşüyor

• "Uzamsal hash indeksleme > ağaç veri yapıları" bu alanda iyi olabilir, ama dünya çapında geçerli bir gerçek olarak kabul edilmemeli

  • Noktalar eşit dağılmıyorsa hash fonksiyonu kötü olabilir

• Üniversitede öğrendiğim anahtar kelimeleri hatırlıyorum

  • Gösterişli algoritmaları kullanma fırsatım hiç olmadı
  • Onun yerine UI bileşenleri ve REST API'leri inşa ettim

• 2D/3D uzamsal problemlerle doğrudan ilgilenmeyen biri olarak, görselleştirmenin değeri benim için en büyük ders

  • İnsanlar görselleri anlama ve analiz etmede çok iyidir
  • Problemin şeklini anlamak için olasılıksal ya da kaba kuvvet yöntemleri kullanma fikri önemlidir