Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

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

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

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

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

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

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

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

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

По результатам его исследований был составлен график, демонстрирующий, как информация со временем исчезает из памяти. Современные психологи называют его «кривая забывания». Исследования Эббингауза укрепили уверенность в том, что человеческая память имеет количественное измерение, но при этом некоторые вопросы так и остались без ответа. Почему именно эта кривая? Говорит ли она о том, что у человека хорошая или плохая память? Что стоит за этими результатами? Эти вопросы и вдохновляли психологов на дальнейшие наблюдения и исследования в течение более 100 лет.

В 1987 году психолог и программист Университета Карнеги – Меллон Джон Андерсон наткнулся на материал, посвященный работе информационно-поисковых систем, применяющихся в университетских библиотеках. Первоначальной целью Андерсона было написание работы о том, как результаты исследования человеческой памяти могли бы быть полезны для разработки таких систем. Но произошло обратное: он понял, что как раз принципы работы информационных систем могут стать ключом к изучению разума.

«В течение долгого времени, – отмечал Андерсон, – мне казалось, что в существующих теориях о памяти человека, в том числе и в моей собственной теории, чего-то не хватает. По сути, все эти теории характеризуют память как произвольную и неоптимальную структуру… Мне же давно казалось, что ключевые процессы памяти довольно адаптивны и, вероятно, даже оптимальны; однако у меня не было возможности использовать какую-либо схему, чтобы удостовериться в этом. В научной статье об информационном поиске я наконец обнаружил эту схему».

Мы привыкли думать, что причина забывания каких-либо вещей – нехватка места в памяти человека. Но ключевая идея, которая стоит за наблюдениями Андерсона, подсказывает нам, что проблема кроется не в хранении информации, а в ее организации.

Согласно этой теории, объем памяти мозга неограничен, но ограничено время, которое мы тратим на поиск воспоминаний. Андерсон провел аналогию с библиотекой, в которой есть только одна бесконечно длинная полка – система подшивки и хранения документов в масштабе Библиотеки Конгресса США. Вы можете уместить на ней столько документов, сколько пожелаете, при этом, чем ближе искомый элемент к началу полки, тем быстрее его можно найти.

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

Если не брать в расчет ясновидение, то для того, чтобы делать прогнозы в мире людей, требуется понимание устройства этого мира в целом. Вместе со своим коллегой Лайлом Шулером Андерсон начал примерять исследования, похожие на упражнения Эббингауза, но не в отношении мозга, а в отношении устройства человеческого общества. Вопрос был простой: какова схема забывания у всего мира? Каким образом события постепенно угасают в памяти общества? Андерсон и Шулер проанализировали три примера окружающей среды современного человека на примере заголовков из The New York Times, записей разговоров родителей со своими детьми и содержимого электронного почтового ящика самого Андерсона. Во всех трех случаях они обнаружили, что одно слово с большой вероятностью будет повторено вновь сразу после того, как было произнесено, однако вероятность, что оно будет употреблено снова, со временем уменьшается.