kairo-gokko (17) 回路の分割 1



通電判定の説明で使った図を 2つ並べてみました。 たとえば 1枚の基板上(机の上とかでもいいですが)にこういうふうに並べて配置されている状況を想像してみます。

f:id:sonota88:20200308110730p:plain

エッジについて通電判定するためにダイクストラ法を使って最短距離を求めることにしましたが、このとき、左の島について判定する際に右の島の情報(エッジとノード)も使ってしまうと、無駄な処理が発生してしまいます。

というのも、左右の島同士は完全に切り離されていて、 右の島の状態によって左の島の挙動が変わることはないはずだからです(左右を逆にしても同じ)。

なので、これは分割統治するのが良いでしょうね。


今の時点ではパフォーマンス上の問題(処理落ちなど)はまだ出ていませんから、 その点では先回り気味だと思います。 それよりも、分割統治により扱うデータの範囲・量が狭まって一度に考慮すべき事項が減ることの方がありがたい感じです。


修正の前に名前を整理します。

とりあえず、記事上では、区別する必要がある場合は次のように呼ぶことにします。

  • 子回路: 上記で「島」と呼んでいたものに相当。
  • 回路全体: 上記で「基板」と呼んでいたものに相当。1個以上の子回路を含む。

それはいいとしてクラス名をどうするか……いろいろ悩みましたが *1、ひとまず下記で進めます。

  • ChildCircuit: 子回路に相当
  • Circuit: 回路全体に相当

ということは、まずは今までの Circuit クラスを ChildCircuit にリネームして、 変数名やファイル名も合わせて修正して……今回は力尽きたのでここまで。



*1:ChildCircuit は長くて嫌だけど回路全体は CircuitSet とか WholeCircuit ではなく Circuit と呼びたいだとか、これまでの説明との連続性がとか、いっそのこと board, island ではどうかとか……