- tscircuit向けのオープンソースPCB autorouterを約1年開発した経験から、A*、可視化、空間分割、キャッシュのように探索問題を小さくする設計こそが性能の核心であることが分かった
- 最適化の焦点は、言語や1回の反復の速度よりも反復回数の削減にあり、JavaScriptであっても、より賢くキャッシュしやすいアルゴリズムなら低レベル実装より速くなり得る
- 空間検索では、QuadTreeのような汎用ツリーよりもSpatial Hash Indexのほうが単純で高速な場合があるが、セルサイズの選択を誤ると検索ごとに高い固定コストが発生する
- 複雑なautorouterパイプラインでは、段階ごとの入力・出力を可視化し、反復過程をアニメーションで確認する必要がある。再帰関数とMonte Carlo方式は、デバッグ・最適化・決定性の面で不利
- A*はWeighted A*のGreedy Multiplierにより最適性を一部犠牲にして速度を大きく高められ、各段階は後続段階が解きやすい状態を作るように失敗確率を下げるべきである
A*を基本的な探索ツールにする
- A*は2Dグリッド専用のアルゴリズムではなく、さまざまな形の**情報付き探索（informed search）**に使える基盤アルゴリズムである
- BFSは隣接ノードをすべて探索するが、A*は目的地により近いノードを優先して探索する
- グラフ外部の距離指標を使うため、情報付き探索に該当する
- 再帰アルゴリズムは深さ優先探索（DFS）に近く、候補や近傍をソートせずに探索するループはBFSに近い
- 既存のBFSやDFS形式のコードをA*に変えると、大きな性能向上が得られることが多い
- autorouterでは複数レベルのA*を使い、問題に合ったハイパーパラメータを見つける
- 各autorouter設定を候補として実行する
- 良いコストでルーティングに成功し始めた設定に、より多くの反復を割り当てる
- 距離コストと反復コストを併せてペナルティとして使うmeta-A*の形である
言語よりアルゴリズムが重要
- tscircuit autorouterはJavaScriptで書かれており、性能の議論では言語が最初に指摘されることが多い
- アルゴリズム最適化は大きく2つの軸に分かれる
- 必要な反復回数を減らし、アルゴリズムをより賢くする
- 各反復の実行速度を上げる
- 1回の反復速度の改善に過度に集中すると、間違ったアプローチを速く実行するだけに終わりかねない
- 例えば、重なり検査のためにすべてをグリッド化する方式は、言語に関係なく遅くなり得る
- 低レベルで最適化されたアセンブリの単純なアルゴリズムより、JavaScriptの賢いアルゴリズムのほうが速い場合がある
- 開発時間の95%は反復回数を減らすことに使うのがよく、最も賢くキャッシュ可能なアルゴリズムに早く到達させてくれる言語が良い選択である
Spatial Hash Indexはツリーより優れている場合がある
- 多次元空間の最適化ではQuadTreeがよく登場するが、汎用ツリー構造は遅いことがある
- QuadTreeは2D・3D空間で近いオブジェクト検索を
O(N)からO(log(N))へ減らすデータ構造として知られているが、ツリーはデータに対する情報付き表現ではない
- Spatial Hash Indexはオブジェクト自体ではなく、オブジェクトの位置をハッシュ化してセルまたは近いもののバケットに保存する
- このアプローチは、HashSetやHashMapのような高速なハッシュベースのアクセスを空間データに適用する方式である
- 空間ハッシュがあまり一般的でない理由は、適切なセルサイズを選ぶ必要があるためである
- セルサイズの調整を誤ると、検索ごとに高い固定コストが発生する
- 実際には、妥当なセルサイズを選ぶことはそれほど難しくないと見ている
空間分割とキャッシュが性能を変える
- iPhone内部のような回路基板には、およそ10,000〜20,000本のトレースがある場合があり、最高水準のEDAツールを使ってもチームが数か月かけてルーティングすることがある
- autorouting問題で重要な単純なアイデアは、すでにルーティング済みのものは以前にもルーティングされたことがある、という点である
- ゲーム開発者はナビゲーションメッシュを事前に焼き込み、LLMは検索のためにインターネットを重みへ圧縮する
- 次世代のautorouterは問題を空間的に分割し、すでに解かれた解を含む大きなキャッシュを活用できる
- autorouting問題の99%がキャッシュ内で事前に解かれているなら、アルゴリズム自体の速度はそれほど重要ではなくなる
- 現在の多くのアルゴリズムは、キャッシュ再利用性と空間分割に十分集中していない
- 保存とキャッシュのコストは計算速度の向上よりも速く下がっているように見え、autorouterを50%速くするために1GBのキャッシュを使うことは大きな問題ではないと考えている
可視化とプロファイリングで問題を直接見る
- 問題に対する可視化がなければ解決できない、という原則が重要である
- 数字だけを見る方式ではデバッグが難しく、小さなサブ問題ごとに可視化を作ると問題をはるかに速く理解できる
- autorouter開発では、問題解決を可視化から始めることも多い
- 45度経路を見つけるサブアルゴリズムも可視化しており、これはautorouterのほぼ最後の段階であるPath Simplification Phaseで使われる
- JavaScriptのプロファイリングツールは、各コード行で消費した合計時間をミリ秒単位で表示する
- ブラウザでJavaScriptを実行し、Performanceタブを開けばよい
- flame chartとメモリ使用量の機能も提供される
- 関連する短い動画: youtube short
再帰とMonte Carloを避ける
- 再帰関数は性能重視のコードでは避けるほうがよい
- ほぼ常に同期的に動作するため、アニメーションのために途中で止めにくい
- 本質的にDFSであり、A*へ簡単には変えにくい
- 反復回数の追跡が容易ではない
- 再帰関数では可変性が不自然だが、性能には可変性が重要な場合がある
- 反復ベースの実装は
visitedNodes集合を維持し、探索前にノードを確認できるため、より速い場合がある
- Monte Carloアルゴリズムはランダム性によって解に近づくが、決定的でないためデバッグが難しく、ヒューリスティックに比べて最適な場合はほとんどないと見ている
- 候補をどう評価するかは分かるが、解に到達する方法が分からないとき、Monte Carlo方式は直感を得る助けになることがある
- コスト関数に近いものができたら、Monte CarloやSimulated Annealingのようなランダム手法より良い方式を使うべきである
- ローカルミニマムに敏感なら、ハイパーパラメータや、より複雑なコスト関数を検討できる
- PCB設計者が回路基板上にランダムに線を引かないのと同じように、このドメインではより良いヒューリスティックを見つけられると考えている
中間アルゴリズムは同じ座標系に置く
- autorouterは現在、13段階と約20個のサブアルゴリズムからなるパイプラインである
- 空間分割の判断や、独立してautorouteされた領域境界の経路単純化といった作業で反復回数を測定する
- 各段階の入力と出力を重ねて可視化すると、現在解いている問題の文脈を理解できる
- downstream段階、特にhigh density routing段階の問題は、前段階の出力を改善することで解決されることが多い
- サブアルゴリズムを作るとき、問題を最も単純な形に分離し、座標を
(0, 0)周辺へ正規化したくなる誘惑がある
- 正規化や複雑な変換は、初期段階の結果が後続段階に与える影響を素早く見ることを難しくする場合がある
- アルゴリズム全体のライフサイクルで座標空間を一貫して維持する方式が有利である
- 各段階を順番に見て拡大すると、失敗したDesign Rule Checkの原因となった段階を見つける助けになる
反復アニメーションとグリッド回避
- 反復回数を減らすことが重要なので、アルゴリズムの反復をアニメーションで見ると、無駄な探索を直感的に把握できる
- アニメーションは特にGreedy Multiplierを調整するときに役立つ
- ある単純なトレースが失敗すべき状況で、すぐ失敗せず外側へ向かって際限なく解決を試みる事例は、アニメーションなしでは把握しにくかった
- 2本のトレースAとBが重なるかどうかを判断する方法は大きく2つある
- AとBの各セグメントを見て交差を確認する
- Bが存在するグリッドをマークしたうえで、Aが通るグリッドにBがあるか確認する
- グリッド方式は簡単に1000倍遅くなり得る
- 高速なベクトル数学を使えば、単一グリッドセル確認のためのメモリアクセスより、2セグメントの交差判定のためのdot productのほうが速い場合がある
- 厳密には、適切なクリアランスを保証するためにセグメント間距離計算を使う必要があり、これは交差判定より少し複雑だが、大きくは変わらない
失敗確率とWeighted A*
- 空間分割段階では、各段階の解決失敗確率を先行指標として測定できる
- Unravel Autorouterは主要なパイプライン段階ごとに各Capacity Nodeの失敗確率を追跡する
- 各段階は隣接ノードの再構成や再ルーティングを通じて、失敗確率を下げることに集中する
- 失敗確率は実際に測定でき、アルゴリズムが変われば予測も改善できる
- 各段階は後続段階の失敗可能性を下げる方向に動作できる
- あまりに多くの制約を一度に入れるより、解決可能性を優先するほうがよい
- いったんボードが解ければ、最初から最適解を生成するより既存の解を扱うほうが簡単な場合が多い
Greedy Multiplierで速度と最適性をトレードオフする
- 基本のA*は最適解を保証するが、速度をより重視するなら
f(n)を少し変えてWeighted A*を使える
- 通常のA*:
f(n) = g(n) + h(n)
- Weighted A*:
f(n) = g(n) + w * h(n)
- Weighted A*はより貪欲に問題を解き、一般にずっと高速に動作する
- この方式は最適性を一部犠牲にする代わりに、A*の性能を大きく高めるGreedy Multiplierとして機能する
- Weighted A*とその他のA*派生形については、weighted A* and other A* variants hereでさらに見られる
- ゲーム開発者はautorouting開発者と似た問題を多く扱うため、関連研究を探すときはゲーム開発の論文を調べるとよい
公開予定のautorouter
- tscircuit向けautorouterはリリースに近づいている
- 成果物はMITライセンスのオープンソースとして提供される
- autoroutingの解決は物理世界のイノベーションを大きく切り開くことができ、電子製品の「vibe-building」を可能にする重要なピースだと考えている
- 関連アカウント: follow me on twitter.
1件のコメント
Hacker Newsの意見
概してオートルーターは信用していないし、この分野に入ってくるAIツールについても同様だが、eCADでレイアウトの一部を素早く作る大きな機会があることは否定しにくい
完全自動のツールよりは、共同制作型ツールのほうを使うと思う。設計初期には部品配置が確定していないことが多く、配置が配線に大きく影響するからだ。ページ上では、配置がアルゴリズムに含まれているのかは分からなかった。すでにpush-and-shoveや、時々オートコンプリートのようなツールは使っている
この市場は小さく、ツールは断片化しており、既存企業は動きの鈍い巨大企業で、ユーザーはこだわりの強い熱心な人たちだ。KiCadは絶対に手放せない。オートルーターがJavaScriptで書かれていること自体には大きな意見はないが、CADベンダーやオープンソースツールのエコシステムに接続する計画なのか、それともまた別の新しいエコシステムへ人々を引き込もうとしているのかが気になる
キャッシュフレンドリーであれば、部品を動かして別のレイアウトを試す速度がずっと速くなる。JavaScriptは今ではQuickJSやProfforのような小さなランタイムまであり、かなり移植性が高く、ローカルで実行して巨大なキャッシュを直接作れると見ている
EDAにおけるロックインとエコシステムの断片化は誰もが懸念すべきことだが、tscircuitとこのオートルーターはMITの寛容なライセンスの技術なので、EDAでは珍しく、あらゆるものと相互運用できるように作れる
フットプリント、配置、制約、手動配線済みのネットを固定してしまえば、非常に素早く反復できた
Cadenceが90年代にSPECCTRAを買収して以来、PCBオートルーターはかなり停滞していたので、誰かがこの分野に改めて取り組むのは喜ばしい。SPECCTRAを作った人たちは、記憶ではVLSIのほうへ行って戻ってこなかったし、名声とお金はそちらにあったようだ。しばらくは特許の地雷原だったのかもしれないし、今もそうかもしれない
自動配置は当時もまったく扱いにくい問題で、今もそう見えるが、生成AIアプローチはうまく合う可能性がある。良い生成AIベースの一次部品配置は全体の時間を減らせる。最大の問題は、完璧でなくても十分に良い場合があることを、頑固な人たちに納得させることだ
コードとしての回路図をやろうとする試みは少し不思議に感じる。バックエンド形式としてうまくいくなら良いし、特にjitx方面のように、アプリノートやデータシートレベルの設計ルールを部品モデルへエンコードする進展は良さそうに見える。商用設計に必要なレベルで全データシートを読む作業は思ったよりはるかに多く、ジュニアエンジニアにその過程を身につけさせるのも同様なので、自動化には利点がある
ただし、それらのアプローチは回路図をレイアウト用のデータ入力、いわばソースコードと見る考えに根ざしているようだ。回路図は、EDA製品群がインストールされていない人でもアクセスできるべき、慎重に発展してきた視覚言語を持つ設計文書でもある。Adafruit/Sparkfun/Shenzhenスタイルのように、明示的な配線を最小限にした回路図を読み解いて学んだ人たちは、良い回路図の価値をよく分からないかもしれない
もう一つは、類推に頼りすぎてPCBレベル設計をVLSI設計のようにしようとする傾向だ。まったく不可能だとは思わない。DRCと検証ツールがより良くなれば、部品レベル設計もVLSIに近づけるかもしれない。だが、設計、EDA/CAM/シミュレーション、検証、製造業者、組立業者、部品ベンダー、規制・認証機関の間の結合があまりに緩いため、このうち一角だけでもきちんとやり遂げられれば大きな成果だ
最近はインピーダンス制御UHF設計を、ドメイン特化のシミュレーションツールと併用して進める流れだ。そのため、重要なトレースを先に手動で配線し、アイランドポールを作り、最後に電源接続を処理する
KiCadのレイアウトはないよりは少しましだが、さらにもう一つ中途半端なシミュレーションツールにしようとするのは滑稽に見える
データベース対応とoutjob機能だ。それ以外は、採用と、ユーザーがこの機能をどう活用するかの問題に近く、データベースには通常、データ整理に関する社内官僚主義がより多く付いてくる
レイアウトを高速化するワークフローという観点では、KiCadもすでにある程度その方向へ進んでいるのではないかと思う。例えば7.0あたりで入った「トレース自動補完」機能がある。pcbnewではショートカットがFだったと思うが、現在配置中のトラックのトレースを敷いてくれる。「トラックの反対側から配線」ショートカットEと一緒に使うと、異なる2つのボールアウトグリッド間で作業するときに生産性が大きく上がる
バージョン9ではバスや複数のトラックをドラッグできるようになり、この流れがさらに速くなる可能性がある
正直、満足できる配置まで持っていけて、オートルーターに配線位置の制約を与えられるなら、設計の相当部分はオートルーターに任せられそうだ。例えば昨年、NXP iMX8MPとeMMCを使うボードをやったが、プロセッサ周辺のボールアウトがeMMCのボールアウトとうまく合っていたので、チップを合わせて置いて線を引くだけで済んだ。データバスを最上位レイヤーに維持せよ、ということさえ分かっていれば、オートルーターは10分かかった作業を数秒で終えただろう
オートルータープロジェクトには成功基準の問題がある。ボードのすべてを処理できて初めて「完成」だと考えているようだが、実務の電気エンジニアとしてはそれを望んでいない。設計の小さな塊を一つずつ一緒に処理し、レビューする時間を与えてから次の塊へ進むオートルーターが欲しい
レイヤーをまたぐ制約まで与えられるなら強力だ。例えば「D0-7という名前のすべてのネットを1番と3番レイヤーに維持し、長さを互いに5mm以内に合わせ、D0を長さの基準にせよ」といった具合だ。これができればDRAMの長さチューニングを解決したも同然で、はるかに広い複雑度の設計が一般ユーザーにも可能になる
時間があれば、どういう意味かデモで示したい
8番でモンテカルロ法を早々に退けたのは大きな間違いだと思う
モンテカルロの核心は、精度と速度をトレードオフできる点にある。アルゴリズムを長く走らせるほど、より正確になる
さらに興味深いのは、その対偶もよく使えるという点だ。非常に不正確な結果を非常に高速に得られる。すべての経路を探索する代わりに、ランダムに選んだ経路を1つだけ探索する、といった具合だ
この方式は、アルゴリズムの最も内側のネストしたループに入れたときに真価を発揮する。たとえば自動配線を学ぶニューラルネットワークを学習させるなら、外側のループはニューラルネットワークのパラメータを更新し、内側のループはグラフを通る経路を計算する
モンテカルロを使えば、バイアスがないなら、精度を制御するこの内側のループを1回の反復にまで減らせる。分散が大きくなって外側のループは遅くなるだろうが、機械学習は「理論上は」学習できる
そのため、チェスや囲碁のように直感的に正しい判断を選ぶポリシーを作れる。AlphaGo Zero、AlphaChess Zero、AlphaRouter Zero のようなモンテカルロ木探索の変種では、探索部分がなくても、ニューラルネットワークのパラメータとしてエンコードされた巨大なキャッシュにより、学習後はニューラルネットワークを1回通すだけ、つまり定数時間で最善の推定経路を計算できる。この定数は、パラメータを増やすか、より長く学習させることで、メモリと速度を簡単にトレードオフできる
MCは現実感覚をつかませてくれるアルゴリズムだ。遅いが、ほぼ常に実装は非常に単純で、完全に見当違いの方向へ外れていないかを非常に高い確信で再確認するのに信頼できる
自動配線についての優れた議論なのに、最後が「電子製品の vibe-building を可能にする中核ピース」で終わっていて少しつらかった
配線そのものは簡単だ。新しい配線を入れるために、すでに敷いたものを剥がさなければならない瞬間に複雑になり、組合せ爆発が襲ってくる
以前 KiCad にあった自動配線器が懐かしい。あいまいな知的財産権上の理由で外されたが、作者が自動配線の会社で働いたことがあったためだ。戻してほしいというユーザーには、「本物の男は自動配線器を使わない」といった反応があった
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
この自動配線器と、それに続く他のツールによって、多くの地図や正式な教育なしに人々が最初の電子製品をリリースできるようになることを願っている
もちろん、優れた自動配線器は専門家にとっても有用であるべきなので、その点でも役立ってほしい
ただし、KiCad が自動配線器に力を入れるのはあまり見たくない、面倒な古参の一人として言うと、PCB自動配線器は常に厄介で、まともに動かない
なぜそうなのかは、VLSI自動配線器を見れば分かる。VLSI自動配線器も厄介で、まともに動かなかった。その後、VLSIには非常に多くのレイヤーが使われるようになり、垂直配線用レイヤー、水平配線用レイヤー、電源用レイヤーを別々に割り当てたうえで、さらにグローバルな垂直接続、グローバルな水平接続、グローバルな電源用レイヤーをいくつか持てるようになった
PCB自動配線の根本問題は、PCBにはVLSIチップよりも障害物がはるかに多いことだ。第一に、部品そのものが障害物でありボトルネックでもある。第二に、PCBのビアはほぼ常に基板のすべてのレイヤーをふさぐが、VLSIのビアは接続される2つのレイヤーだけをふさぐ。第三に、PCBのビアはたいてい配線金属の幅より大きい。第四に、PCBで使うレイヤー数はVLSIよりはるかに少ない。一般的なのは4層で、そのうち通常の配線にまともに使えるのは2つだけだし、コストのために2層も多く、自動配線はさらに難しく、6層はごく少数だ
結果として、PCB自動配線はVLSI自動配線よりもはるかに複雑な作業になる
記事で可視化とキャッシュ効果を特に重要に扱っている点は良い
ただし、いくつか引っかかる点がある。「再帰アルゴリズムは深さ優先探索で、候補や隣接ノードをソートせずに探索するループは幅優先探索」という話は間違っているか、直感を取り違えているように思う。DFS と BFS はどちらもループでも再帰でも書けるし、実際の違いは次の候補をスタックの上から取り出すか下から取り出すか、つまりスタック（FILO）を使うかキュー（FIFO）を使うかにある
A* がすべての情報に基づく探索の最高の基盤だという話にも文脈が必要。目的地までの計算しやすい「距離」の概念があり、同じグラフでクエリを数回だけ実行する場合の経路探索には有用。道路網のようにほぼ静的なグラフで多数のクエリを実行するつもりなら、contraction hierarchy のような前処理アルゴリズムの方がよい場合がある。巡回セールスマン問題のように最適化はするが目標が決まっていない場合は、2-opt のような別の局所探索ヒューリスティックの方がよい場合もある
「BFS はすべての隣接ノードを探索し、A* は目的地に近いノードを優先する」というのは違いではあるが、より大きな違いは A* が動的アルゴリズムだという点。だから最短経路を見つけたと確信して早期終了できる。BFS はグラフ全体を探索するまで確信できないこともあり、グラフが巨大な場合もある
たいていの言語では、外部スタックを持ち出して考えるより、そのように表現する方が簡単。だから実際のコードで再帰を見たら DFS に近い可能性が高いが、厳密な規則ではない
BFS は FIFO キュー、DFS は LIFO スタック、A* は通常ヒープで実装した優先度付きキューを使う
これが BFS が正しい結果を出すための基本的な不変条件の一つなので、すべての目標に到達したら早期終了できる
A* と BFS の違いは、BFS が 2 点間の最短経路ではなく、単一の始点からグラフ上のすべての点への最短経路を求める点にある。A* はより弱い問いに答える代わりに、個別クエリを高速化するトレードオフ
問題構造が許すなら、何千回もの A* 呼び出しを 1 回の BFS や Dijkstra 呼び出しに置き換えるだけでも大きな高速化が得られる。また重要な違いは、BFS はすべての辺の長さが同じグラフでしか動作せず、A* は異なる辺長をサポートする点。両者は相互に置き換えられるものではなく、リスト内の最小要素を見つけることがリストのソートの代替にならないのと同じ
「四分木とすべての汎用木データ構造は猛烈に遅い」「木はデータに関する情報を含んだ表現ではない」「木を使うたびに O(~1) のハッシュアルゴリズムの代わりに、より複雑な O(log N) アルゴリズムを使っている」という話は、かなり見当違い
ハッシュを使うアプローチは、点が均等に分布していて、選んだ固定分割に近い領域だけを問い合わせる場合には問題ない。そうでなければ、その O(1) は O(n) に崩れ得る
データ分布が分からないとき、木は情報を含んだ表現になる
ランダム化アルゴリズムも似ている。探索空間が数兆以上の項目や可能性で構成されていたらどうするのか。ヒューリスティックもないなら？ 総当たりもできず、賢いアルゴリズムも使えない状況では、ランダム化アルゴリズムが救いになる
この特定のアプリケーションには必要ないかもしれないが、一般化した断定は避けた方がよい
より真面目に言うと、木ベースのアルゴリズムは過大評価されがちで、人々はビッグオーの挙動にこだわりすぎて、数十万要素でも定数係数が非常に重要だという点を忘れているように思う。データ局所性なども同じ。より複雑な構造の帳簿管理をするより、単純に順次スキャンでなめる方が速いこともある
全体としては、操作を小さなラッパーで包み、簡単な実装から作って、計測で判断する方がよい
最悪の場合、より良い性能を狙って別の構造に合わせてプログラム全体を書き直す必要があるが、経験上、ファイルを最初から書き直すと、おまけの改善もかなり付いてくる
まだ 2D や 3D の点を保存して近傍点を問い合わせる満足のいく方法は見つけていない。kD 木は良いが、固定された集合を基に構造を作るのではなく、進めながら点を追加したい
ほぼすべての内容が、自分のゲーム開発ヒューリスティックと一致している。JavaScriptを選んだのも理解できる
今、Lisp式のS式で動作するゲームModdingフレームワークを作っているところだが、創造的な反復にかかる時間を減らす最適化が何より重要だと分かってきた
A*やLeeアルゴリズムのようなものはどれも素晴らしい。どんな種類のflood fillであれ、可視化も一緒に作らないのは犯罪に近い。ドーパミンをあまりにも無駄にしている
この記事を見て、自分は読んでいないがゲーム開発周辺にある手法が、こうした問題にも役立つのか気になった。boidsルーターがかなり面白そうだと思ったのは、きっと自分が初めてではないはずだ。もう少し真面目に言うと、jump floodingベースの符号付き距離場はかなり力を発揮できそうだ
特に空間ハッシュについての内容は自分の経験と一致する。ほぼ20年の間、ツリー構造が費やした時間に見合う価値を持っていた例はあまり見たことがない。例外が一つあって、自分が作ったラブクラフト風テキストエディタでは、リアクティブ処理にtrieをかなり多用している。45,000語をイベント処理用の圧縮状態機械にするには良い方法だった
以前、再帰パターンのオートルーターについて書いたことがあるが、解空間が小さいので既存の機械学習アルゴリズムで予測しやすい部類だ。自動配線には、まだ探検されていない興味深い領域が非常に多い
jump floodingは知らなかった。他の人向けに補足すると、距離場を高速に並列近似するアルゴリズムだ。確かに面白くなり得るし、教えてくれてありがとう
ツリーは再帰アルゴリズムにもよく合うし、筆者は反復アルゴリズムを再帰より選ぶ理由があると言っていたので、これらの助言は互いにかみ合っている
大きく見ると、「再帰」と「非再帰」の区別はいくらか人工的だ。本当の問いは「厳格なルールを持つ事前に組まれたアルゴリズムがフロー制御を担うのか、それとも自分が担うのか」だ。性能をかなり気にするなら答えは自分で担う側であるべきで、実行状態が実行環境の提供するスタックの中に抽象化され、実行時に妙に変えにくくなると邪魔になり始める
「集中の95%は反復回数を減らすことに使うべきだ。だから言語は重要ではない」という話はある程度正しいが、遊び心があり表現力の高いインタプリタ型・抽象的・低速な言語で優れた高性能アルゴリズムを作った後でも性能が重要なら、同じものを性能の良い低レベル言語で書き直し、必要ならアーキテクチャ別のアセンブリまで書けばよい
numpy、pandas、OpenCV、TensorFlowが純粋なPythonで書かれていないのには理由がある。Pythonは高性能なC++/アセンブリ/CUDAなどで実装された処理に指示を出す役割を担っている
問題空間を探索し、効率的なアルゴリズムを見つけてブログに書いたことにどれほど誇りがあっても、純粋なPythonやJavaScriptだけで書くことに固執していたなら、人気の数値計算ライブラリにはなりにくかったはずだ
面白い記事ではあるが、筆者のアルゴリズム上の洞察によって純粋JavaScriptのHEVCエンコーダが1フレームあたり1日から3時間に短縮されたのだとしたら、同じ結論にはなりにくかったと思う
大学時代に覚えていたキーワードがたくさん出てくる。有名でかっこいいアルゴリズムを使う機会があればいいのに
実際にはUIコンポーネントとREST APIを作ってElasticsearchの結果を表示する仕事ばかりしている。面白いものは全部ブラックボックスの中に埋もれている
ゲーム開発では避けて通れないアルゴリズムが多いので、アルゴリズムを作りたいならタワーディフェンスのようなものを作ってみると、古典的アルゴリズムをたくさん扱うことになる
少なくとも現在のコンピュータサイエンス学位は分割すべきだと思う。かっこいい数学寄りの部分は別の学位にすべきで、AI関連の新しい学位と統合されることもあり得る。データベースとネットワーク理論も別学位にすべきで、低レベルアセンブリも同様だ。電子部品、NANDゲート、ブール代数などがどのように動作するかは、電子工学に移すのが適切だ
市場が最も必要としている、CRUDアプリを量産できる人材については、学問的知識が必須だと言い張るなら別学位にするか、職業教育側へ移すべきだ
同時に、採用要件のゲートキーピングも法律で扱うべきだ。実際の職務とほとんど関係のない学位を要求できないようにすべきだ。今は若者に人生の何年も浪費させ、5桁から6桁ドルの借金を負わせ、ただ企業が人をふるいにかけやすくしているだけだ
2D/3D空間問題を直接扱っているわけではないが、最大の教訓は可視化の価値だ
人間は図を理解し分析するのが非常に得意だ。もう一つは、確率的手法や総当たりで問題の形をまず把握したうえで、純粋な理論的理解だけでなく、それに合わせてより良い方法を選ぶというアイデアだ
「実装言語は重要ではない」という話はこの分野では正しいのかもしれないが、一般的なソフトウェア工学に適用すると、言語選択が速度や必要な反復回数に影響しないという仮定は大きく間違っていると思う
指数項や多項式項を制御しようとしている段階なら、Rustやハードコードしたアセンブリと、JavaScriptやVisual Basicの差はかなり無意味になり得る