生きるアルゴリズム：04

Cache：最適な物の配置

本記事は"Algorithms to Live By: The Computer Science of Human Decisions"のchapter04の要約と所感のようなものです。

Chapter04はCache（キャッシュ：日本語訳がこれしかありません😇）についてです、じゃあキャッシュってどういうものなんでしょう。

超簡略化するとコンピュータにおけるキャッシュはよく使うデータを取りやすいとこに置き使いやすくほかのデータに比べ使いやすくするというようなものです。

身近なものに例えると自宅にある本なんていかがでしょうか？

家には本棚があってそこに本を置いておきます、でもよく読むもしくは今読んでいる本は本棚というよりも自分の作業机やカバンの中などより手の届きやすい場所においてあるのではないでしょうか？

また、パソコンのデスクトップのショートカットはよく使うものをワンクリックで利用できるように使っている人が多いのではないでしょうか？

これがコンピュータサイエンスでいう「キャッシュ」です。

キャッシュしておけるデータは全データの一部のみです、実世界で考えるとわかりやすいですが全データがデスクトップにあったり本棚の本がすべて机に広がっていたらもはや意味がないですよね？

デスクトップや机の上の空間はほかの空間（よくわからないディレクトリの奥のほうや家の本棚）よりも価値が高いわけです、そこをいろんなものを置いてごちゃごちゃにはしたくありません。

キャッシュできるデータが限定的であることが分かった今、次の関心は何をキャッシュしておくか（つまり何が使用頻度の高いデータか）です。

これを決めるには、近い未来自分が何のデータを頻繁に利用するかという未来を見通す力が必要です。

ひとたびキャッシュできるメモリの限界が来た時にどのメモリから捨てていくかのアルゴリズムを比較した実験があります。実験ではrandom eviction（ランダムに捨てる）、FIFO(First-in First-out：キャッシュされた時期が早い順に捨てる)、LRU（Least recently used：使われた時期が最も古いものを捨てる）が比べられました。

結果はLRUがほかの二つを圧倒的に上回るものでした、コンピュータサイエンスでいうtemporal locality（時間的局所性：プログラムはある情報を呼び出すと近い未来で同じ情報を呼び出す可能性が高い）というものによります。

この結果から考えればもしかしたら図書館は返却された本を元あった場所に戻すよりも図書館の入り口近くに最近返却された本コーナーを置いたほうがいいかもしれません。

この考え方を利用したストレージが物理的な倉庫と電子的ストレージどちらにも応用されています、物理的倉庫のほうではAmazonが特許を持っている「予想パッケージシッピング」という、例えばある地域でトイレットペーパーの購入が増えたら注文が入る前にその地域の近くのAmazonの倉庫にトイレットペーパーを先に運んでおくようなものがあります。

電子的なものでは特定のウェブページのキャッシュをそのウェブページが良く利用される地域の近くのサーバー(amazon.jpなら日本にあるCDN{content distributed networks：akamaiという会社がこのCDNのシェア一位を誇るらしいです})においておくことで素早くウェブページがロードできます。

ちなみに、日本人の経済学者でNoguchiという人がいてその人が素晴らしいファイル管理方法を提案したことがあります、使ったファイルを古いものから順に積み上げていくものですが、これはLRUと同じものですし、僕たちの机の上によく出来上がる本や書類の積み重ねも意外とコンピュータサイエンス的にとても効率的なデータの活用法なのかもしれません。

次はスケジューリングです！