Мы могли бы просто прибегнуть к произвольному замещению, добавляя новые данные в кеш и записывая их поверх старых вне какого-либо определенного порядка. Одним из удивительных результатов ранней теории кеширования стал тот факт, что этот подход, хоть и далекий от идеала, отчасти все же работает. Получается, что просто наличие кеша в системе уже делает ее более эффективной, вне зависимости от того, как вы ее используете. Единицы информации, которые вы часто используете, все равно вернутся в кеш. Другое простое решение – метод «первым вошел, первым вышел», когда вы замещаете или перезаписываете те данные, которые находятся в кеше дольше всего (помните вопрос Марты Стюарт «Как давно у меня эта вещь?»).
В рамках третьего подхода – вытеснения по давности использования – замещается тот фрагмент информации, к которому дольше всего не было обращений (вопрос Марты Стюарт «Когда в последний раз я это надевала или использовала?»).
Получается, что эти две мантры Марты Стюарт предлагают две разные стратегии. Более того, одна из них явно превосходит другую. Белади сравнил произвольное замещение, метод «первым вошел, первым вышел» и различные вариации вытеснения по давности использования на нескольких примерах и пришел к выводу, что метод вытеснения по давности использования неизменно показывал результаты, максимально близкие к ясновидению. Этот метод эффективен из-за так называемой временной локальности: если программа обращалась к некоему фрагменту информации единожды, то вполне вероятно, что это повторится в ближайшем будущем. Временная локальность отчасти обусловлена тем, как компьютер справляется с задачами (например, выполнением цикла быстрых операций, связанных со считыванием данных и их записью), но она также заметно проявляется и в том, как люди решают свои проблемы. Работая на компьютере, вы можете переключаться между электронной почтой, интернет-браузером и текстовым редактором. Тот факт, что вы недавно использовали одну из этих программ, указывает на то, что вы, вполне вероятно, откроете ее снова, и при прочих равных условиях программа, которой вы не пользовались дольше всего, с наибольшей вероятностью не будет открыта в ближайшее время.
По сути, этот принцип косвенным образом лежит в основе интерфейса, который компьютер демонстрирует своим пользователям. Окна на экране вашего компьютера располагаются в Z-образном порядке, который симулирует глубину, показывая, какая программа открыта поверх остальных. Программа, которая использовалась максимально давно, как будто оказывается на дне. Как утверждает Аза Раскин, бывший креативный директор Firefox, «бóльшая часть времени, которую вы проводите за современным компьютером, – это цифровой эквивалент сортировки бумаг». Эта «сортировка» с точностью отражается в интерфейсах переключения задач в Windows и Mac OS: когда вы нажимаете на клавиши Alt + Tab или Command + Tab, вы видите, что ваши приложения отражаются упорядоченным списком, от наиболее используемого к наименее используемому.