【悲報】安易に基板配線自動化ツールを作ろうとした結果…開発者が語る7つの後悔

＞Point 8, the fast dismissal of Monte-Carlo method is a huge blunder.”
マジそれな。記事を読んだとき同じこと思ったわ。
MCは”現実的な”アルゴリズムで、遅いけど実装がめっちゃ簡単で、道を完全に間違ってないかチェックできるから信頼できる。

モンテカルロ法の直感的な説明がおもしろいよねー。ランダムにさまよって、もしかしたら無駄なことしてるかも、みたいな。

ああ、ごめん。「nested（ネストされた）」って言うべきだったね。（フランス語の”imbriqué(es)”からの正しい借用表現なんだけど）。

新しい単語を教えるのは全然悪くないよ。珍しくて嬉しいサプライズだった。

でも作者はシミュレーテッドアニーリングに触れてるから、ニューラルネットを試そうとしてなかったんじゃない？SAは勾配を計算しないし。

シミュレーテッドアニーリングは、回路設計における自動配線に使われてきた古典的なメタヒューリスティック手法の一つ。確率的なアプローチでNP困難な問題における局所最適解から抜け出すことができるから、初期の研究や一部の商用ツールで広く使われてた。最近の自動配線ツールはもっと高速で特殊なハイブリッド手法を使うことが多いけど、シミュレーテッドアニーリングは、学術研究やルーティングやフロアプランニング関連のプロトタイプのベンチマークとして使われてるよ。
ソース：昔、VLSI配線用のシミュレーテッドアニーリングを書いたことがある。あれはクールだった。

シミュレーテッドアニーリングは地図のラベル配置にめっちゃ使える。
例えば、POIにフラッグでラベルを付けるとして、フラッグが重ならないようにしたいし、ラベルはPOIの東西南北にしか置けないとする。
1．ラベルをランダム＊な方向に配置する。
2．重なりの総量を計算する。
3．ラベルの10％をランダム＊に移動する。
4．重なりの総量を再計算する。
重なりが改善されたら、変更を維持する。
悪化したら、元に戻す。
5．時々、悪化する変更をランダムに維持する。これがアニーリングの部分。これで局所最適解から抜け出すんだ。
＊ランダム性は100％である必要はない。2/3の確率で最近傍を賢く避け、1/3の確率でランダムに移動してみるとか。常に賢くしようとすると、局所最適解にハマりがち。

自動配線の素晴らしい議論だね。で、最後はこう締めくくる。
”エレクトロニクスの「雰囲気作り」を可能にする重要な要素。”
うっ。
ルーティング自体は簡単。難しいのは、新しいものを入れるために、すでにルーティングしたものを剥がすとき。組み合わせ最適化がマジでヤバくなる。
KiCADが昔持ってた自動配線が懐かしい。怪しいIPの関係で削除されちゃったんだよね（作者が自動配線会社で働いてたから）。それを取り戻したいユーザーへの反応は、「本物の男は自動配線なんて使わない」みたいな感じだった。[1]
[1]
https://forum.kicad.info/t/autorouting-and-autoplacement/185…

vibe-*って聞くと、マジで「うっ」ってなるよね。vibeコード系のアプリを推してる人を見ると毎回ちょっと萎えるけど、自分がコーディング始めた頃（ActionScriptのフォーラムでコードの修正をめっちゃ質問してた）を思い出すと、どんな分野でも手軽に始められるってすごい可能性あると思うんだよね。うちのautorouter（とか、後に続くやつ！）も、みんなが指導とか正式な教育なしで電子回路作れるようにしたいな。もちろん、プロにも役立つautorouterを目指してるよ！

