ドキュメント
Computer Science
アルゴリズム
最適化アルゴリズム
Cache

Cache

キャッシュアルゴリズム - LRU と LFU キャッシュ置換戦略(ちかんせんりゃく) 、システム性能(せいのう) とメモリ管理効率(かんりこうりつ) を向上(こうじょう) させるために使用(しよう) 。

LRU vs LFU 選択ガイド

比較項目(ひかくこうもく)LRU (Least Recently Used)LFU (Least Frequently Used)
原理(げんり)最近最(さいきんもっと) も使用(しよう) されていない項目(こうもく) を削除(さくじょ)使用頻度(しようひんど) が最(もっと) も低(ひく) い項目(こうもく) を削除(さくじょ)
適用場面(てきようばめん)最近(さいきん) アクセスしたデータが再度(さいど) アクセスされる可能性(かのうせい) がある人気(にんき) データが長期的(ちょうきてき) にアクセスされ、不人気(ふにんき) データは早(はや) めに削除(さくじょ) すべき
実装難易度(じっそうなんいど)簡単(かんたん) （双方向(そうほうこう) リンクリスト + HashMap）複雑(ふくざつ) （頻度計算(ひんどけいさん) が必要(ひつよう) 、min-heap やカウンタを使用(しよう) する場合(ばあい) あり）
利点(りてん)低(てい) オーバーヘッド、短期(たんき) アクセスパターンに適(てき) している長期的(ちょうきてき) に人気(にんき) のデータを保持(ほじ) 可能
欠点(けってん)Cache Pollution：短期的(たんきてき) に人気(にんき) だが後(あと) でアクセスされないデータがキャッシュを占有(せんゆう)LFU Aging Issue：古(ふる) い人気(にんき) データが長期間(ちょうきかん) キャッシュを占有(せんゆう)

LRU 適用場面

  • OS（ページ置換(ちかん) 、CPU キャッシュ）
  • ブラウザキャッシュ、データベースキャッシュ、CDN
  • 最近(さいきん) アクセスしたデータが将来(しょうらい) もアクセスされる可能性(かのうせい) がある

LFU 適用場面

  • 検索(けんさく) エンジン、広告配信(こうこくはいしん) 、レコメンドシステム
  • 長期的(ちょうきてき) に人気(にんき) のコンテンツ（人気映画(にんきえいが) 、音楽(おんがく) 、ニュース）
  • 短期的(たんきてき) に人気(にんき) だがすぐに冷(さ) めるデータがキャッシュを占有(せんゆう) するのを回避(かいひ)
Bit ManipulationLMAX Disruptor