элемент.
Ответ на этот вопрос кроется в результатах исследования, которое провели программисты в 70-е и 80-е годы. Их версия задачи называется «самоорганизующиеся списки», и ее формулировка практически полностью копирует дилемму Ногучи о хранении папок. Представьте, что у вас есть набор последовательных элементов и вы должны периодически просматривать их, чтобы найти определенные элементы. Поиск не может быть линейным, поскольку вы должны «отсматривать» один элемент за другим с самого начала. Но, найдя искомый предмет, вы можете вернуть его на любое место в этой последовательности. Вопрос: на какое место вы должны вернуть элемент, чтобы поиск был максимально эффективным?
Исследование самоорганизующихся списков, опубликованное Дэниэлом Слитором и Робертом Таржаном в 1985 году, оказалось исчерпывающим. В работе были рассмотрены наихудшие результаты, которые возможно было получить при различных способах организации списка. Поскольку поиск начинается сверху, вам интуитивно хотелось бы организовать последовательность так, чтобы элементы, которые вам, скорее всего, понадобятся снова, отобразились сверху. Но что за элементы должны там оказаться? Здесь нам снова хотелось бы воспользоваться даром ясновидения. «Если вам заранее известна последовательность, – пишет Таржан, которому приходится делить свое время между Кремниевой долиной и Принстоном, – вы можете адаптировать структуру данных таким образом, чтобы минимизировать время, затраченное на всю последовательность элементов. Это идеальный автономный алгоритм, Богом данный, если угодно. Конечно, никто не может предсказать будущее, но вопрос в том, что если вы не знаете будущего, то как близко вы сможете подойти к этому идеальному алгоритму?» Результаты исследования Слитора и Таржана выявили, что в некоторых «очень простых адаптивных схемах, что удивительно, всегда присутствует один неизменный фактор» ясновидения. А именно: если следовать принципу замещения по давности использования, согласно которому вы всегда возвращаете искомый элемент в самое начало списка, то время, которое вы потратите на поиски, будет максимум вдвое больше того, которое вам понадобилось бы, знай вы будущее. Другие алгоритмы не дадут вам таких гарантий.
Тот факт, что за системой хранения документов по Ногучи стоит именно принцип замещения по давности использования, говорит о том, что этот принцип не просто эффективен. Он оптимален.
Результаты исследования Слитора и Таржана демонстрируют нам следующий виток, и он становится очевиден, если взглянуть на систему хранения Ногучи под другим углом. Проще говоря, коробка с папками превращается в кипу. И естественно, когда вы ищете что-то в кипе бумаг или папок, вы кладете найденный документ сверху, но не в то место, откуда вы его взяли