Алгоритмы и структуры данных #10 | Кэширование, eviction policies, LRU cache, doubly linked lists

Продолжаем уроки по алгоритмам и структурам данных! В этот раз говорим про кэширование и про политики "выселения" элементов из кэша (eviction policies). Мы рассмотрим политики farthest in the future и least recently used (LRU). Также узнаем, для чего могут потребоваться двунаправленные связанные списки (doubly linked lists) и что такое spatial locality. Таймкоды: 00:00 Введение 01:00 Что такое кэш? 03:30 Уровни хранения данных 05:00 Eviction policy 06:55 Наивная реализация кэша 07:45 Политика farthest in the future 10:55 Политика least recently used 13:00 Алгоритмическая сложность LRU 15:30 Комбинация структур для LRU 18:40 Doubly linked lists для LRU 21:40 Комбинируем DLL с хэшами 24:40 Реализация doubly linked lists 26:50 Реализация LRU 28:45 Пример работы LRU 30:35 Worst case scenario LRU 32:05 Случайность для LRU 33:15 Spatial locality 37:00 Заключение Станьте спонсором канала, и вы получите доступ к эксклюзивным бонусам:    / @ilyabodrovkrukowski   Boosty: https://boosty.to/bodrovis
Patreon:   / bodrovis   Аккаунт Ethereum (ETH), Arbitrum, Polygon, BNB, USDT, TRX, BUSD: 0x719C2d2bcC155c85190f20E1Cc3710F90FAFDa16 Исходный код https://github.com/bodrovis-learning/...
Канал Telegram: https://t.me/dev_in_ruby_colors
Наш чат в Telegram: https://t.me/joinchat/MxYT6-01eeA1NTYy
Мой сайт: http://bodrovis.tech