Текст книги "Алгоритмы для жизни: Простые способы принимать верные решения"

Кровавая сортировка: неофициальная иерархия и доминирование

Во всех примерах, рассмотренных до сих пор, процесс сортировки в каждом случае происходил сверху вниз: библиотекарь расставлял книги на полке, Национальная ассоциация студенческого спорта указывала командам, когда и с кем играть. Но что, если такие сравнения происходили бы только на добровольной основе? Как бы выглядела сортировка, если бы она производилась более органично – снизу вверх?

Для ответа на этот вопрос рассмотрим игру в онлайн-покер.

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

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

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

Так что же происходит, если установлен некий необъявленный консенсус и никто не желает демонстрировать, что он играет лучше, чем кто-либо другой? Тогда это выглядит так, как будто игроки просто соревнуются в борьбе за место. Большинство сайтов для игры в онлайн-покер имеют лишь конечное число доступных мест. «Так что, если вы хотите играть, оперируя блайндами в 50 и 100 долларов, в вашем распоряжении только десять доступных столов, – комментирует Хакстон, – да и то подразумевается, что за столом сейчас отсутствуют десять лучших рейтинговых игроков, а все остальные сидят и ждут, что кто-то придет и покажет, что просто хочет поиграть». И если вдруг за один из этих столов приходит и садится суперигрок, тогда любой игрок, который не желает участвовать в анте, просто покидает стол.

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

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

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

Выглядит знакомо, не правда ли? Именно это называется компромиссной сортировкой.

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

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

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

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

Гонка вместо драки

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

Необязательно всегда идти этим путем. Есть и менее затратные способы навести порядок.

Существует, например, одно спортивное соревнование, в котором десятки тысяч конкурентов полностью сортируются в течение ровно того времени, которое требуется для проведения этого мероприятия. (При этом мы должны помнить, что проведение турнира с 10 тысячами участников по цикличному алгоритму требует около 100 миллионов матчей.) Единственный нюанс состоит в том, что длительность такого турнира определяется его самыми медленными участниками. Это спортивное соревнование называется марафон. И здесь возникает критический момент: гонка принципиально отличается от борьбы.

Давайте повнимательнее рассмотрим суть различий между боксерами и лыжниками, между фехтовальщиками и бегунами. Олимпийский боксер, чтобы подняться на подиум, не только сам рискует получить нокаут O(log n) раз (как правило, в 4–6 боях), но и подвергает риску и ставит под угрозу здоровье большого количества других спортсменов. А вот прыгуну с трамплина или фристайлеру нужно сделать лишь ограниченное число рискованных трюков, связанных с преодолением силы тяжести, причем независимо от дистанции. И если фехтовальщик отдает себя на милость противника O(log n) раз, то тот же марафонец должен выдержать только одну гонку с тем, чтобы, присвоив себе простой числовой показатель, характеризующий результат его работы в алгоритме постоянного времени, определить свой статус.

Такой переход от «порядковых» чисел (которые определяют ранг) к «количественным» показателям (которые служат прямой мерой чьих-то возможностей) естественным образом определяет порядок, в котором нет необходимости сравнивать пары. Соответственно, это делает возможным появление доминантных иерархий, которые не требуют проведения прямых матчей. Список крупнейших компаний мира Fortune 500, формирующий своего рода корпоративную иерархию, является как раз одним из таких примеров. Для того чтобы найти самую дорогую компанию Соединенных Штатов, аналитикам не нужно усердно трудиться, поочередно сравнивая Microsoft и General Motors, затем General Motors и Chevron, потом Chevron и Walmart и т. д. Эти сопоставления, казалось бы, совершенно несопоставимого (программное обеспечение и фьючерсы на нефть) становятся возможными с помощью промежуточного звена – доллара. Наличие измерительного эталона любого вида решает вычислительную задачу при расширении масштабов сортировки.

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

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

Когда мы задумываемся о факторах, которые делают возможным существование крупномасштабных человеческих сообществ, нам проще сосредоточиться на технологиях: сельское хозяйство, металлообработка, машиностроение. Но не стоит забывать и о том, что культурологический подход к измерению статуса с помощью количественных показателей также может иметь большое значение. Деньги, конечно, не должны быть критерием. Например, такое правило, как уважение к старшим, точно так же решает вопросы о статусе народа, как и отсылка к его количественной составляющей. Этот же принцип работает в спорах как между народами, так и внутри них. Часто отмечается, что такой критерий, как ВВП страны, лежащий в основе рассылки приглашений на встречи на высшем дипломатическом уровне (например, на встречу правительств G20), непродуман и неполноценен. Но тем не менее существование какого бы то ни было эталона играет важную роль, поскольку трансформирует вопрос одной из сторон о национальном статусе из линейно-логарифмического количества обсуждений и резолюций во что-то, имеющее единую точку отсчета, которой все подчиняются. Поскольку споры между народами часто переходят в военные действия, это экономит не только время, но жизни.

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

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

4. Кеширование
Забудьте об этом

С точки зрения практического использования нашего интеллекта забывание – такая же важная функция, как и запоминание.

Уильям Джеймс

У вас проблема. Ваш шкаф переполнен: ботинки, рубашки и нижнее белье – все вываливается на пол. Вы думаете, что пора бы навести порядок. Теперь у вас две проблемы.

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

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

Помимо этой группы, существует и другое сообщество экспертов, поглощенных мыслями о хранении вещей, – и у них свое видение проблемы.

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

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

То, что на самом деле там происходит, называется кешированием.

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

Иерархия памяти

У одной женщины было обостренное чувство ответственности и почти не было памяти.

