Алгоритмы для жизни: Простые способы принимать верные решения - [46]

Но при этом компьютерная наука дает нам то, что большинство гуру эффективности дать не могут, – гарантии.

Хотя Ногучи и не осознавал этого, его система подшивки и хранения документов представляет собой не что иное, как продолжение принципа замещения по давности использования. Как мы помним, этот принцип подсказывает нам, что, добавляя в кеш что-то новое, мы должны отказаться от наиболее долго хранящегося в нем элемента. Но при этом нам не говорят, куда конкретно мы должны поместить новый элемент.

Ответ на этот вопрос кроется в результатах исследования, которое провели программисты в 70-е и 80-е годы. Их версия задачи называется «самоорганизующиеся списки», и ее формулировка практически полностью копирует дилемму Ногучи о хранении папок. Представьте, что у вас есть набор последовательных элементов и вы должны периодически просматривать их, чтобы найти определенные элементы. Поиск не может быть линейным, поскольку вы должны «отсматривать» один элемент за другим с самого начала. Но, найдя искомый предмет, вы можете вернуть его на любое место в этой последовательности. Вопрос: на какое место вы должны вернуть элемент, чтобы поиск был максимально эффективным?

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

Тот факт, что за системой хранения документов по Ногучи стоит именно принцип замещения по давности использования, говорит о том, что этот принцип не просто эффективен. Он оптимален.

Результаты исследования Слитора и Таржана демонстрируют нам следующий виток, и он становится очевиден, если взглянуть на систему хранения Ногучи под другим углом. Проще говоря, коробка с папками превращается в кипу. И естественно, когда вы ищете что-то в кипе бумаг или папок, вы кладете найденный документ сверху, но не в то место, откуда вы его взяли[12].

Математическая основа самоорганизующихся списков подсказывает нам другое – радикальное – видение этой ситуации: огромная кипа бумаг на вашем столе – это не столько провоцирующий чувство вины очаг хаоса, сколько одна из наиболее логично и эффективно организованных структур в мире. То, что может со стороны показаться неорганизованным беспорядком, по сути, является самоорганизующимся беспорядком. Бросить документы назад на самый верх стопки – лучшее, что вы можете сделать, не осмеливаясь предугадывать будущее. В предыдущей главе мы рассмотрели случаи, когда отказаться от сортировки было в разы эффективнее, чем тратить на нее время. Здесь, однако, совсем другая причина, по которой нам не нужно создавать порядок.

Ведь мы его уже создали.

Кривая забывания

Конечно, ни одно рассуждение о памяти не будет исчерпывающим без упоминания «органа памяти», самого близкого к началу начал, – человеческого мозга. За последние несколько десятилетий влияние компьютерной науки совершило своего рода революцию в представлениях психологов о памяти.

Считается, что наука о человеческой памяти берет свое начало в 1879 году. Возникновение науки связывают с именем молодого психолога, научного сотрудника Берлинского университета Германа Эббингауза. Ученый хотел добраться до самой сути работы памяти человека и доказать, что ее можно изучить со всей математической строгостью, присущей естественным наукам. Тогда он начал проводить эксперименты над собой.

Каждый день Эббингауз садился за стол и старался запомнить ничего не значащие слоги по списку. Затем он проверял, насколько хорошо помнит списки, заученные в предыдущие дни. В итоге в течение года он сделал множество ключевых выводов относительно человеческой памяти. В частности, Эббингауз подтвердил тот факт, что многократное повторение материала заставляет его дольше оставаться в памяти и количество запоминаемых элементов, которые человек может воспроизвести в точности, со временем уменьшается.