スプレッドシートを再計算する方法

2人の友人のためにブリトーを注文していて、合計注文額を計算したいとします。







このテーブルのデータフローは従うのが少し難しいので、テーブルをグラフとして表す同等のチャートを次に示します。







エルファロリートスーパーベジブリトーのコストを8ドルに丸めます。 2ドルの価値があり、合計金額は20ドルになります。



ああ、すっかり忘れてしまいました！私の友人の1人は1つのブリトーには十分ではありません、彼は2つ必要です。だから本当に3つ注文したいです。更新された Num Burritos



場合、ナイーブスプレッドシートエンジンは、最初に入力なしでセルを再計算し、次にセルがなくなるまで準備完了入力で各セルを再計算することにより、ドキュメント全体を再計算できます。この場合、最初にブリトーの価格と数量を計算し、次に配送ブリトーの価格を計算し、次に新しい合計$ 30を計算します。







ドキュメント全体を再計算するこの単純な戦略は無駄に思えるかもしれませんが、実際には、歴史上最初のスプレッドシートであり、AppleIIコンピューターを普及させた最初のいわゆるキラーアプリであるVisiCalcよりも優れています。 VisiCalcは、セルを左から右、上から下に何度も再計算し、何も変更されていませんが、何度も何度もスキャンしました。この「興味深い」アルゴリズムにもかかわらず、VisiCalcは4年間主要なスプレッドシートソフトウェアであり続けました。彼の治世は、ロータス1-2-3が「自然秩序の再計算」で市場を引き継いだ1983年に終わりました。これは 、Tracy RobnettLickliderがByteマガジンで彼を説明した方法です。

Lotus 1-2-3は自然な順序を使用しましたが、VisiCalcの行モードと列モードもサポートしていました。自然な再計算により、セルの依存関係のリストが維持され、依存関係に基づいてセルが再計算されました。

Lotus 1-2-3は、上記のすべての再計算戦略を実装しました。スプレッドシート開発の最初の10年間は​​、これが最適なアプローチでした。はい、ドキュメント内のすべてのセルを再計算しますが、1回だけです。

しかし、配達ブリトーの価格はどうですか

本当に。 3つのブリトを使用する私の例では、1つのブリトの価格を配達時に再計算する理由はありません。これは、順序でブリトの数を変更しても、ブリトの価格に影響を与えないためです。 1989年、ロータスの競合他社の1つがこれを理解し、SuperCalc5を作成しました。おそらく、アルゴリズムの背後にあるスーパーブリート理論にちなんで名付けられました。 SuperCalc5は「変更されたセルに依存するセルのみ」を再計算したため、ブリトカウントの更新は次のようになりました。







入力データが変更されたときにのみセルを更新することで、配信時にブリトの価格を再計算することを回避できます。この場合、追加を1つだけ保存しますが、大きなスプレッドシートでは、節約がはるかに重要になる可能性があります。残念ながら、現在は別の問題があります。私の友人が今、1ドル高い肉のブリトーを欲しがっていて、El Farolitoは、ブリトーの数に関係なく、注文に2ドルを追加するとします。何かを再計算する前に、グラフを見てみましょう。







ここでは2つのセルが更新されているため、問題が発生します。最初に1つのブリトーの価格を再計算する必要がありますか、それとも合計を再計算する必要がありますか？理想的には、最初にブリトー価格を計算し、変化に気づき、次に出荷ブリトー価格を再計算し、最後に合計を再計算します。ただし、代わりに最初に合計を再計算する場合は、新しい9ドルのブリトー価格がセルに分散したら、もう一度合計を再計算する必要があります。セルを正しい順序で計算しない場合、このアルゴリズムはドキュメント全体を再計算するよりも優れています。場合によってはVisiCalcと同じくらい遅いです！



明らかに、セルを更新する正しい順序を決定することが重要です。一般に、この問題には2つの解決策があります。ダーティマーキングとトポロジカルソートです。



最初の解決策は、更新されたセルの下流にあるすべてのセルにラベルを付けることです。それらはダーティとしてマークされています。たとえば、私たちはブリトーの価格を更新するとき、私たちは、下流の細胞をマーク Burrito Price w Ship



して Total



：任意の再計算を行う前に、







