Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - [15]

Шрифт
Интервал

. Оно может стать и пороком, и добродетелью, в зависимости от того, как ее использовать.

9

Как починить ожерелье?

Джо – независимая ремесленница. Она продает свои поделки на рынке в Нью-Мехико, или на Индейском рынке, как его часто называют на рекламных плакатах. Много лет она страдает от ревматоидного артрита, поэтому ей все труднее зарабатывать на жизнь. Ее работа связана с ручным трудом: она изготавливает на заказ ожерелья с именами. Прилавок Джо расположен рядом со входом на рынок, и она убеждает каждого посетителя, что лучший подарок, который можно купить на рынке, это ожерелье с именем любимого человека или своим собственным.

Маленькая девочка поддалась на ее уговоры. «Меня зовут Жаклин», – говорит она. Джо приступает к работе, нанизывая бусины на простой кусок шпагата, к которому на концах приклеивается застежка. Она отдает законченную вещь девочке, но та мотает головой. Ей не нравится ожерелье. «Простите, но в моем имени две буквы «к». Разве вы не знали, что детям теперь модно давать оригинальные имена?» Бедная Джо!

В главе 1 мы говорили о массивах как о способе хранить группы элементов, которые могут быть быстро просмотрены в линейном времени. А в главе 3 мы узнали, что есть алгоритмы для выполнения заданий, на которые уходит постоянное количество времени независимо от величины задания. Сейчас мы поговорим об алгоритме, который концентрируется на возможности добавлять и удалять элементы в любых точках и за постоянное время. Для начала давайте рассмотрим два способа, при помощи которых Джо может исправить ожерелье Жаклин.


ЦЕЛЬ: ДОБАВИТЬ ШАРИК С ПРОПУЩЕННОЙ БУКВОЙ НА ОЖЕРЕЛЬЕ.

МЕТОД 1: РАССТЕГНУТЬ ОЖЕРЕЛЬЕ, УДАЛИТЬ ВСЕ БУСИНЫ, ПОКА НЕ ДОБЕРЕШЬСЯ ДО БУКВЫ «К» ИЛИ «Л». ДОБАВИТЬ ПРОПУЩЕННУЮ БУКВУ, НАНИЗАТЬ ОСТАЛЬНЫЕ БУСИНЫ.

МЕТОД 2: РАЗРЕЗАТЬ ОЖЕРЕЛЬЕ МЕЖДУ БУКВАМИ «К» И «Л». ВСТАВИТЬ БУКУ «К» НА ЛЮБОЙ ИЗ ОТРЕЗКОВ. СКРЕПИТЬ ШПАГАТ КЛЕЕМ.

У массивов есть недостатки – элементы, которые появляются рядом друг с другом, так же рядом и хранятся в памяти. Если возникает необходимость вставить новый элемент между двумя другими, мы не можем сделать это просто так: нам придется сдвинуть все элементы, расположенные после этой точки, чтобы освободить место для нового. Так поступают в соответствии с методом 1. Джо нужно по очереди удалить бусины с любого конца ожерелья, пока она не доберется до места, где должна стоять дополнительная бусина. Потом она нанизывает ее на шпагат и ставит на место все остальные. Процесс займет вдвое больше времени, если имя заказчика будет длиннее в два раза.[38]

Новизна метода 2 состоит в том, что кусок шпагата может быть разрезан в любой точке и затем связан или склеен. Это важное свойство шпагата, потому что – и в этом мы сейчас убедимся – оно позволяет нам устранить главный недостаток массивов, в которых добавление или удаление элемента означает высокие трудозатраты. До определенного момента метод 1 может оказаться лучшим: чего стоит удаление одной-двух бусин по сравнению с разрезанием шпагата и связыванием двух концов? Но вряд ли его преимущество сохранится, если в ожерелье окажется больше бусин.

В информатике существует структура, которая проявляет именно это свойство, и вот как она выглядит:

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

Эта структура, разработанная еще в 50-е годы, известна под названием связный список. Она стала основой для многих приложений в вычислительной технике из-за ее эффективности при вставке и удалении элементов из группы в заданной точке. Например, в главе 8 мы упомянули, что принтер может ставить задания в очередь, хранить их в списке и решать, поместить ли менее объемные задания перед другими. Эффективным способом для этого будет создание очереди с использованием связного списка.

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

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

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