彼らのautorouterがKiCadに組み込まれるといいね。でも、KiCadがautorouterに力を入れるのはマジ勘弁って思ってるクソジジイの一人としては、PCBのautorouterなんて全然使い物にならないゴミだと思ってるんだよね。VLSIのautorouterを見れば理由はわかる。VLSIのautorouterも使い物にならなかった。でも、VLSIはレイヤー数がめっちゃ増えて、垂直配線専用、水平配線専用、電源専用のレイヤーを作れるようになったんだよね。PCB autoroutingの根本的な問題は、PCBの方がVLSIチップよりも障害物が多いってこと。まず、部品自体が障害物であり、ボトルネックになる。次に、PCBのビアはほぼ全てのレイヤーを塞ぐけど、VLSIのビアは接続する2つのレイヤーしか塞がない。それに、PCBのビアは配線幅よりも大きいことが多い。おまけに、PCBのレイヤー数はVLSIよりもずっと少ない。4層（ほとんどのプロジェクトで、実質2層しか使わない）、2層（コスト重視）、6層（少数派）。つまり、PCB autoroutingはVLSI autoroutingよりもはるかに複雑なんだよ。

＞6層（少数派）
それはないと思うな。PCBの製造数で言えば、2層と4層がほとんどだろうけど（IoT製品とか、目覚まし時計とか）。それに、片面基板も多いし。趣味レベルのMCUなら、4層が最適。でも、そういうのは単純な回路か、配置がめっちゃシビアなものが多いんだよね。基板設計の労力のほとんどは6層以上のものに使われてる。簡単なスマートライトのPCBなら1日で終わるけど、BGAのSoC、DDR、PCIe、FPGAを搭載した基板は何ヶ月もかかるし、制約もめっちゃ複雑。コンデンサをピンの近くに置く、テストポイントを並べる、差動ペアのビアを対称にする、SMPSをノイズ源から遠ざける、インダクタのループを小さくする、とか、細かいルールがたくさんある。DRCを通っても動かない基板なんていくらでも作れる。特に、配線は配置よりも重要度が低い。PCBエンジニアが何やってるかって言うと、レイヤー数が多かったり、配置がキツかったり、高電圧回路だったりする。そして、配置を調整してる。キーボードとかDIP ICみたいな簡単な例は、お金も労力もかからないから参考にならない。

KiCadが6層基板に使われるようになってきたってことは、レベル上がってきてるのかな。それとも、Altiumが年間5500ドルもするから、プロでも高すぎるってこと？KiCadは趣味のツールだと思ってた。プロのツールみたいにライブラリが充実してないし。フットプリントとか3Dモデルはユーザー投稿で、ちゃんとテストされてない。フットプリントは手動で調整が必要だったりする。プロのツールはお金払って部品情報とかを入力してくれる人がいるけど、KiCadはそこら辺どうなの？

＞KiCadが6層基板に使われるようになってきたってことは
KiCadはリリースされるたびにAltiumとの差が小さくなってる。
＞プロのツールはお金払って部品情報とかを入力してくれる人がいるけど
PCBツールを使ってきた経験から言うと、そんなことないよ。基板設計者以外の人が管理してるライブラリは全部ダメだった。自分で使ったことない部品は、ほぼ確実に壊れてる。プロツール（ExpeditionとかAllegro）を使ってる人は、自分でライブラリを管理してる。Altiumがライブラリを暗号化してサブスクリプションにしたせいで自爆した話はもう飽きた。KiCadはAltiumの代わりにシェアをどんどん奪ってる。まだ足りない機能（内層の銅箔、フレキシブル基板のスタックアップ）もあるけど、リリースごとに減ってる。AutodeskのEagleの動きも、KiCadへの移行を加速させてる。

マジでみんなKiCadで6層以上の基板作ってるよ。俺の最新の設計は6層だけど、KiCadは余裕だった。CERNの12層の設計がデモとしてKiCadに付属してるくらいだし。どんなツールでも、ライブラリを修正する必要がないなんてことはない。普通の簡単な設計なら、KiCadのライブラリの99%は修正する必要がないけど、どんなツールでも全部に対応できるわけじゃない。ライブラリを修正する必要がないなんて嘘。どこから持ってきたフットプリントでも、必ずチェックするべき。KiCadには新しいライブラリチームがあって、5年前よりもずっと良くなってる。