-それを再計算し、ループの中で、我々は無い汚い入力で汚れた細胞を見つけます。汚れたセルがなくなったら、完了です。これにより、依存関係の問題が解決されます。ただし、欠点が1つあります。セルが再計算され、新しい結果が前の結果と同じであることがわかった場合でも、下位のセルが再計算されます。少し余分なロジックを使用すると問題を回避できますが、残念ながら、セルのマーキングとマーキングの削除に時間を費やしています。



2番目の解決策はトポロジカルソートです。セルに入力がない場合は、その高さを0としてマークします。入力がある場合は、入力セルの最大値に1を加えたものとして高さをマークします。これにより、各セルの高さの値がどの着信セルよりも大きくなるため、入力が変更されたすべてのセルを追跡し、常に最初に再計算するために高さが最も低いセルを選択し







ます。二重更新の例では、ブリトと合計金額は、最初に変換ヒープに追加されます。ブリトー価格は低く、最初に再計算されます。結果が変わったので、配信ブリトーの価格を再計算ヒープに追加します。また、高さがよりも短いためです。 Total



その後、最終的に再カウントする前に再計算されます Total



。



これは最初の解決策よりもはるかに優れています。着信セルの1つが実際に変更されない限り、ダーティとマークされるセルはありません。ただし、これには、再計算が行われるまでセルをソートされた順序で保持する必要があります。ヒープで使用すると、O(n log n)



速度が低下します 。これは、最悪の場合、Lotus1-2-3の再計算された戦略よりも漸近的に遅くなります。



最新のExcelは、汚染とトポロジカルソートを組み合わせて使用します 。詳細については、ドキュメントを参照してください。

怠惰な評価

現在、最新のスプレッドシートで再計算アルゴリズムを多かれ少なかれ達成しています。残念ながら、原則として、さらなる改善のためのビジネス上の正当性はないと思います。人々はすでに、他のプラットフォームへの移行を不可能にするのに十分なExcel式を作成しています。幸い、私はビジネスに精通していないので、とにかくさらなる改善を検討します。



キャッシングとは別に、スプレッドシートスタイルの計算グラフの興味深い側面の1つは、関心のあるセルしか計算できないことです。これは、遅延評価または需要主導型計算と呼ばれることもあります。より具体的な例として、これは少し拡張されたブリトスプレッドシートグラフです。例は以前と同じですが、「サルサ計算」として最もよく説明されるものを追加しました。各ブリトーには40グラムのサルサが含まれており、注文全体でどれだけのサルサが含まれているかを調べるために簡単に乗算を行います。注文にブリトが3つあるので、合計120グラムのサルサがあります。







もちろん、目の肥えた読者はすでに問題に気づいています：注文のサルサの総重量はかなり役に立たない測定基準です。 120グラムかどうか誰が気にしますか？この情報をどうすればよいですか？残念ながら、通常のスプレッドシートでは、ほとんどの場合サルサ計算が必要ない場合でも、サルサ計算にサイクルが費やされます。



これは、怠惰な再計算が役立つ場合があります。どういうわけか、結果のみに関心があることを示した場合 Total



、このセルとその依存関係を再計算し、サルサに触れることはできません。その結果を見ようとしているので、それをTotal



観測セルと呼びましょう 。必要なTotal



依存関係の3つを 呼び出すこともでき ます。観測されたセルを計算するために必要なセル。 Salsa In Order



そしてSalsa Per Burrito



それを不要と 呼びます 。



この問題を解決するために、Rustチームメイトの一部はSalsaフレームワークを作成し、 コンピューターサイクルを浪費した不要なSalsa計算にちなんで明示的に名前を付けました。確かに 彼らはそれがどのように機能するかを私よりよく説明することができます。非常に大まかに言えば、フレームワークはリビジョン番号を使用して、セルの再計算が必要かどうかを追跡します。式または入力に変異があると、グローバルリビジョン番号が増加し、各セルは2つのリビジョンを追跡します。 verified_at



結果が更新さchanged_at



れたリビジョンおよび 実際に結果が変更されたリビジョンの場合。







ユーザーが新しい値が必要であることを示すと Total



、最初にに必要なすべてのセルを再帰的に再計算し Total



、リビジョンlast_updated



がグローバルリビジョンと等しいセルをスキップし ます。依存関係が Total



更新されTotal



たら、Burrito Price w Shipの場合、またはチェックされたNum Burrito



リビジョンchanged_at



よりも大きいリビジョン がある場合にのみ 、実際の式を再実行し ます。 Total



