Книга «Продвинутые алгоритмы и структуры данных»
Привет, Хаброжители!
Познакомьтесь с самыми необходимыми алгоритмами решения сложных задач программирования в области анализа данных, машинного обучения и графов.
Вы постоянно сталкиваетесь с бесчисленными проблемами программирования, которые поначалу кажутся запутанными, трудными или нерешаемыми. Не отчаивайтесь! Многие из «новых» проблем уже имеют проверенные временем решения. Эффективные подходы к решению широкого спектра сложных задач кодирования легко адаптировать и применять в собственных приложениях, а при необходимости создавать собственные структуры данных под конкретную задачу. Сбалансированное сочетание классических, продвинутых и новых алгоритмов обновит ваш инструментарий программирования, добавив в него новые перспективы и практические методы.
- Хорошо знаете математику, в частности алгебру. Это поможет вам понять теоретические разделы. Тем не менее в приложении Б содержится краткое введение в нотацию «О большое» и асимптотический анализ.
- Посещали вводный курс по информатике или даже по алгоритмам. Тогда вы уже знакомы с базовыми структурами данных, которые станут основой обсуждений в этой книге.
- Знакомы с такими понятиями, необходимыми для полного понимания структур данных, как:
— основные структуры для хранения данных, такие как массивы и связные списки;
— хеш-таблицы и хеширование;
— деревья;
— контейнеры (очереди и стеки);
— основы рекурсии.
4.6 РЕАЛИЗАЦИЯ
Достаточно теории; пришло время заняться практикой! Как и ранее, в последующих разделах рассмотрим фрагменты псевдокода и исследуем его ключевые моменты. Тривиальные методы будут опущены. В репозитории книги на GitHub можно найти полный код реализаций вместе с модульными тестами.
4.6.1. Использование фильтра Блума
Вернемся к примеру обработки контактов: можно ли применять фильтр Блума, чтобы ускорить работу с контактами? Как уже упоминалось, необходимо использовать список подобно словарю, поэтому создадим новый фильтр Блума, получим список контактов с сервера и добавим их в фильтр Блума. В листинге 4.1 показана обобщенная реализация этого процесса инициализации.
Кроме настройки приложения, немалый интерес представляют две операции: проверка наличия контакта в списке и добавление нового контакта.
При выполнении первой операции (листинг 4.2) проверяется фильтр Блума, и если выяснится, что контакт никогда не добавлялся, то можно с уверенностью утверждать, что контакт отсутствует в системе. Однако если фильтр Блума возвращает true, то это может быть ложным срабатыванием, тогда нужно связаться с сервером для перепроверки.
Для добавления новых контактов всегда необходимо выполнять синхронизацию с хранилищем, как показано в листинге 4.3. Поскольку это, возможно, подразумевает удаленное соединение через сеть, существует немалая вероятность того, что обращение к серверу завершится неудачей; поэтому прежде, чем обновлять фильтр Блума, нужно обработать возможные сбои и убедиться, что удаленный вызов прошел успешно.
Для большей точности в реальных реализациях также следует синхронизировать доступ к серверу и фильтру Блума, используя механизм блокировки (см. главу 7) и заключать всю операцию в блок try-catch, откатывая (или повторяя попытку) если вызов был неудачным.
4.6.2. Чтение и запись битов
Теперь перейдем к реализации фильтра Блума и, как обычно, начнем со вспомогательных методов — основных строительных блоков, необходимых для реализации API.
В частности, нам понадобятся:
- возможность читать и писать биты в любом месте буфера нашего фильтра;
- возможность отображать ключи в индексы битов в буфере;
- набор детерминированно сгенерированных хеш-функций для преобразования ключей в список индексов.
Напомню, что фильтры Блума используются для экономии памяти, поэтому хранить биты неэффективно, это противоречит логике. Необходимо упаковать биты в наименьший целочисленный тип, доступный в выбранном языке программирования, и соответственно для чтения и записи битов реализовать отображение индекса требуемого бита в пару целых чисел.
На самом деле в современных языках программирования эти операции можно ускорить, используя числовые массивы фиксированного размера и векторную алгебру.
При этом, получив запрос на доступ к i-му биту в фильтре, следует по индексу i определить две координаты: номер элемента в массиве, где хранится i-й бит, и номер бита в этом элементе.
В листинге 4.4 показано, как можно вычислить эти координаты.
Получив эти два индекса, можно прочитать или записать любой бит; для этого достаточно прибегнуть к операциям битовой арифметики. Например, в листинге 4.5 показан метод readBit, отвечающий за чтение.
В листинге 4.6 показан аналогичный метод записи writeBit. Возможно, вас удивит, что методу не передается значение записываемого бита, но, учитывая, что фильтр Блума (по крайней мере, эта его версия) не поддерживает удаление элементов, записываться может только значение 1.
Посмотрим, как работают методы readBit и writeBit. Предположим, у нас есть такой буфер: B=[157, 25, 44, 204] и BITS_PER_INT=8.
Вызываем readBit (B, 19) и получаем, что искомый бит находится в: element==2, bit==3.
Следовательно:
И метод readBit вернет 1.
Выполняя вызов writeBit (B, 15), получаем: element==1, bit==7.
Следовательно:
И буфер изменится так: B=[157, 153, 44, 204].
4.6.3. Поиск места, где хранится ключ
Чтобы получить индексы всех битов, используемых для хранения ключа, нужно выполнить двухэтапный процесс, описанный в листинге 4.7.
Имейте в виду, что наша конечная цель — преобразовать строку в k позиций, между 0 и m — 1.
Прежде всего будем использовать две хеш-функции для строк, сильно отличающиеся друг от друга: функцию murmur-хеширования и функцию хеширования fnv1. Вероятность, что для данной строки обе дадут один и тот же результат, чрезвычайно мала.
Для каждой из k позиций получаем соответствующую хеш-функцию из нашего пула. Для каждой позиции i между 0 и k — 1 генерируем (при инициализации) функцию двойного хеширования hi. Таким образом, для i-го бита будет получена функция hi (hM, hF), где hM — результат murmur-хеширования входного ключа, а hF — результат хеширования fnv1.
Наивысший уровень рандомизации можно было бы получить, выбирая случайное начальное значение в каждом прогоне, но для нас важнее детерминированное поведение, чтобы иметь возможность тестировать или воссоздавать фильтр Блума из сериализованного представления для поддержки быстрого перезапуска в случае сбоя. Следовательно, необходимо предусмотреть возможность передачи начального значения конструктору фильтра Блума.
4.6.4. Генерирование хеш-функций
В листинге 4.7 отмечено, что при вызове метода key2Positions ему передается массив хеш-функций, и затем он используется для преобразования ключа в список индексов: позиций в битовом массиве фильтра, где хранится ключ. Теперь пришло время посмотреть, как инициализируются эти k хеш-функций (листинг 4.8), необходимых для отображения каждого ключа (уже преобразованного в строку) в набор k индексов, определяющих биты с информацией о ключе (хранимом или нет).
Набор функций создается с использованием двойного хеширования для объединения двух аргументов k различными способами. По сравнению с линейным или квадратичным хешированием, двойное хеширование увеличит количество возможных хеш-функций с O (k) до O (k2). Конечно, это количество далеко от идеала O (k! ), гарантированного равномерным хешированием, но на практике оно достаточно близко к желаемому (что означает низкий уровень конфликтов).
4.6.5. Конструктор
Теперь перейдем к общедоступному API, отражающему API множества set, который был определен в подразделе 4.3.3. Начнем с конструктора.
Как это часто бывает, конструктор содержит в основном шаблонный код для настройки внутреннего состояния фильтра Блума. В этом случае, однако, выполняются некоторые нетривиальные действия, связанные с вычислением объемов ресурсов. Эти операции нужно выделить, чтобы контейнер соответствовал точности, требуемой клиентом.
В листинге 4.9 показана возможная реализация конструктора. Обратите внимание, в частности, на строки 5 и 8, где вычисляются количество битов и количество хеш-функций соответственно. Они необходимы, чтобы оценить желаемую долю ложноположительных результатов в пределах допуска, заданного параметром maxTolerance, и, соответственно, определить количество элементов массива (строка 9), необходимых для хранения фильтра. Здесь предполагается, что массив состоит из целых чисел, а BITS_PER_INT — это системная переменная, определяющая размер целых чисел в битах. Очевидно, что для языков, поддерживающих несколько целочисленных типов, можно использовать массивы байтов, если они доступны.
На этапе создания достаточно знать только максимальное количество элементов, которое, как ожидается, будет содержать фильтр. Если в какой-то момент мы поймем, что сохранили в фильтре больше элементов, чем maxSize, то будем знать, что места хватит, и это хорошо, но при этом мы не сможем гарантировать ожидаемую точность, и это плохо.
Учитывая сказанное выше, можно передать необязательный второй параметр, чтобы гарантировать ожидаемую точность. По умолчанию порог вероятности ложноположительных результатов (maxTolerance) установлен равным 1%, но можно добиться большей точности, передав меньшее значение, или согласиться на худшую точность в обмен на меньшее потребление памяти.
Последний необязательный параметр необходим, как объяснялось в предыдущем разделе, чтобы обеспечить детерминированное поведение фильтра. Если вызывающая сторона опустит его, то будет выбрано случайное начальное значение.
После проверки полученных аргументов (в листинге 4.9 проверки опущены) выполняется настройка базовых полей. Затем наступает самая сложная часть: исходя из заданного количества элементов и ожидаемой точности вычисляется размер буфера. Здесь используется формула, описанная в разделе 4.10, но нужно убедиться, что размер буфера сможет разместиться в отведенной памяти.
Получив размер буфера, вычисляем оптимальное количество хешей, необходимых для поддержания уровня ложноположительных результатов на минимально возможном уровне.
Марчелло Ла Рокка — старший инженер-программист в Tundra.com. В фокусе его профессиональных интересов находятся графы, алгоритмы оптимизации, генетические алгоритмы, машинное обучение и квантовые вычисления. Он участвовал в разработке крупномасштабных веб-приложений и инфраструктур данных в таких компаниях, как Twitter, Microsoft и Apple, проводил прикладные исследования как в научной сфере, так и в промышленной. Марчелло придумал и реализовал алгоритм адаптивной сортировки NeatSort.
Более подробно с книгой можно ознакомиться на сайте издательства:
» Оглавление
» Отрывок
По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Алгоритмы
