この記事では,検索しても意外と解説が少なかったLRUキャッシュとLFUキャッシュをPythonで丁寧めに実装していきます.特にLFUキャッシュが厄介なのでそちらがメインです. キャッシュとは ざっくり言うとキャッシュはよく使うデータを取り出しやすい場所に一時的に保存しておくものです.メモリ上のデータは参照される頻度に差があるので(時間的,空間的局所性など),よく参照されるデータをキャッシュに入れておくことでデータアクセスが高速になります.現代のコンピュータにはまさに必須の構造です. キャッシュに蓄えられるデータは多くはないため,どのデータを置いておくかというのは重要な問題です.容量いっぱいのキャッシュに新たな要素が入ってきたとき,今保持しているどの要素を捨てるかという選択に関して,最も基本的なものが以下の2つです. LRUキャッシュ: Least Recently Used. 直近に参照し