Skip to content

Instantly share code, notes, and snippets.

@t3t5u
Last active August 29, 2015 14:17
Show Gist options
  • Save t3t5u/2c626eacc351021c5563 to your computer and use it in GitHub Desktop.
Save t3t5u/2c626eacc351021c5563 to your computer and use it in GitHub Desktop.
6.4 物理学者の方法

6.4 物理学者の方法

銀行家の方法と同様に物理学者の方法でも、累積した貯蓄ではなく累積した負債を使うことができる。 伝統的な物理学者の方法では、ポテンシャル関数Φは累積した貯蓄の下限を表す。 貯蓄の代わりに負債を使うには、それぞれのオブジェクトを、累積した負債の上限(少なくとも、累積した負債のうちのオブジェクトの部分の上限)を表すポテンシャルにマップする関数Ψで、関数Φを置き換える。 大ざっぱに言えば、ある演算の償却されるコストとは、その演算の完全なコスト(つまり共有されるコストと共有されないコスト)からポテンシャルの変化を減算したものである。 ある演算の完全なコストを算出する簡単な方法は、全ての計算が正格であると見せ掛けることであった。

累積した負債の変化は、全てポテンシャルの変化に反映される。 ある演算が共有されるコストを全く支払わないなら、そのポテンシャルの変化は共有されるコストに等しくなるので、その演算の償却されるコストは共有されないコストに等しくなる。 一方で、ある演算が、共有されるコストあるいは先行する演算の共有されるコストの一部を支払うなら、そのポテンシャルの変化は共有されるコストよりも小さくなる(つまり累積した負債の増加は共有されるコストよりも小さくなる)ので、その演算の償却されるコストは共有されないコストよりも大きくなる。 しかし、ある演算の償却されるコストが共有されないコストよりも小さくなることはできないので、そのポテンシャルの変化が共有されるコストよりも大きくなることは許されない。

銀行家の方法と関連付けることで、物理学者の方法を正当化することができる。 銀行家の方法において、ある演算の償却されるコストとは、その共有されないコストに返済した負債の数を加算したものであった。 物理学者の方法において、償却されるコストとは、完全なコストからポテンシャルの変化を減算したもの、つまり、共有されないコストに共有されるコストとポテンシャルの変化の差を加算したものである。 ポテンシャルの一単位と一負債を同等であると見なすなら、共有されるコストは累積した負債を増加させたかもしれない負債の数であり、ポテンシャルの変化は累積した負債を増加させた負債の数である。 その違いは、一部の負債を返済することによって作られたに違いない。 従って、物理学者の方法における償却されるコストとは、共有されないコストに返済した負債の数を加算したものであると見なすことができる。

時として、あるオブジェクトのポテンシャルがゼロではないのに、そのオブジェクトのサスペンションをフォースしたくなる。 その場合は、償却されるコストにオブジェクトのポテンシャルを加算する。 これは通常、演算が新しいオブジェクトを返さないために、サスペンションをフォースするコストをポテンシャルの変化に反映させることができない、クエリにおいて発生する。

銀行家と物理学者の方法の間の大きな違いは、銀行家の方法では、あるサスペンションに対する負債が支払われたらすぐに、その他のサスペンションに対する負債が返済されるのを待たずに、そのサスペンションをフォースしてもよいが、物理学者の方法では、あるオブジェクトの累積した負債が全体として減少して、そのポテンシャルがゼロになることが測定されたときにだけ、共有されるサスペンションをフォースできることだ。 あるオブジェクトの累積した負債の全体としてのポテンシャルを測定するだけで場所の違いは区別しないので、未払いの負債の全体がフォースしたい特定のサスペンションに関連していると、悲観的に仮定しなければならない。 この理由により、物理学者の方法は銀行家の方法よりも劣っているように見える。 しかしながら、それが適用できるなら、物理学者の方法は銀行家の方法よりもずっと簡単になる傾向がある。

物理学者の方法では、ネストしたサスペンションの部分的な実行を活用できないので、モノリシックな関数よりもインクリメンタルな関数を好む理由はない。 実のところ、物理学者の方法を適用できるかどうかの良いヒントは、全てあるいは大部分のサスペンションがモノリシックであるかどうかだ。

@t3t5u
Copy link
Author

t3t5u commented Mar 20, 2015

累積した貯蓄の下限を、累積した負債の上限に、置き換える。
累積した負債の変化は、全てポテンシャルの変化に反映される。
償却されるコストとは、完全なコストからポテンシャルの変化を減算したもの。
償却されるコストとは、共有されないコストに返済した負債の数を加算したもの。
返済した負債の数とは、共有されるコストとポテンシャルの変化の差。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment