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

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

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

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

Глубоко в дебрях библиотеки Гарднер Стакс в Калифорнийском университете в Беркли, за закрытыми дверями с большой табличкой «Вход только для персонала», располагается одна из жемчужин библиотечной системы университета. Кормак Маккарти, Томас Пинчон, Элизабет Бишоп, Дж. Д. Сэлинджер; Анаис Нин, Сьюзан Зонтаг, Хунот Диас и Майкл Шейбон; Энни Пру, Марк Стрэнд и Филип К. Дик; Уильям Карлос Уильямс, Чак Паланик и Тони Моррисон; Дэнис Джонсон, Джулиана Спар, Джори Грэм и Дэвид Седарис; Сильвия Плат, Дэвид Мэмет, Дэвид Фостер Воллас и Нил Гейман… Это не коллекция редких книг библиотеки. Это ее кеш.

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

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

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

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

Тем временем в зале студенческой Библиотеки Моффит, где находятся наиболее значимые и доступные книжные полки, демонстрационные стенды заполнены недавно поступившими в библиотеку книгами. Этот случай демонстрирует применение метода «первым вошел, первым вышел», когда в привилегированном положении оказываются книги, которые были последними добавлены в библиотеку, а не последними прочтены.

Результаты большинства тестов, с помощью которых ученые пытались оценить основную эффективность алгоритма замещения по давности использования, продиктовали простое решение: вывернуть библиотеку наизнанку. Поставьте последние поступившие в библиотеку издания в самый угол для тех, кто хочет их найти. А затем разместите недавно возвращенные книги в зале библиотеки, где они будут доступны для всеобщего обозрения.

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

Однако такая система была бы не только более позитивной в социальном плане. Поскольку крайне вероятно, что именно последние возвращенные в библиотеку книги и станут объектом поиска новых посетителей библиотеки, эта система, скорее всего, показала бы еще и свою эффективность. Действительно, студенты могут быть озадачены тем фактом, что иногда популярные книги они могут найти только в книгохранилище, а иногда – в зале. Однако недавно возвращенные книги, которые еще не успели вернуться на полки, в хранилище тоже отсутствуют. Пока они находятся в этом кратковременном заточении, они недоступны. Если позволить недавно вернувшимся книгам украсить своим присутствием холл библиотеки, это даст возможность студентам полностью замкнуть процесс наполнения полок. Сотрудникам библиотеки больше не придется блуждать по книгохранилищу, чтобы разместить книги, а студентам – чтобы их потом отыскать. Вот как в точности должен работать кеш.