作者です。みんな良いこと言ってるね。クレイジーな予想をさせて。
autoroutingは、今は良いデータセットがない画像変換の問題だと思う。もし巨大AI企業がautoroutingに注目して、物理的にシミュレートされた回路のデータセットを作ったら、autoroutingは解決すると思う。つまり、俺が今やってる発見的アルゴリズムも、みんながやってる努力も、将来的には必要なくなるってこと。autoroutingは、今の画像生成モデルよりも難しくないと思うんだよね。

PCBの大きな違いは、全ての配線がルールを守らないと動かないってこと。AIが生成したアートは欠陥があっても無視されるけど。PCBはそうはいかない。AIとDRCチェッカーを組み合わせて繰り返せばいいのかもしれないけど、複雑な回路でちゃんと動くかどうかはわからない。

Claudeが構文エラーのあるコードを出力しないように、画像変換モデルはDRCに準拠した画像を出力する！空間分割を使えば、DRC違反の問題を解決できるはず。最初から画像を生成するよりも、修正する方が簡単だと思う。

Claudeは動かないコードを出力することが多いけどね。DRCに合格するのは一つのこと（構文エラーがない）。実際に動くのは別のこと（コンパイルされて、望む結果になる）。しかも、単体テストでチェックすることもできない。

ロボットが大量の画像を見ただけでルーティングのアルゴリズムとかルールを学べるって言ってるの？
まあ、超大量のデータがあれば、たぶんね。
例えるなら、「ビーグルのリアルな肖像画が欲しい」のと「隣の家のビーグル、ボブのリアルな肖像画が欲しい」のとの違いみたいなもんかな。前者はビーグルってものの一般的なルールがあるから難しくないけど、後者はボブの写真をいっぱい持ってないと無理じゃん。
AIが今回のタスクをこなすには、本質的にビーグルの写真から物理法則（つまり”ボブっぽさ”）を学ばなきゃいけないんだよね。

＞物理法則を学ばなきゃいけない
名前忘れちゃったけど、最近AIと物理的に正しいモデリングを組み合わせたプロジェクトがあったはず。
追記：見つけた。Genesis project：https://x.com/zhou_xian_/status/1869511650782658846

賛成。
このデータセットを手に入れる一番いい方法は、ユニークなmicroCTスキャンを送ってくれる電子機器リサイクルセンターに補助金を出すことじゃないかな。トモグラフィー装置をリースしてさ。彼らの収益も増えるし、こっちは高品質な商用PCBデザインの巨大なデータセットが手に入る。

面白いアイデアだね。既存の設計で学習するって考えはなかったなー（IPがデリケートすぎて、十分なデータを得る方法が思いつかなかった）。
俺のアプローチはちょっと違ってて、ヒューリスティックに自動配線されたPCBの巨大な合成データセットを作って、AIに視覚的なトークンシステムと基本的なDRCコンプライアンスを学習させるべきだと思う。それから強化学習を使って、既存のデザインの改善に報酬を与える。そうすれば、新しいLLMモデルがリリースされるたびに合成データセットが改善されて、その後のLLMのトレーニングが楽になるのと同じように、データセットはどんどん良くなっていくはず。
このシステムをトレーニングするには、もっとたくさんのPCBが必要だってことをみんな過小評価してると思うんだよね。完璧な忠実度で1000万枚以上のPCBが必要になると思う。大規模な合成データ戦略が必要になるのは間違いない。

データを抽出するためのハードウェアにお金をかける前に、深センで買った方がずっと安くて早いよ。Apple製品は全部リバースエンジニアリングされてるし、ZXWみたいなアプリにはPCBレイヤーのスキャンデータがある。適当にググってみて。
https://www.diyfixtool.com/blogs/news/iphone-circuit-diagram…