..。これは、単純さが重要であり、各セルの計算に時間がかかる錆分析装置のSalsaに最適です。ただし、上記のブリトーのグラフでは、欠点に気付くことができます。 Salsa Per Burrito



絶えず変化している場合、グローバルリビジョン番号が増えることがよくあります。その結果、Total



どの観測も変更されていなくても、各観測で は3つのセルをトラバースする必要があります。式は再計算されませんが、グラフが大きい場合、すべてのセルの依存関係を繰り返すとコストがかかる可能性があります。

怠惰な評価のためのより速いオプション

新しい怠惰なアルゴリズムを発明する代わりに、前述の2つの古典的なスプレッドシートアルゴリズムであるラベリングとトポロジカルソートを試してみましょう。ご想像のとおり、レイジーモデルはこれらのタスクの両方を複雑にしますが、どちらも実行可能です。



最初にマーキングを見てみましょう。以前と同様に、セルの式を変更すると、すべてのダウンストリームセルがダーティとしてマークされます。したがって、更新すると、次の Salsa Per Burrito



ようになります。







ただし、すべてのダーティセルをすぐに再計算 するのではなく、ユーザーがセルを確認するまで待機します。次に、Salsaアルゴリズムを実行しますが、古いバージョン番号で依存関係を再チェックする代わりに verified_at



、ダーティとマークされたセルのみを再チェックします。Adaptonはこの手法を使用します 。このような状況では、セルを観察すると、セル Total



が汚れていないことがわかります。したがって、Salsaが実行したはずのグラフパスをスキップできます。



を観察すると Salsa In Order



、ダーティとしてマークされているため、再チェックして再計算し、、、およびを再計算 Salsa Per Burrito



し Salsa In Order



ます。ここでも、まだ空白のセルを再帰的にスキップできるため、リビジョン番号のみを使用するよりも利点があります Num Burritos



。



レイジーダーティラベリングは、観察しようとしているセルのセットを頻繁に変更するのに最適です。残念ながら、以前のダーティマーキングアルゴリズムと同じ欠点があります。ダウンストリームセルが多数あるセルが変更された場合、再計算に進んだときに入力が実際に変更されていなくても、セルのマーク付けとマーク解除に多くの時間を費やします。最悪の場合、変更するたびにグラフ全体がダーティとしてマークされ、Salsaアルゴリズムとほぼ同じパフォーマンスが得られます。



面倒なラベリングに加えて、怠惰な評価のためにトポロジカルソートを適応させることもできます。このメソッドはインクリメンタルライブラリを使用します ジェーンストリートから、そしてそれを正しく動作させるにはいくつかの深刻なトリックが必要です。遅延評価を実装する前に、トポロジカルソートアルゴリズムはヒープを使用して、次に再計算するセルを決定しました。しかし今、必要なセルだけを再計算したいと思います。どうやって？アダプトンのように観察されたセルからツリー全体を歩くことは望ましくありません。ツリーを完全に歩くと、トポロジカルソートの目的全体が破壊され、アダプトンと同様のパフォーマンス特性が得られるためです。



代わりに、インクリメンタルは、ユーザーが監視対象としてマークしたセルのセットと、監視対象のセルに必要なセルのセットを維持します。セルが監視可能または監視不能としてマークされている場合は常に、インクリメンタルはそのセルの依存関係をウォークスルーして、必要なラベルが正しく適用されていることを確認します。次に、必要に応じてマークが付けられている場合にのみ、セルを再計算ヒープに追加します。私たちのブリトグラフでTotal



は、それ が観察可能なセットの一部であるSalsa in Order



限り、必要なセルのみが再計算されるため、変更 によってグラフが通過することはありません。







これにより、セルをダーティとしてマークするためにグラフを熱心に歩くことなく、問題が解決されます。私たちはまだそのセルを覚えておく必要があります Salsa per Burrito



必要に応じて後で再計算するために汚れています。ただし、Adaptonのアルゴリズムとは異なり、その1つのダーティラベルをグラフ全体にプッシュする必要はありません。

アンカー、ハイブリッドソリューション

