Monthly Archives: Декабрь 2013

Граница Парето в 3D за O(NlogN) время

Продолжая тему поста «Граница Парето в 2D за O(NlogN) или O(N) время«, я решил реализовать и опубликовать аналог в трёхмерном пространстве (обобщение на три показателя качества). Соответствующий алгоритм также описан в книге Препараты и Шеймоса «Вычислительная геометрия: Введение» вслед за двумерным алгоритмом. Алгоритм основан на принципе заметания объёма плоскостью.

  1. Отсортировать точки по координате z.
  2. Проходя точки в порядке сортировки от максимального значения координаты z до минимального, добавлять их в статус заметающей плоскости.

Статус плоскости хранит упорядочение (например, по координате x) подмножества доминирующих точек и представляет собой сечение плоскостью z = const области пространства, доминируемой перебранными на данный момент точками («лесенку», см. рисунок ниже). При добавлении новой точки P в статус:

  1. Ищем в статусе точку R, ближайшую справа к P.
    • Если она лежит выше P, то отбрасываем P и выходим.
    • Если её нет, либо она лежит ниже P, то вставляем P в статус и переходим к п.2.
  2. Ищем в статусе точку L, ближайшую слева к P и находящуюся выше P.
  3. Удаляем из статуса все точки в интервале (L, P). Если L не найдена, то удаляются все точки слева от P.
  4. Сообщаем P как недоминируемый элемент.

граница Парето 3D статус

Статус может быть реализован в виде сбалансированного двоичного дерева (желательно, прошитого, возможно, уложенного в массив), тогда, как нетрудно видеть, алгоритм найдёт все недоминируемые точки за O(NlogN) время. Была написана реализация на C++, позволяющая реализовать статус в виде политики, передаваемой параметром шаблона, либо воспользоваться std::set или любым совместимым аналогом.

Xprer

Недавно возникла забавная задачка. Предположим, некий софт накапливает данные в файле. Иногда происходят сбои, и данные начинают записываться повторно в конец файла так, что результирующую структуру файла можно представить в виде трёх участков alpha alpha beta, где alpha — дублирующаяся последовательность байт (префикс). Корректный файл выглядит как alpha beta. Итак, задача: отбросить максимальный дублирующийся префикс в заданном файле за приемлемое время (файл может быть размером в десяток гигабайт).

Для решения данной задачи я написал небольшую консольную утилиту xprer «maXimal PREfix Reduction» (сборка под Windows x86-64, Microsoft Visual C++ 2013 runtime), принимающую один или два параметра командной строки: имя исходного файла и необязательное имя результирующего файла. Если имя результирующего файла не задано, то результат записывается в файл xprer.out.имя исходного файла.

Реализация утилиты использует стандартную библиотеку C++. Исходный код доступен здесь. Для поиска совпадения префикса используется подход, аналогичный алгоритму поиска подстроки Рабина-Карпа. Используется кольцевой хэш на основе суммы и суммы сумм (похож на Adler32, но имеет длину 64 бита и вычисляется по модулю 232).

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

Граница Парето в 2D за O(NlogN) или O(N) время

Постановка задачи

Предположим, что есть набор из N возможных решений {pi} некоторой задачи, и заданы показатели качества f1(p) → max и f2(p) → max, таким образом, каждому pi соответствует некоторая точка xi = (f1(pi), f2(pi)) на плоскости. Предположим, что заранее мы не можем решить, какой из показателей важнее, или как свести два показателя к одному общему, но мы можем заранее убрать из рассмотрения заведомо проигрышные решения pj, т.е. такие, для которых мы можем подобрать некоторое pk: f1(pj) ≤ f1(pk) и f2(pj) ≤ f2(pk). Тогда соответствующий набор оставшихся xk составит «границу Парето» исходного набора точек.

Очевидно, что мы можем сделать это за O(N2)-время, сравнив все значения показателей для решений попарно. Несколько лет назад мне понадобилось решать эту задачу в качестве подзадачи. Тогда я разработал для её решения алгоритм, работающий за O(NlogN)-время с помощью сортировки. Недавно мне пришлось вспомнить тот результат, кроме того, я решил обратиться к литературе по вычислительной геометрии и нашёл тот самый алгоритм в классической книге Препараты и Шеймоса «Вычислительная геометрия: Введение» (М.: Мир, 1989, с.194-195), где данная задача названа задачей «о поиске максимумов множества точек». Позволю себе высказать одно замечание. Для этого мне необходимо процитировать вводную часть из книги (с.192).

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

Далее в книге приведена формальная постановка задачи. Что интересно, указанная неформальная постановка относится к совсем другой (хотя и похожей внешне) задаче — задаче о выпуклой оболочке. Это станет очевидным, если её формализовать корректно: пусть vi — это количество дензнаков i-й валюты, ci — курс i-й валюты в некоторых условных единицах (в конце концов, всегда можно взять некоторую валюту за единицу, у неё ci = 1), тогда стоимость пакета v есть скалярное произведение векторов (vi) и (ci). Это будет максимизируемый показатель качества (см. опорная функция). Ниже показана иллюстрация с тремя «пакетами», где все три пакета являются элементами границы Парето, но «средний» из них не будет решением задачи о потенциальных королях Эревона (показано три возможных вектора).

(иллюстрация)

Итак, пусть заданы бинарные предикаты Sl, l=1..n, каждый из которых удовлетворяет аксиомам нестрогого порядка. Частным случаем таких предикатов могут быть операции сравнения точек по значению фиксированной координаты на «меньше или равно».

Определение. Элемент p доминирует элемент q, если Sl(q, p) для всех l.

Задача. Найти все p из набора pi, i=1..N, такие, что для любого j из 1..N : pj ≠ p ⇒ pj не доминирует p (для простоты формулировки задачи положим, что набор pi не содержит дубликатов, представленный ниже алгоритм отбрасывает дубликаты).

Алгоритм

Решение указанной задачи для случая n=2 (в частности, для точек на плоскости) основывается на том наблюдении, что если некоторый p находится «левее» (S1) некоторого q, то из недоминирования q над p следует, что p должен находиться «выше» (S2) q. Аналогично, некоторый r, находящийся «левее» p, должен быть «выше» p. Пусть процедура report(p) сообщает p в качестве одного из элементов решения.

  1. Переномеруем (отсортируем) pi так, чтобы для любого i=1..(N-1) и любого j=(i+1)..N было верно S1(pi, pj).
  2. Положим max=pN; report(max).
  3. Для i=(N-1)..1: если S1(max, pi), то max=pi; report(max).

граница Парето алгоритм 2D

Данный довольно простой алгоритм демонстрирует один из базовых приёмов вычислительной геометрии — «заметание» (плоскости прямой) в его простейшей форме.

Обобщённая реализация данного алгоритма на C++ здесь.

Простой анализ алгоритма даёт O(NlogN)-время для произвольного предиката S1 (сортировка с предикатом) и O(N)-память для хранения результата сортировки для последующего заметания. В случае, если pi можно отобразить в точки xi=(f1(pi), f2(pi)) на плоскости, заданные с ограниченной точностью, и сравнивать покоординатно, то сортировку можно выполнить за O(N)-время (например, с помощью блочной или поразрядной сортировок).