この記事は重要な点を指摘してるねー特に視覚化とキャッシュの影響について。
いくつか細かい点とか大雑把な点もあるけど：
＞再帰的なアルゴリズムは深さ優先探索。候補／近傍をソートせずに探索するループは幅優先探索。
これについては何て言えばいいか分かんないなー間違ってるか、俺が何か勘違いしてるかのどっちかだ。深さ優先探索も幅優先探索も、反復的に書くことも再帰的に書くこともできるじゃん。本当の違いは、スタックのトップから次の候補を取り出すか、ボトムから取り出すかだよね。つまり、スタック（LIFO）を使うか、キュー（FIFO）を使うか。まあ、俺はCSじゃなくて数学を専攻したから、自分で確認してね。
＞これは、あらゆる種類の情報に基づいた探索（2Dグリッドだけじゃない！）の基礎として最適です。
Aは、目的のターゲットまでの「距離」を簡単に計算できる場合に、経路探索に役立つよね。でも、ほとんど静的なグラフ（道路ネットワークみたいな）で何度もクエリを実行する予定があるなら、コントラクションハイアラーキーみたいな前処理アルゴリズムを適用した方がいいかも。最適化したいけど、目標が分からない（巡回セールスマン問題とか）場合は、2-optみたいな別のローカルサーチヒューリスティックを使う方がいいかもしれない。
＞これら（AとBFS）の主な違いは、BFSはすべての隣接ノードを探索するのに対し、Aは目的地に近いノードの探索を優先することです。
これは確かに違いの一つだよね。でも、一番大きな違いを無視してる。Aは動的なアルゴリズムなんだよ。それによって、最短経路を見つけたと確信して早期に終了できる。BFSでは、グラフ全体を検索するまで確信できない可能性がある。それは膨大な量になるかもしれない。

＞recursive == DFS
人が再帰的にアルゴリズムを書くのは、スタックのトップとのやり取りに簡単にマッピングできるからなんだよね。ほとんどの言語では、外部スタックを持ち込むよりもそっちの方が簡単に表現できるから。だから、再帰的なものを見たら、幅優先探索よりも深さ優先探索に近いことが多い。君が指摘するように、それは絶対的なルールじゃないけど。

その通り。BFS、DFS、Aはすべて同じアルゴリズムで、未探索ノードを追跡するためのデータ構造が違うだけなんだよね。BFSはFIFOキュー、DFSはLIFOスタック、Aは優先度付きキュー（通常はヒープ）を使う。

A*は優先度付きキューの順序付けも重要だよね。ダイクストラのアルゴリズムはただの優先度付きキューを使ったBFSだけど、比較キーにヒューリスティックがないから、明らかに幅優先探索のままだ。

そうだね。A*は距離ヒューリスティックを優先度式に追加することで、ダイクストラのアルゴリズムを一般化したものだ。

いやいや、BFSでグラフ全体を検索する必要はないんだよ（始点と終点が反対の角にある場合は別だけど）。最初にノードに到達した時点で、それが最短経路だって100％確信できるじゃん。それこそがBFSが正しい結果を出すための基本的な不変条件の一つで、すべてのターゲットに到達したらすぐに終了できるってわけ。AとBFSの違いは、Aが2点間の最短経路を探すのに対し、BFSは単一の点からグラフ内のすべての点への最短経路を見つけるってこと。Aは、より弱い問いに答えることで個々のクエリを高速化してるんだ。問題によっては、何千ものA呼び出しを単一のBFSまたはDijkstra呼び出しに置き換えることで、大幅な高速化が可能になるよ。あと、BFSはすべてのエッジの長さが同じグラフでのみ機能するけど、A*は混合エッジ長をサポートしてるってのも重要な違いだね。これらは互換性があるわけじゃないんだ。リスト内の最小要素を見つけるのが、リストのソートの代わりにならないのと同じさ。