AdaptonとIncrementalはどちらも、セルを再計算しなくてもグラフをトラバースします。インクリメンタルは、観測されたセルのセットが変更されるとグラフを上に移動し、アダプトンは式が変更されるとグラフを下に移動します。小さなグラフでは、これらのパスの高コストがすぐには明らかにならない場合があります。しかし、グラフが大きく、セルの計算が比較的安価である場合（多くの場合、これはスプレッドシートの場合です）、計算のほとんどがグラフを不必要に歩き回ることで無駄になっていることがわかります。セルが安価な場合、セルにビットをラベル付けすることは、セルを最初から再計算するのとほぼ同じコストになる可能性があります。したがって、理想的には、アルゴリズムを単純な計算よりも大幅に高速にしたい場合は、グラフを不必要に歩き回らないようにする必要があります。



この問題について考えれば考えるほど、ほぼ逆の状況でグラフをトラバースするのに時間を浪費していることに気づきました。ブリトーグラフで、セルの式がめったに変更されないことを想像してみましょう。ただし、最初に観察してTotal



から、次に すばやく切り替え Salsa in Order



ます。







この場合、Adaptonはツリーを歩きません。入力データは変更されないため、セルにマークを付ける必要はありません。フラグが立てられていないため、空白のセルからキャッシュされた値をすぐに返すことができるため、すべての観測は安価です。ただし、この例ではインクリメンタルはうまく機能しません。値は再計算されませんが、インクリメンタルは必要または不要な場合に多くのセルを繰り返しマークおよびチェック解除します。



それ以外の場合は、式が急速に変化しているが、観測されたセルのリストは変更されていないグラフを想像してみましょう。たとえばTotal



、ブリトーの価格をから4+4



に すばやく変更して、自分が見ている と想像するかもしれません 2*4



。







前の例のように、私たちは、実際に多くのセルを再計算しません。 4+4



と 2*4



対等 8



、したがって、理想的には、ユーザーがこの変更を行ったときにのみ、この算術を再計算します。ただし、前の例とは異なり、インクリメンタルはツリーウォーキングを回避するようになりました。インクリメンタルでは、ブリト価格が必須セルであるという事実をキャッシュしているため、変更された場合、グラフを経由せずに再計算できます。 Adaptonを使用するBurrito Price w Ship



とTotal



、結果Burrito Price



が変わらない場合でも、マーキングの時間と 面倒な 作業を無駄に します。



各アルゴリズムが他の縮退したケースでうまく機能することを考えると、理想的にはそれらの縮退したケースを検出して、より高速なアルゴリズムに切り替えてみませんか？これは私が自分のライブラリに実装しようとしたものです アンカー。同じグラフで両方のアルゴリズムを同時に実行します！クレイジーで、不必要で、複雑すぎるように聞こえる場合は、おそらくそうだからです。



多くの場合、アンカーはインクリメンタルアルゴリズムに正確に従うため、上記の縮退したアダプトンのケースを回避できます。しかし、細胞が観察不能としてマークされている場合、それらの動作はわずかに異なります。何が起こっているのか見てみましょう。Total



観察されたセルとしてマークすることから始めましょう ：







次にそれTotal



を観察不可能なセルとしてマークSalsa in Order



し、観察可能なものとしてマークする と 、従来のインクリメンタルアルゴリズムはグラフを変更し、プロセス内のすべてのセルを通過します：







この変更のアンカーもすべてのセルをバイパスしますが、別のグラフを作成します：







「きれいな」セルのフラグに注意してください！セルが不要になると、空白としてマークします。観測Salsa in Order



から Total



次のように移動するとどうなるか見てみましょう ：







右-グラフに「必要な」セルが なくなりました。セルに「クリーン」フラグがある場合、それを監視可能としてマークすることはありません。これからは、どのセルを観測済みまたは未観測としてマークしても、アンカーはグラフを歩く時間を無駄にすることはありません。入力が変更されていないことを彼女は知っています。



El Farolitoが割引を発表したようです！ブリトーの値段を1ドル下げましょう。アンカーはどのようにして金額を再計算することを知っていますか？再計算する前に、ブリト価格が変更された直後にアンカーがグラフをどのように表示するかを見てみましょう。







セルに明確なフラグがある場合は、従来のAdaptonアルゴリズムを実行して、下流のセルをダーティとしてマークします。後でインクリメンタルアルゴリズムを実行すると、ダーティとマークされた観測可能なセルがあることがすぐにわかり、その依存関係を再計算する必要があることがわかります。最終的なグラフは次のようになります。







セルは必要な場合にのみ再計算するため、ダーティセルを再計算するときは常に、必要に応じてマークを付けます。大まかに言えば、セルのこれら3つの状態を循環状態マシンと考えることができます。