Рекомендуем почитать
Мегатренинг для развития мозга, воли, памяти. Упражнения для ума, которые используют миллионеры и чемпионы

Автор этой книги – бывший сотрудник ФБР, а сегодня знаменитый тренер, воспитывающий победителей в спорте и в жизни. Эта удивительная книга учит, как занесколько секунд войти в состояние наивысшей производительности мозга.Перед вами настоящая методика чемпионства! В ее основе – исследования спортивной психологии, НЛП, восточные практики концентрации.По этой книге учатся политики и актеры, преуспевающие адвокаты и топ-менеджеры. Любой, кто хочет достигнуть выдающихся результатов на игровом поле, в бизнесе или в жизни, теперь сможет овладеть «боевым методом мгновенной концентрации внимания и мышления» и добиться грандиозного успеха!


24 сверхспособности. Гениальность по-французски!

Мадам, вы такая умница! Вы настоящий гений, месье! Не верите? Напрасно.Флоранс Серван-Шрейбер, автор этой книги, знает, что внутри каждого из нас спокойным сном спят двадцать четыре сверхвозможности, которые могут превратить нас в миллионера или остроумного собеседника, главу корпорации или гениального оратора.В этой книге – инструкция, как разбудить эти силы. Все очень просто и действенно! И кстати, книга написана настоящей француженкой, а такая книга просто не может быть скучной и непонятной! Вы узнаете о тайнах подсознания, о скрытых возможностях вашего мозга, об источниках энергии внутри вас, и все это без напряжения и скуки, легко и даже весело! Вуаля! Будьте гениальны, умны и счастливы!


Основы системы Дизайна человека. Центры

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


Жить без негативных эмоций

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


Религиозный вопрос в XXI веке. Геополитика и кризис постмодерна

Жорж Корм – философ, экономист, автор многих замечательных книг, посвященных истории Западной Европы и стран Ближнего Востока.В этой книге он обращается к анализу подъёма религиозных настроений в последние десятилетия XX века и в начале века нынешнего. Именно они становятся сегодня доминирующим фактором мировой политики, одним из ключевых вопросов строительства современного общества и – самое главное – самой острой из существующих (наряду с проблемами окружающей среды) проблем человечества в целом и каждой страны, каждого общества в отдельности.


Феноменальный интеллект. Искусство думать эффективно

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


Стань себе родителем: как исцелить своего внутреннего ребенка и по-настоящему полюбить себя

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


Рестарт. Как вырваться из «дня сурка» и начать жить

Порой наша жизнь начинает напоминать «день сурка», вновь и вновь проигрывающий все тот же сценарий «дом–работа–дом». Если вы устали каждый день проводить без смысла и радости, делать то, что вам совсем не хочется, эта книга для вас! По мнению Татьяны Ананьевой, признанного эксперта в области HR и маркетинга, консультанта ведущих компаний страны, в основе счастливой и гармоничной жизни лежит принцип осознанности и четкое понимание своих желаний. В легкой и доступной форме она рассказывает, как научиться управлять своей жизнью и обрести внутренний баланс и равновесие, стать счастливее в работе и в жизни. Из этой книги вы узнаете: [ul]Как найти свою мечту и реализовать ее; Почему нам так трудно избавиться от шаблонов и что с этим делать; Как научиться делать шаг к цели каждый день; Чем отличается подход к работе у разных поколений; Как избежать типичных ошибок в планировании.[/ul].


Синдром самозванца. Как перестать обесценивать свои успехи и постоянно доказывать себе и другим, что ты достоин

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


Предназначение. Найти дело жизни и реализовать свои мечты

У каждого есть Предназначение. Не следовать ему – самое большое преступление. Отсутствие четкого понимания своего пути делает людей несчастными и бедными. Александр Рей – практикующий психолог и просто счастливый человек. Он написал книгу-тренинг «Предназначение» для того, чтобы без пустых теорий и рассуждений помочь вам осознать свою миссию и немедленно приступить к ее осуществлению.