これは間違ってるか、少なくとも誤解を招く内容だよ。A*は点から点への検索に限定されず、点から点の集合への検索も問題なく扱えるんだ（考え方を変える必要があるかもしれないけどね）。これは「どれか1つへのパスが必要なだけ」の場合によく使われるけど、マージのおかげで、すべてへのパスが必要な場合でもより速いんだ。グラフ上のすべての点を訪れる（BFSがそうするように）のは、実際にはめったに必要とされないことなんだ（グリッドを捨てられる場合は別だけど。記事と同じように、グリッドを使いすぎる人が多いと思う）。BFSは可変エッジの重みでも問題なく動作するよ。次に訪れるノードのセットに対して、普通のキューの代わりに優先度付きキューを使用する必要があるだけさ。

優先度付きキューを使ったBFSはBFSとは呼ばないよ。Dijkstraのアルゴリズムって言うんだ。それって、「どれか1つが必要なだけ」の場合じゃなくて、集合内のすべての点への最短経路に対して正しく機能するって確信してる？逆方向に実行すると、ターゲットに最も近い点が最初に優先されると思うんだけど、それによってターゲット周辺の領域がすべて訪問済みとしてマークされ、集合内の他の点からのパスがブロックされる可能性があるんじゃないかな。それはグラフに別の点を追加して、それを集合内のすべての点に接続するのと同じことだよ。集合内のすべてへのパスに対して機能しない限り、DijkstraやBFSが答えるものよりも弱い結果にしかならないよ。必要ないなら使うなってこと。でも、僕が言いたいのは、必要なクエリに直接答える最も弱いアルゴリズムを使って、より特化された弱いアルゴリズムを繰り返し呼び出すことによって、より強力なアルゴリズムを構築することは、必ずしも最適ではないってこと。

A*は、one-to-manyの最短経路を解くように調整できるよ。すべてのターゲットに対するヒューリスティック関数をどのように集約するか注意する必要があるけどね[0]。また、Dijkstraと比較したパフォーマンスの向上は、たとえばソースがすべてのターゲットの「真ん中」にある場合など、多くのシナリオで実質的に消滅するだろうね。その場合、特定のターゲットに検索を偏らせるメリットはないんだ。普通にDijkstraで行うように、外側に展開する方がいいかもしれないね。道路ネットワークルーティング（こっちの方が得意なんだけど）では、contraction heirarchies [1]でグラフを事前処理し、クエリ時にRPhast [2]のような特殊なアルゴリズムを使用する方が、桁違いに優れているよ。
[0] https://www.semanticscholar.org/paper/Heuristic-search-for-o…
[1] https://en.wikipedia.org/wiki/Contraction_hierarchies
[2] https://www.microsoft.com/en-us/research/publication/faster-…

＞BFS works just fine with variable edge weights, you just have to use a priority queue instead of a plain queue for the next set of nodes to be visited.”
でも普通、優先度付きキューを使ってるならBFSって呼ばないよね？

＞first time you reach a node you know 100% that it is the shortest path”
後でコメントで指摘してるように、これはエッジの重みが均一な場合にのみ当てはまることだよ。一般的には、ソースからターゲットへの非常に長い直接エッジと、合計するとより小さくなる多数の短いエッジがあるような簡単な反例を思いつくことができるよね。

もし混合エッジがあるならBFSは使わないで、Dijkstraのアルゴリズムをヒープと一緒に使うのが好ましいね。それに、あなたが言った例でも問題ないよ。多くのエッジで構成された短いパスは、最初にヒープから取り出され、最初に訪問した時点で最短であることが保証されるから。もし実際のBFSを非均一なエッジで実行すると、a->b a->c b->d c->d d->eのようなものでは、最短経路すら生成されない可能性があるよ。それが機能すると想像できる唯一の方法は、単一のノードを2回訪問しないという要件を破棄して、最短経路を生成することだね。その時点で、それはBFSではまったくなくなるし、グラフ全体を訪問する必要があるだけでなく、グラフ全体を複数回訪問する必要があるだろうね。最悪の場合、パスの分岐チェーンのようなものがあれば指数関数的になるだろうね。

僕らは同意してるよ。これはどれも僕の元の主張と矛盾しないんだ。一般的な重み付きグラフでBFSを使うことはできるけど、最短経路であることを確認するには、グラフ全体を検索する必要があるだろうね。だから誰もそうしないんだ。

