テクノロジー

生きるアルゴリズム:04

nano's icon'
  • nano
  • 2020/04/04 13:54

Cache:最適な物の配置

Content image

 

本記事は"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と同じものですし、僕たちの机の上によく出来上がる本や書類の積み重ねも意外とコンピュータサイエンス的にとても効率的なデータの活用法なのかもしれません。

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

Supporter profile iconSupporter profile icon
Article tip 2人がサポートしています
獲得ALIS: Article like 62.44 ALIS Article tip 2.10 ALIS
nano's icon'
  • nano
  • @cryptoMedNano
コンピュータサイエンス専攻じゃないけどITに興味がある学生。英語、中国語もサポートしています。

投稿者の人気記事
コメントする
コメントする
こちらもおすすめ!
Eye catch
テクノロジー

iOS15 配信開始!!

Like token Tip token
7.20 ALIS
Eye catch
クリプト

Bitcoinの価値の源泉は、PoWによる電気代ではなくて"競争原理"だった。

Like token Tip token
159.32 ALIS
Eye catch
クリプト

17万円のPCでTwitterやってるのはもったいないのでETHマイニングを始めた話

Like token Tip token
46.60 ALIS
Eye catch
テクノロジー

彼女でも分かるように解説:ディープフェイク

Like token Tip token
32.10 ALIS
Eye catch
テクノロジー

なぜ、素人エンジニアの私が60日間でブロックチェーンゲームを制作できたのか、について語ってみた

Like token Tip token
270.93 ALIS
Eye catch
テクノロジー

オープンソースプロジェクトに参加して自己肯定感を高める

Like token Tip token
85.05 ALIS
Eye catch
クリプト

NFT解体新書・デジタルデータをNFTで販売するときのすべて【実証実験・共有レポート】

Like token Tip token
121.79 ALIS
Eye catch
他カテゴリ

ALISのシステム概観

Like token Tip token
5.00 ALIS
Eye catch
ゲーム

ドラクエで学ぶオーバフロー

Like token Tip token
30.10 ALIS
Eye catch
クリプト

Bitcoin史 〜0.00076ドルから6万ドルへの歩み〜

Like token Tip token
947.13 ALIS
Eye catch
クリプト

約2年間ブロックチェ-ンゲームをして

Like token Tip token
61.20 ALIS
Eye catch
他カテゴリ

機械学習を体験してみよう!(難易度低)

Like token Tip token
124.82 ALIS