Двоичная куча - это классическая структура данных, обычно используемая для отслеживания рабочего минимума или рабочего максимума в потоке вставок и извлечений. Мы попытались расширить его с помощью методов машинного обучения, чтобы ускорить его обычные операции. Наша расширенная куча сделала на 55% меньше сравнений в K-way Merge и дала многообещающие результаты при решении игры с 15 головоломками.

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

Работа была выполнена Адибом Хасаном и Ангелосом Пелеканосом в рамках нашего заключительного проекта для класса 6.890 Массачусетского технологического института по алгоритмам с расширенным обучением, который преподавали проф. Даскалакис и проф. Индик весной 2019 г. Наш окончательный отчет по этому занятию можно найти здесь: "отчет о проекте".

Быстрый обзор двоичных куч

Двоичная куча - это древовидная структура данных. Он хранит все элементы в полном двоичном дереве, так что каждый узел удовлетворяет следующему свойству heap:

  • В максимальной куче значение на каждом узле должно быть меньше или равно значению на его родительском узле.
  • В минимальной куче значение на каждом узле должно быть больше или равно значению на его родительском узле.

Двоичная куча поддерживает три операции:

  • Heapify: учитывая список из n элементов, создайте из них максимальную / минимальную кучу.
  • Insert: вставляет значение x в кучу. Значение x добавляется к нижнему слою кучи. Если свойство кучи нарушено, x заменяется местами своего родителя до тех пор, пока свойство кучи не будет восстановлено.
  • Извлечь: удаляет максимальное / минимальное значение x * из кучи. Значение x * находится в корне. Он заменяется последним элементом нижнего слоя y. Затем x * удаляется из кучи, а y заменяется его дочерним элементом max / min до тех пор, пока свойство кучи не будет восстановлено.

Первый занимает O (n) времени, а два последних - O (log n) времени, где n - количество элементов в данный момент в куче. Также обратите внимание, что max heaps и min hips эквивалентны с алгоритмической точки зрения. Следовательно, оставшаяся часть статьи будет посвящена обсуждению максимальных куч.

Выявление узкого места

  • Вставка. Обратите внимание, что 87,5% элементов кучи находятся в трех нижних слоях кучи. Таким образом, вставка случайного элемента в среднем довольно эффективна. Однако, если наши вставленные элементы имеют тенденцию увеличиваться со временем (например, при использовании A * для решения лабиринта, метрика наших позиций имеет тенденцию увеличиваться по мере приближения к нашей цели), вставки должны будут проходить полностью до верхние слои кучи. Это делает вставки неэффективными.
  • Извлечение: при извлечении максимального элемента он заменяется последним элементом нижнего слоя. Этот предмет относительно небольшой. Чтобы восстановить свойство кучи, его нужно снова нажать на нижнюю часть кучи. Это делает добычу дорогостоящей.

Это дает нам идею: заменить дорогие вставки и извлечения недорогими.

Создание ярлыков

Наша основная идея - создать в куче пустое место, то есть «узлы быстрого доступа». Мы можем объединить эти узлы ярлыков с оракулом машинного обучения, чтобы предсказать «узел ярлыков» для каждого вставленного значения. Мы надеемся, что оракул машинного обучения спрогнозирует правильный «узел быстрого доступа» и поместив туда вставленное значение, восстановит свойство кучи. К сожалению, мы не можем этого гарантировать, и поэтому после помещения вставленного значения в «узел ярлыка» нам могут потребоваться дополнительные перестановки вверх или вниз по куче, пока свойство кучи не будет восстановлено. Обратите внимание, что количество необходимых свопов и сравнений ограничено сверху значением O (log n), как и для обычной двоичной кучи. Если наш оракул машинного обучения будет успешно обучен, мы ожидаем гораздо меньше. «Узлы быстрого доступа» строятся в дереве с использованием следующей стратегии:

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

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

  • Освободите место на верхних слоях кучи. Однако убедитесь, что вытолкнутые элементы равномерно распределены по куче.
  • Теперь для каждого вставленного элемента, если он кажется «достаточно большим», используйте «ярлык», чтобы вставить его. Слегка сдвиньте вверх / вниз, чтобы восстановить свойство кучи.
  • В противном случае просто делайте обычные прошивки.
  • Если у вас закончились свободные места, создайте больше.

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

Эксперименты

K-образное слияние

K-way Merge - это алгоритм, обычно используемый для сортировки больших коллекций элементов. Он работает так, что он разбивает коллекцию на K частей, которые сортируются независимо (возможно, путем рекурсивного вызова K-way Merge). Затем полученные K отсортированных коллекций объединяются вместе, сохраняя двоичную кучу с первыми элементами каждой коллекции. На каждой итерации из кучи извлекается новый элемент и помещается в отсортированный результат. Кроме того, в двоичную кучу вставляется следующий элемент из исходной коллекции извлеченного элемента. Заинтересованные читатели могут прочитать статью Википедии.

Мы реализовали K-way Merge и сравнили производительность алгоритма с исходной двоичной кучей с нашей расширенной двоичной кучей.

15-Головоломка с использованием A * Search

The 15-Puzzle - игра, в которой используются скользящие блоки с целью упорядочить блоки в порядке возрастания. Простой алгоритм, который используется для решения подобных задач, - это поиск A *. A * search - это модифицированный алгоритм поиска в глубину в пространстве состояний игры, который отдает приоритет исследованию состояний, которые ближе к целевому состоянию в соответствии с некоторой метрикой. Для того, чтобы упорядочить возможные состояния и всегда выбирать лучшее для исследования следующим, для алгоритма необходима двоичная куча.

Мы снова реализовали две версии A * Search для решения игры «15 головоломок» и сравнили реализацию с исходной двоичной кучей с нашей реализацией расширенной двоичной кучи.

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

Дальнейшая работа

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

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

Если читатель заинтересован в том, чтобы помочь нам осуществить вторую фазу этого проекта, вы можете отправить нам электронное письмо.