＞The QuadTree and every general-purpose tree data structure are insanely slow. Trees are not an informed representation of your data.
＞Any time you’re using a tree you’re ignoring an O(~1) hash algorithm for a more complicated O(log(N)) algorithm
これは非常に誤解を招くよ。ハッシュアプローチは、ポイントが均等に分散されていて、固定されたサブディビジョンに近い領域だけをクエリしたい場合には問題ないけど、それ以外の場合はO(1)がO(n)に劣化するだろうね。ツリーは、データの分布がわからない場合に有効な表現なんだ。ランダム化アルゴリズムについても同様だよ。検索スペースが数兆個のアイテムや可能性である場合はどうなるの？または、ヒューリスティクスがない場合は？ブルートフォースが使えなくて、賢いアルゴリズムも使えないなら、ランダム化アルゴリズムは救世主だよ。この特定のアプリケーションには必要ないかもしれないけど、安易な決めつけはしない方がいいね。

計測、計測、計測、計測。ケースバイケースだよ。でも、もっと真剣に言うと、ツリーベースのアルゴリズムは過大評価されがちで、人々は何十万もの要素を見ているときでも、定数係数が非常に重要であるときに、ビッグOの振る舞いについて考えすぎてしまう傾向があると思うんだ。データの局所性のようなものもそう。シーケンシャルスキャンで調べる方が、洗練された構造の簿記を処理するよりも速い場合もあるんだ。時にはね。僕が思うに、もっと良い議論は、操作の周りに小さなラッパーを作って、簡単なものを構築して、計測を通してそれを理解することだと思うな。最悪の場合、より良いパフォーマンスを試すために、異なる構造に対応するためにプログラム全体を書き換えることになるけど、僕の経験では、ファイル全体を最初から書き換えることは、かなりの数の改善点を無料で得られる傾向があるよ。

今のアーキテクチャだとシーケンシャルスキャンってマジで見過ごされがちだよね。データが小さくて要素数が最大1000個くらいなら、配列を単純にスキャンするのが速度とメモリ効率で最強だと思うよ。木構造とかもデフォルトとしてはアリだけどね。パフォーマンスをほぼリニアにスケールさせるには工夫が必要で、ここで多くのソフトウェアがコケるんだよね。使いやすさ的に。

記事の作者だよ。これ、記事に書く価値あったかも。たまに友達にアルゴリズムを見てもらうと、ソート関数を優先度付きキューに変えたりする提案をもらうんだけど（性能データを見ずに）、変化がなかったり、ちょっと悪くなることさえあったんだ！だから性能データが超重要なの。複雑なアルゴリズムの性能は直感に反することがあるし、性能の「落とし穴」のほとんどは単純なミスや再計算なんだよね。GTA5のロード時間が5秒も長くなるバグを、たまたまいた開発者が修正したみたいにね！

3Dだとocttreeがマジで効果的で速いことがわかったよ。実装によっては、木を再生成しなくてもアイテムを移動できるんだ。ポイント（2Dまたは3D）を保存して、近くのポイントをクエリする方法はまだ見つかってないけどね。kD treeは良いんだけど、固定されたセットの周りに構造を作るんじゃなくて、ポイントをどんどん追加したいんだ。

trieの考え方で、各ノードが最適な表現を選ぶのが良いと思う。トップレベルは通常グリッドを使うべきだけど、均一な密度の子供もグリッドを使える。グリッドのスケールは、空の子を最小限に抑えつつ、低密度の子供を最大化するように選ぶべき。低密度の子供には、ソートされていないアイテムの塊を格納するか、1つの軸（レンダリングに使用される最も外側の軸が望ましい）でソートする。外側のレベルが均一なら、子供はすべてこれになる（または空）。高密度の子供には、quadtree/octreeを使うか、再帰的に処理される不透明なオブジェクトとして扱う。これらはメモリアクセスが多いから嫌だけど、グリッドを使って外側の部分を処理したから、オーバーヘッドは小さい。実装が良ければ「近くの」クエリができるけど、多くの実装はイマイチ。可変にすると、リバランスを実装するか、固定された平面に固執する必要がある。