Она помнила достаточно, чтобы работать. И работала она упорно.

Лидия Дэвис

Начиная примерно с 2008 года, каждый, кто хочет приобрести новый компьютер, сталкивается с определенной парадоксальной ситуацией при выборе возможностей хранения информации. Необходимо найти компромисс между объемом и скоростью. Сегодня технологии компьютерной индустрии пребывают в фазе перехода от накопителей на жестком диске к твердотельным накопителям (SSD). При одинаковой стоимости жесткий диск может продемонстрировать более высокую мощность, однако твердотельный накопитель гораздо более эффективен, и этот факт либо уже известен потребителям, либо они сами быстро приходят к такому выводу в процессе покупки.

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

В 1946 году Артур Беркс, Герман Голдстайн и Джон фон Нейман, трудясь в Институте специальных исследований в Принстоне, выработали проект предложения, который они назвали «электрический орган памяти». По их словам, в идеальном мире техника, разумеется, обладала бы безграничным количеством молниеносно работающей памяти, но на практике это невозможно (до сих пор). Вместо этого тройка экспертов предложила другой вариант, по их мнению, лучший из реальных: «иерархия слоев памяти, каждый из которых обладал бы большей мощностью, чем предыдущий, но при этом был бы менее доступным». По сути, имея пирамиду из различных форм памяти (маленькой, но быстрой и большой, но медленной), мы могли бы извлечь максимум выгоды из обоих видов. Основная идея иерархии интуитивно будет понятна любому человеку, который хоть раз пользовался библиотекой. Если вы проводите исследование для дипломной работы, вам наверняка понадобятся некоторые книги, на которые вы будете многократно ссылаться. Вместо того чтобы каждый раз идти в читальный зал, вы, разумеется, возьмете нужные книги домой, чтобы они были у вас всегда под рукой.

Идея иерархии памяти оставалась лишь теорией до изобретения суперкомпьютера, или ЭВМ сверхвысокой производительности, который получил название «Атлас» (это произошло в 1962 году в Манчестере). Основная память компьютера состояла из огромного барабана, который вращался при чтении и записи информации в отличие от его предшественника – воскового цилиндра. Однако у «Атласа» была более быстрая оперативная память меньшего объема, работающая на поляризованных магнитах. Данные считывались из цилиндра и передавались на магниты, где быстро обрабатывались, и затем результаты записывались на цилиндр. Вскоре после изобретения «Атласа» кембриджский математик Морис Вилкес пришел к выводу, что быстрая память небольшого объема – не самое подходящее место для хранения данных до их повторного сохранения на цилиндре. Оперативную память также можно было использовать для хранения фрагментов информации, которые могли бы пригодиться позднее. Ожидание аналогичных будущих запросов на эту информацию существенно ускоряло операционные процессы компьютера. Если информация, которую вы ищете, все еще находится в оперативной памяти, то вам не нужно выгружать ее из цилиндра. Как отметил Вилкес, память меньшего объема «автоматически накапливает в себе слова, которые переходят в нее из основной медленной памяти, и сохраняет их для последующего использования без необходимости вновь обращаться к основной памяти». Главное здесь, конечно, возможность использовать эту небольшую, быструю драгоценную память так, чтобы в ней всегда было то, что вам нужно, и вы могли обращаться к ней максимально часто. Если развить аналогию с библиотекой, это тот случай, когда вы можете один раз сходить за всеми нужными книгами и затем всю неделю работать с ними дома. Это так же удобно, как если бы все книги библиотеки уже лежали на вашем рабочем столе. Чем больше походов в библиотеку вы совершаете, тем больше замедляются темпы вашей работы.

Предложение Вилкеса было использовано позже, в конце 1960-х годов, когда в суперкомпьютер IBM 360/85 внедрили память, которая получила название «кеш» (быстродействующая буферная память большой емкости). С тех пор кеш повсеместно использовался в компьютерных технологиях. Идея хранения фрагментов информации, к которой пользователь обращается часто, настолько высокоэффективна, что в наши дни она используется во всех аспектах компьютерной деятельности.

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

История развития компьютерных технологий за последние пятьдесят с небольшим лет постоянно демонстрирует опережающий рост и отчасти позволяет нам сослаться на известное своей точностью предсказание, озвученное Гордоном Муром из корпорации Intel в 1975 году. Согласно этому предсказанию, количество транзисторов в компьютерном процессоре должно было удваиваться каждые два года. Тем не менее эффективность памяти при этом не прогрессировала, то есть затраты на доступ к памяти также многократно возрастали относительно времени обработки данных. Таким образом, чем быстрее вы пишете вашу дипломную работу, тем больше снижается продуктивность каждого похода в библиотеку. Аналогично эффективность завода, который удваивает скорость производства каждый год (но при этом получает все то же количество деталей из-за рубежа в прежнем неторопливом темпе), едва ли будет выше эффективности завода, работающего в два раза медленнее. Сначала казалось, что закон Мура не принес никакой пользы, кроме того что процессоры стали «простаивать» все больше и чаще. В 90-е годы эта проблема получила название «стена памяти».

Лучшим средством защиты компьютерной науки от удара об эту стену стало изобретение еще более сложной иерархии: кеш для кеша для кеша на всех уровнях памяти. Современные лэптопы, планшеты и смартфоны имеют шестиуровневую иерархию памяти, при этом экономное и разумное использование памяти еще никогда не было так важно для компьютерных технологий, как сейчас. Так давайте рассмотрим первый вопрос, который приходит на ум, когда речь заходит о кеш-памяти (или о шкафах, к примеру). Что же нам делать, когда все переполнено?