Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава

для поиска соответствий в гораздо большем масштабе. Например, представьте, что вы хотите перейти на веб-сайт — допустим, http://adit.io. Ваш компьютер должен преобразовать символическое имя adit.io в IP-адрес.

Для любого посещаемого веб-сайта его имя преобразуется в IP-адрес:

Связать символическое имя с IP-адресом? Идеальная задача для хеш-таблиц! Этот процесс называется преобразованием DNS. Хеш-таблицы — всего лишь один из способов реализации этой функциональности.

Исключение дубликатов

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

Если имя входит в список, значит, этот человек уже проголосовал — гоните наглеца! В противном случае вы добавляете имя в список и разрешаете ему проголосовать. Теперь предположим, что желающих проголосовать много и список уже проголосовавших достаточно велик.

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

Сначала создадим хеш для хранения информации об уже проголосовавших людях:

>>> voted = {}

Когда кто-то приходит голосовать, проверьте, присутствует ли его имя в хеше:

>>> value = voted.get("tom")

Функция get возвращает значение, если ключ "tom" присутствует в хеш-таблице. В противном случае возвращается None. С помощью этой функции можно проверить, голосовал избиратель ранее или нет!

Код выглядит так:

voted = {}

def check_voter(name):

  if voted.get(name):

    print "kick them out!"

  else:

    voted[name] = True

    print "let them vote!"

Давайте протестируем его на нескольких примерах:

>>> check_voter("tom")

let them vote!

>>> check_voter("mike")

let them vote!

>>> check_voter("mike")

kick them out!

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

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

Использование хеш-таблицы как кэша

Последний пример: кэширование. Если вы работаете над созданием веб-сайтов, вероятно, вы уже слышали о пользе кэширования. Общая идея кэширования такова: допустим, вы заходите на сайт facebook.com:

1. Вы обращаетесь с запросом к серверу Face­book.

2. Сервер ненадолго задумывается, генерирует веб-страницу и отправляет ее вам.

3. Вы получаете веб-страницу.

Например, на Facebook сервер может собирать информацию о действиях всех ваших друзей, чтобы представить ее вам. На то, чтобы собрать всю информацию и передать ее вам, требуется пара секунд. С точки зрения пользователя, пара секунд — это очень долго. Он начинает думать: «Почему Facebook работает так медленно?» С другой стороны, серверам Facebook приходится обслуживать миллионы людей, и эти пары секунд для них суммируются. Серверы Facebook трудятся в полную силу, чтобы сгенерировать все эти страницы. Нельзя ли как-то ускорить работу Facebook при том, чтобы серверы выполняли меньше работы?

Представьте, что у вас есть племянница, которая пристает к вам с вопросами о планетах: «Сколько километров от Земли до Марса?», «А сколько километров до Луны?», «А до Юпитера?» Каждый раз вы вводите запрос в Google и сообщаете ей ответ. На это уходит пара минут. А теперь представьте, что она всегда спрашивает: «Сколько километров от Земли до Луны?» Довольно быстро вы запоминаете, что Луна находится на расстоянии 384 400 километров от Земли. Искать информацию в Google не нужно… вы просто запоминаете и выдаете ответ. Вот так работает механизм кэширования: сайт просто запоминает данные, вместо того чтобы пересчитывать их заново.

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

Такой механизм хранения называется кэшированием. Он обладает двумя преимуществами:

• вы получаете веб-страницу намного быстрее, как и в том случае, когда вы запомнили расстояние от Земли до Луны. Когда племянница в следующий раз задаст вопрос, вам не придется гуглить. Вы можете выдать ответ мгновенно;

• Facebook приходится выполнять меньше работы.

Кэширование — стандартный способ ускорения работы. Все крупные веб-сайты применяют кэширование. А кэшируемые данные хранятся в хеше!

Facebook не просто кэширует домашнюю страницу. Также кэшируются страницы «О нас», «Условия использования» и многие другие. Следовательно, необходимо создать связь URL-адреса страницы и данных страницы.

Когда вы посещаете страницу на сайте Facebook, сайт сначала проверяет, хранится ли страница в хеше.

Вот как это выглядит в коде:

cache = {}

def get_page(url):

  if cache.get(url):

    return cache[url]      Возвращаются кэшированныеданные

  else:

    data = get_data_from_server(url)