ほとんどが俺のゲーム開発の経験則と一致するな。JSを選んだことにも共感する。今、lispyなs式で動作するゲームMOD作成フレームワークを作ってるんだけど、創造的な反復時間を優先してる。A*とかLeeのアルゴリズムとかは全部クールだよね。可視化せずにfloodfillを書くなんてありえない。この記事を読んで、これまで読まなかったけど隣接するゲーム開発の知識が役に立つんじゃないかと思った。boidsルーターを考える人がいてもおかしくないよね。jumpflooding signed distance fieldは強力だと思う。特に空間ハッシュは経験と一致する。木構造が役に立ったことはほとんどない。例外は、lovecraftianテキストエディタかな。リアクティビティのためにtrieをたくさん使ってる。45,000語をコンパクトなイベント処理用のステートマシンに圧縮できるんだ。

boidsルーターを作るのはマジで楽しいアイデアだね（今後の記事のために取っておく！）。以前、再帰的なパターンautorouterについて書いたけど、これは小さな解空間を持つ場合にすごく有効なんだ（だから、従来の機械学習アルゴリズムで予測しやすい）。autoroutingには、まだ探求されていない面白い分野がたくさんあるんだ！！jumpflooding（高速で並列な距離場近似アルゴリズム）は知らなかったけど、間違いなく面白いかも、アドバイスありがとう！

木構造は、メモリとキャッシュが小さかった昔はもっと役に立ったと思う（固定グリッドとスマートなサイズ変更をベンチマークする必要があると思うけど、プリコンピュテーションにはまだ役立つと思う）。木構造は再帰的なアルゴリズムにも適しているけど、作者は反復的なアルゴリズムを選ぶ理由があるって言ってたから、このアドバイスは相乗効果があるね。（「再帰的」vs「非再帰的」っていうのは、ちょっと人工的な区別だってことを指摘しておく価値があるかも。「事前に用意された厳格なルールを持つアルゴリズムがフロー制御を処理するのか、それとも自分で処理するのか？」が本当の問題だ。もしパフォーマンスを重視するなら、自分で処理したいよね。実行環境が提供するスタックにランタイム状態が抽象化されると、簡単に変更できなくなるから邪魔になるんだ）。

95%以上の焦点をイテレーション回数を減らすことに当てるべき。だから言語なんてどうでもいいんだ。そして、遊び心があって表現力豊かな（インタプリタ型、抽象的、低速な）言語を使って、優れた高性能なアルゴリズムを開発したら…もしパフォーマンスがまだ重要なら、同じことを高性能な低レベル言語で書き直し、場合によってはアーキテクチャ固有のアセンブリも書く。numpy、pandas、OpenCV、TensorFlowが純粋なPythonで書かれていないのはそのためだ。代わりに、PythonにC++/assembly/CUDAなどで実装された処理を実行させてる。問題空間を探求して効率的なアルゴリズムを考え出すことを誇りに思っても（そしてブログに書いても）、純粋なPythonやJavascriptで書くことに固執したら、人気のある数値計算ライブラリにはならないだろう。今回のブログは面白いけど、純粋なJavascriptでHEVCエンコーダを1フレームあたり1日から3時間に短縮できなければ、同じような教訓は得られないだろう。

大学で覚えたキーワードがたくさんあるな。高度な有名なアルゴリズムを使いたかったよ。代わりに、UIコンポーネントとREST APIを構築してelasticsearchの結果を表示するだけだ。面白いことはすべてブラックボックスに隠されている。

LLMが幾何学的ヒューリスティクスをすべて記憶しているから、アルゴリズムはもっと楽しくなってるよね。多くのアルゴリズムはゲーム開発では避けられないから、タワーディフェンスゲームのようなものを作れば、古典的なアルゴリズムがたくさん出てくるよ！