必要なセルで、インクリメンタルトポロジカルソートアルゴリズムを実行します。残りの部分では、Adaptonアルゴリズムを実行します。

Burrito構文

結論として、最後の質問に答えたいと思います。これまで、レイジーモデルがテーブル再計算戦略に引き起こす多くの問題について説明してきました。しかし、問題はアルゴリズムだけにあるのではなく、構文上の問題もあります。たとえば、テーブルをまとめて、クライアントの絵文字ブリトーを選択しましょう。私たちは声明書きたいと思い IF



、このようなテーブルでは：







伝統的なスプレッドシートは怠け者ではありませんので、我々は計算することができ B1



、 B2



かつ B3



任意の順序で、その後、セルを計算します IF



..。ただし、怠惰な世界では、最初にB1の値を計算できれば、結果を見て、再計算する必要のある値（B2またはB3）を見つけることができます。残念ながら、従来のスプレッドシートで IF



はこれを表現できません。



問題： B2



セルB2



を同時に参照し、 その値を取得します。代わりに、この記事で言及されている怠惰なライブラリのほとんどは、セル参照とその実際の値を取得する動作を明示的に区別しています。アンカーでは、このセル参照をアンカーと呼びます。実生活のように、ブリトーはたくさんの材料を一緒にAnchor<T>



包みT



ます、タイプは 包み ます。だから私たちのビーガンブリトセルは Anchor<Burrito>



、一種のばかげたブリトブリト。関数はAnchor<Burrito>



、必要なだけ転送でき ます。しかし、実際にブリトをアンラップしてBurrito



内部にアクセスする と、グラフに依存関係エッジが作成され、セルが必要であり、再計算が必要であることを再計算アルゴリズムに示します。



SalsaとAdaptonが採用したアプローチは、これらの値を拡張する方法として、関数呼び出しと通常の制御フローを使用することです。たとえば、Adaptonでは、Burrito forCustomerセルを次のように記述できます。

let burrito_for_customer = cell!({
    if get!(is_vegetarian) {
        get!(vegi_burrito)
    } else {
        get!(meat_burrito)
    }
});
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

セル参照（ここvegi_burrito



）とその値を拡張する動作（ ）を get!



区別することにより、Adaptonはif



。などのRust制御フローステートメントの上で実行できます 。これは素晴らしい解決策です！ただし、を変更get!



するcell!



とき にセルへの呼び出しを 適切にワイヤリングするには、少し魔法のグローバル状態が必要 is_vegetarian



です。インクリメンタルの影響を受けたアンカーライブラリは、それほど魔法のようなアプローチを取りません。async-pre / awaitと同様に Future



、Anchorsではや Anchor<T>



などの操作を 起動できます 。したがって、上記の例は次のようになります。 map



then

let burrito_for_customer: Anchor<Burrito> = is_vegetarian.then(|is_vegetarian: bool| -> Anchor<Burrito> {
  if is_vegetarian {
      vegi_burrito
  } else {
      meat_burrito
  }
});
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

参考文献

このすでに長くて華やかな記事では、それほど多くのトピックのための十分なスペースがありませんでした。うまくいけば、これらのリソースがこの非常に興味深い問題にもう少し光を当てることができます。

• インクリメンタルの7つの実装、インクリメンタルの内部の詳細な調査、説明する時間がなかった高さの絶え間ない増加などの一連の最適化、および依存関係を変更するセルを処理する巧妙な方法。Ron Minsky：FRPParsingからも読む価値があります。
  
  
• Salsaの仕組みを説明するビデオ。
  
  
• これはSalsaチケットで、Adaptonの作成者であるMatthew Hammerが、カットオフがどのように機能するかわからないランダムな通行人（私）に辛抱強く説明します。
  
  
• Rustlab . , « » «: DX CS» — .
  
  
• , « », Materialize. , . , (!) « », , . Noira .
  
  
• Adapton .
  
  
• この考え方は、システムの構築にも当てはまることがわかりました。これは、ビルドシステムとスプレッドシートの類似性に関する最初の科学記事の1つです。
  
  
• Slightly Incremental Ray Tracing は、Ocamlで記述されたわずかにインクリメンタルなレイトレーサーです。
  
  
• ジャストは見、「データフローに基づいたマテリアライズド・ビューで一部国家」とそれが関連すると思われます。
  
  
• スキップとインプも非常に面白そうです。

そしてもちろん、あなたはいつでも私のアンカーフレームワークをチェックすることができます 。