LLMは記憶してないっぽいね。符号付き平面間の符号付き角度を計算させてみたら、Unityの実装をコピーするように指示することになったわ。

わかる。昔はKnuthのvol.1をいつも手元に置いてたけど、今はもうないな。

根本的な問題は、大学のカリキュラムと実際の求人市場のニーズが大きくミスマッチしてることと、企業が「大卒」をリスク回避とADA/差別禁止法を回避する手段として使ってることだと思う。CSの学位を細分化して、市場が本当に必要としてるCRUDアプリを作れる人を育成すべき。

これはいいね。2D/3D空間の問題に直接取り組んでない自分にとって、一番の収穫は視覚化の価値だね。人間は絵を把握して分析するのが得意だし。問題の形状を理解するために、確率的または総当たり法を使うのも良い考えだね。

＞2. 実装言語は関係ない
＞うちのautorouterをJavascriptで書いてるけど、最適化では反復回数を減らすことと、各反復の速度を上げることが重要。
一般的に、言語の選択が速度や反復回数に影響しないというのは間違いだと思う。

Big Oのアルゴリズム改善を追求するなら、言語実行速度の差は最適化としては時期尚早っていうのはもっともな意見だと思う。RustやアセンブラとJavascriptやVisualBasicの差は、指数や多項式の項を制御しようとしてるなら、ほとんど関係ない。

Big Oを追求するという前提が崩れると、議論は成り立たなくなる。キャッシュ/メモリ/ディスクアクセスが悪いと、定数項が大幅に悪化して、アルゴリズムが「悪い」方が実際にはうまくいくことがある。また、最悪のケースを気にしない場合でも、Oではなくオメガ、シータ、平均を参照しがちだ。

そうそう。それに、jsはイテレーションしやすいし、RustとかC#より寛容だし。特に探求してる場合は、それが大きなメリットになる。同じアルゴリズムなら、コンパイル言語の方が遅くなるのは当然。それが重要かどうかは場合によるけど、アルゴリズムを見つけるまでの時間も重要で、jsが役立つなら良い選択。

その後はどうするの？もっとパフォーマンスの高い言語に移行するか、JSに投資したことを受け入れるか？

どっちかだよね。FacebookはPHPに十分投資してたから、言語用の新しいVMをリリースしたし。Pythonでは、パフォーマンスが重要な部分をC（または最近ではRust）に抽出するのが一般的だし、Nodeでも同じことができる。あるいは、JITが十分に速ければ、価値がないかもしれない。

キャッシュを信じろ！ほとんどのウェブサイトが今Javascriptで書けるのは理由があんだよ。I／Oがボトルネックになる方が重要なんだって。アルゴリズムがキャッシュ可能なら（つまり各段階で部分的／空間的なキャッシュを持ってるなら！）、実装言語は大して重要じゃないはず。空間的にキャッシュできないNP困難な問題もあるけど、それは人間にとってもほぼ無理ゲーだから、PCBデザイナーは基板にスペース追加するかレイヤー増やすと思うよ。

この記事マジ最高。強調したい点が2つあるなー。
1．Autoroutingは特に視覚化に向いてる問題だってこと。全部の問題がそうじゃないけどね。根本的に実空間にあるリアルなものに関する問題なんだよ（おまけにほとんど2D平面に制約されてるから、コンピュータ画面で視覚化しやすい）。多くの難しくて面白い問題はそうじゃないから、視覚化に向いてないんだよね。
（…でも、一般的なアドバイスとして、「視覚化できる機会を探せ」ってのはアリ。人間の目と脳は、コンピュータが特別な調整されたソフトウェアなしではできないような、幅広いパターンのマッチングが超得意だから）。
2．Javascriptは、言語自体（特に実行時にデータ構造を反映できる能力）とエコシステムのおかげで、視覚化にめっちゃ向いてる。だからこの問題領域には最適な選択だったんだよ。もしC＋＋とかRustで「ちょっと視覚化してみるか」ってなったら、どれだけ大変か想像してみて。