анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 8 Избранные вопросы проектирования алгоритмов В разделе 8.1 рассматриваются алгоритмы с параллельным просмотром разрядов, в которых для эффективной обработки данных используются поразрядные операции. В типичном случае мы можем заменить цикл for поразрядными операциями, что существенно уменьшает время работы алгоритма. В разделе 8.2 изложена техника амортизационного анализа, применяе- мая для оценки времени выполнения последовательности операций в ал- горитме. С помощью этой техники мы проанализируем алгоритмы нахож- дения ближайшего меньшего элемента и минимума в скользящем окне. В разделе 8.3 обсуждаются троичный поиск и другие методы эффектив- ного вычисления минимумов некоторых функций. 8.1. Алгоритмы с параллельным просмотром разрядов Алгоритмы с параллельным просмотром разрядов основаны на том факте, что отдельными разрядами числа можно манипулировать параллельно, применяя поразрядные операции. Поэтому один из способов проектиро- вания алгоритмов – представить шаги алгоритма таким образом, чтобы их можно было эффективно реализовать с помощью поразрядных операций. 8.1.1. Расстояние Хэмминга Расстоянием Хэмминга hamming (a, b)между строками a и b одинаковой длины называется количество позиций, в которых эти строки различают- ся. Например: hamming (01101, 11001) = 2. Рассмотрим следующую задачу: дано n битовых строк длины k, вычис- лить минимальное расстояние Хэмминга между двумя строками. Напри- мер, для строк [00111, 01101, 11110] ответом будет 2, потому что 8.1. Алгоритмы с параллельным просмотром разрядов 133 • hamming (00111, 01101) = 2; • hamming (00111, 11110) = 3; • hamming (01101, 11110) = 3. Задачу можно решить «в лоб», вычислив расстояние Хэмминга между каждыми двумя строками. Временная сложность такого алгоритма равна O(n 2 k). Для вычисления расстояния между строками a и b служит следую- щая функция: int hamming(string a, string b) { int d = 0; for (int i = 0; i < k; i++) { if (a[i] != b[i]) d++; } return d; } Но поскольку строки состоят из бит, решение можно оптимизировать, если хранить строки в виде целых чисел и вычислять расстояние между ними с помощью поразрядных операций. В частности, если k ≤ 32, то стро- ки можно хранить как значения типа int и для вычисления расстояния использовать такую функцию: int hamming(int a, int b) { return __builtin_popcount(a^b); } Здесь операция ИСКЛЮЧАЮЩЕЕ ИЛИ строит строку, в которой единицы находятся в тех позициях, где a и b различаются. Затем число единичных разрядов вычисляется функцией __builtin_popcount В табл. 8.1 приведены результаты сравнения исходного алгоритма и ал- горитма с параллельным просмотром разрядов с точки зрения времени выполнения на современном компьютере. Алгоритм с параллельным про- смотром разрядов оказался примерно в 20 раз быстрее. Таблица 8.1. Время работы алгоритмов, вычисляющих минимальное расстояние Хэмминга для n битовых строк длины k = 30 Размер n Исходный алгоритм (с) Алгоритм с параллельным просмотром разрядов (с) 5000 0.84 0.06 10 000 3.24 0.18 15 000 7.23 0.37 20 000 12.79 0.63 25 000 19.99 0.97 134 Глава 8. Избранные вопросы проектирования алгоритмов 8.1.2. Подсчет подсеток Рассмотрим далее такую задачу: дана сетка n×n с черными (1) и белы- ми (0) клетками, вычислить количество подсеток, у которых все угловые клетки черные. На рис. 8.1 показаны две такие подсетки. Рис. 8.1. Эта сетка содержит две подсетки с черными углами Для решения задачи существует алгоритм с временной сложностью O(n 3 ): перебрать все O(n 2 ) пар строк и для каждой пары (a, b) вычислить – за время O(n) – количество столбцов – таких, что на их пересечении со стро- ками a и b находится черная клетка. В следующем коде предполагается, что color [y ][x] – цвет клетки на пересечении строки y и столбца x: int count = 0; for (int i = 0; i < n; i++) { if (color[a][i] == 1 && color[b][i] == 1) { count++; } } Зная, что существует count столбцов, в которых обе интересующие нас клетки черные, мы можем вычислить количество искомых подсеток, в ко- торых a – первая строка, а b – вторая, по формуле count ( count − 1)/2. Чтобы построить алгоритм с параллельным просмотром разрядов, представим каждую строку k в виде битового множества длины n row [ k], в котором единицы соответствуют черным клеткам. Тогда количество столбцов, на пересечении которых со строками a и b находятся черные клетки, можно вычислить с помощью операции И и подсчета единичных разрядов. Благодаря битовым множествам это делается просто: int count = (row[a]&row[b]).count(); В табл. 8.2 приведены результаты сравнения исходного алгоритма и ал- горитма с параллельным просмотром разрядов для сеток разного разме- ра. В некоторых случаях алгоритм с параллельным просмотром разрядов оказался в 30 раз быстрее. 8.1. Алгоритмы с параллельным просмотром разрядов 135 Таблица 8.2. Время работы алгоритмов подсчета подсеток Размер сетки n Исходный алгоритм (с) Алгоритм с параллельным просмотром разрядов (с) 1000 0.65 0.05 1500 2.17 0.14 2000 5.51 0.30 2500 12.67 0.52 3000 26.36 0.87 8.1.3. Достижимость в графах Для заданного ориентированного ациклического графа с n вершинами рассмотрим задачу о вычислении для каждой вершины x значения функ- ции reach (x): числа вершин, достижимых из x. На рис. 8.2 показаны граф и значения reach для него. 1 2 3 4 5 reach (1) = 5 reach (2) = 3 reach (3) = 3 reach (4) = 2 reach (5) = 1 Рис. 8.2. Граф и значения reach для него. Например, reach (2) = 3, потому что из вершины 2 достижимы вершины 2, 4 и 5 Задачу можно решить методом динамического программирования за время O(n 2 ), построив для каждой вершинысписок достижимых из нее вершин. Затем мы представим каждый список в виде битового множества размера n. Это позволит эффективно вычислить объединение двух спис- ков с помощью операции ИЛИ. В предположении, что reach – массив би- товых множеств, а граф представлен списками смежности в массиве adj , вычисление для вершины x можно выполнить следующим образом: reach[x][x] = 1; for (auto u : adj[x]) { reach[x] |= reach[u]; } В табл. 8.3 приведено время работы этого алгоритма с параллельным просмотром разрядов. В каждом случае граф состоял из n вершин и 2n слу- чайных ребер a → b,где a < b. Отметим, что при больших n алгоритм по- требляет очень много памяти. Во многих соревнованиях объем памяти не превышает 512 Мб. 136 Глава 8. Избранные вопросы проектирования алгоритмов Таблица 8.3. Время работы алгоритмов подсчета достижимых вершин Размер графа n Время работы (с) Потребление памяти (МБ) 2 · 10 4 0.06 50 4 · 10 4 0.17 200 6 · 10 4 0.32 450 8 · 10 4 0.51 800 10 5 0.78 1250 8.2. Амортизационный анализ Часто временная сложность алгоритма непосредственно вытекает из его структуры, но иногда прямолинейный анализ не дает истинной картины эффективности. Для анализа последовательности операций с различной временной сложностью можно применить амортизационный анализ. Идея в том, чтобы оценить суммарное время выполнения всех операций, а не каждой в отдельности. 8.2.1. Метод двух указателей В этом методе используются два указателя, пробегающих массив. Каж- дый указатель сдвигается только в одном направлении, что гарантирует эффективность алгоритма. В качестве первого примера этой техники рас- смотрим следующую задачу: даны массив n положительных целых чисел и число x, требуется найти подмассив, сумма которого в точности равна x, или сообщить, что такого подмассива не существует. С помощью метода двух указателей задачу можно решить за время O(n). Указатели будут отмечать первый и последний элементы подмассива. На каждом шаге левый указатель сдвигается на одну позицию вправо, а пра- вый сдвигается вправо на столько позиций, чтобы сумма получившегося подмассива не превосходила x. Если сумма оказывается в точности равна x , решение найдено. На рис. 8.3 показано, как обрабатывается массив, когда сумма x = 8. Вна- чале подмассив содержит значения 1, 3 и 2, сумма которых равна 6. Затем левый указатель сдвигается на одну позицию вправо, а правый остается на месте, потому что иначе сумма превысила бы x. Наконец, левый ука- затель сдвигается еще на одну позицию вправо, а правый сдвигается на две позиции. Сумма этого подмассива равна 2 + 5 + 1 = 8, так что искомый подмассив найден. Время работы алгоритма зависит от того, на сколько позиций сдвинет- ся правый указатель. Не существует полезной верхней границы величины сдвига на одном шаге, но мы знаем, что на протяжении работы алгоритма 8.2. Амортизационный анализ 137 этот указатель сдвинется суммарно на O(n)позиций, потому что сдвиг воз- можен только вправо. Поскольку левый и правый указатели сдвигаются на O(n)позиций, то алгоритм работает за время O(n). 1 3 2 5 1 1 2 3 1 3 2 5 1 1 2 3 1 3 2 5 1 1 2 3 Рис. 8.3. Нахождение подмассива с суммой 8 методом двух указателей Задача о сумме двух элементов. Методом двух указателей можно ре- шить также задачу о сумме двух элементов (2SUM): даны массив n чисел и число x, требуется найти в массиве два элемента, сумма которых равна x, или сообщить, что таких элементов не существует. Для решения задачи сначала отсортируем массив в порядке возраста- ния, а затем пробежимся по нему, сдвигая два указателя. Левый указатель первоначально указывает на первый элемент и сдвигается на одну пози- цию вправо на каждом шаге. Правый указатель первоначально указыва- ет на последний элемент и на каждом шаге сдвигается влево, пока сумма левого и правого элементов остается не больше x. Если сумма в точности равна x, то решение найдено. На рис. 8.4 показано, как обрабатывается массив при x = 12. Вначале сум- ма элементов равна 1 + 10 = 11, это меньше x. Затем левый указатель сдви- гается на одну позицию вправо, а правый – на три позиции влево, так что получается сумма 4 + 7 = 11. После этого левый указатель сдвигается еще на одну позицию вправо. Правый указатель остается на месте, что дает нам решение 5 + 7 = 12. 1 4 5 6 7 9 9 10 1 4 5 6 7 9 9 10 1 4 5 6 7 9 9 10 Рис. 8.4. Решение задачи о сумме двух элементов методом двух указателей 138 Глава 8. Избранные вопросы проектирования алгоритмов Временная сложность этого алгоритма равна O(n log n), потому что для предварительной сортировки массива нужно время O(n log n), а затем оба указателя сдвигаются на O(n)позиций. Отметим, что задачу можно решить и по-другому, тоже за время O(n log n),воспользовавшись двоичным поиском. Для этого мы сначала сортируем массив, а затем обходим его и для каждого элемента выпол- няем двоичный поиск второго элемента, такого, что сумма обоих равна x. На самом деле многие задачи, которые можно решить методом двух ука- зателей, решаются также с помощью сортировки или структур на основе множеств, иногда при этом добавляется логарифмический множитель. Интересна также более общая задача о сумме k элементов (kSUM). В этом случае требуется найти k элементов, сумма которых равна x. Оказывается, что задачу 3SUM можно решить за время O(n 2 ), обобщив описанный выше алгоритм 2SUM. Сможете ли вы найти решение? Долгое время считалось, что O(n 2 ) – лучшая оценка временной сложности для задачи 3SUM. Но в 2014 г. Grønlund и Pettie [14] показали, что это не так. 8.2.2. Ближайшие меньшие элементы Амортизационный анализ часто используется для оценки числа опе- раций, выполненных над структурой данных. Распределение операций может быть неравномерным, т. е. большинство операций имеет место на определенном этапе алгоритма, но их общее число ограничено. Предположим, к примеру, что мы хотим для каждого элемента массива найти ближайший меньший элемент, т. е. первый элемент, предшествую- щий данному и меньший его по величине. Если такого элемента не сущест- вует, то алгоритм должен сообщить об этом. Мы предложим эффективное решение этой задачи с помощью стека. Будем обходить массив слева направо, поддерживая при этом стек эле- ментов массива. На каждом шаге мы удаляем из стека элементы до тех пор, пока элемент на вершине не окажется меньше текущего элемента или стек не станет пустым. После этого мы сообщаем, что элемент на вершине стека – ближайший меньший текущего или, если стек пуст, что такого эле- мента не существует. И наконец, помещаем текущий элемент в стек. На рис. 8.5 показано, как этот алгоритм обрабатывает массив. Внача- ле в стек помещается элемент 1. Поскольку это первый элемент массива, очевидно, что у него нет ближайшего меньшего. Далее в стек помещаются элементы 3 и 4. Ближайшим меньшим элементом для 4 является 3, а бли- жайшим меньшим для 3 – 1. Следующий элемент 2 меньше элементов 3 и 4, находящихся на вершине стека, поэтому оба они удаляются. И бли- жайшим меньшим элементом для 2 оказывается 1. Затем элемент 2 поме- щается в стек. Работа алгоритма продолжается, пока не будет обработан весь массив. 8.2. Амортизационный анализ 139 1 3 4 2 5 3 4 2 1 Шаг 1 1 3 4 2 5 3 4 2 1 3 Шаг 2 1 3 4 2 5 3 4 2 1 3 4 Шаг 3 1 3 4 2 5 3 4 2 1 2 Шаг 4 1 3 4 2 5 3 4 2 1 2 5 Шаг 5 1 3 4 2 5 3 4 2 1 2 3 Шаг 6 1 3 4 2 5 3 4 2 1 2 3 4 Шаг 7 1 3 4 2 5 3 4 2 1 2 Шаг 8 Рис. 8.5. Нахождение ближайших меньших элементов за линейное время с использованием стека Эффективность алгоритма зависит от общего числа операций со сте- ком. Если текущий элемент больше элемента на вершине стека, то он сразу добавляется в стек, это эффективно. Но иногда стек содержит несколько бóльших элементов, и на их удаление приходится тратить время. Тем не менее каждый элемент помещается в стек ровно один раз и удаляется из стека не более одного раза. Поэтому с каждым элементом связано O(1) опе- раций со стеком, так что временная сложность алгоритма равна O(n). 8.2.3. Минимум в скользящем окне Скользящим окном называется подмассив постоянного размера, кото- рый движется вдоль массива слева направо. В каждой позиции окна мы вычисляем какую-то информацию о попавших внутрь элементах. Далее мы рассмотрим задачу о запоминании минимума в скользящем окне – для каждого скользящего окна требуется найти наименьшее значение. Для вычисления минимумов в скользящих окнах можно воспользовать- ся той же идеей, что при нахождении ближайших меньших элементов. Но на этот раз нам понадобится очередь, в которой каждый элемент больше предыдущего, а первый элемент всегда соответствует минимальному эле- менту внутри окна. После каждого сдвига окна мы будем удалять из конца очереди элемент до тех пор, пока очередной элемент не окажется мень- ше вновь появившегося в окне элемента или очередь не опустеет. Первый 140 Глава 8. Избранные вопросы проектирования алгоритмов элемент мы также удалим, если он больше не находится внутри окна. И на- конец, мы помещаем новый элемент в очередь. На рис. 8.6 показано, как алгоритм обрабатывает массив, когда размер скользящего окна равен 4. В первой позиции окна наименьшее значение равно 1. Затем окно сдвигается на одну позицию вправо. Новый элемент 3 меньше элементов 4 и 5, находящихся в очереди, поэтому эти элементы уда- ляются из очереди, а элемент 3 помещается в нее. Наименьшим по-преж- нему остается элемент 1. Далее окно снова сдвигается вправо, и наимень- ший элемент 1 «выпадает» из окна. Поэтому он удаляется из очереди, и наименьшим становится элемент 3. В очередь также помещается новый элемент 4. Следующий новый элемент 1 меньше всех элементов в очереди, поэтому все они удаляются, и в очереди остается только элемент 1. Нако- нец, окно достигает последней позиции. Элемент 2 помещается в очередь, но наименьшим элементом внутри окна по-прежнему является 1. 2 1 4 5 3 4 1 2 1 4 5 2 1 4 5 3 4 1 2 1 3 2 1 4 5 3 4 1 2 3 4 2 1 4 5 3 4 1 2 1 2 1 4 5 3 4 1 2 1 2 Рис. 8.6. Нахождение минимумов в скользящем окне за линейное время Поскольку каждый элемент помещается в очередь ровно один раз, а уда- ляется не более одного раза, то алгоритм работает за время O(n). 8.3. Нахождение минимальных значений Рассмотрим функцию f(x), котораясначала убывает, достигает минимума, после чего возрастает. Пример такой функции приведен на рис. 8.7, ее ми- нимум отмечен стрелочкой. Если мы знаем, что функция ведет себя таким образом, то можем эффективно найти минимальное значение. 8.3. Нахождение минимальных значений 141 Рис. 8.7. Функция и ее минимальное значение 8.3.1. Тернарный поиск Тернарный поиск – это эффективный способ нахождения минимумов функций, которые сначала монотонно убывают, а затем монотонно воз- растают. Пусть известно, что значение x, доставляющее минимум f(x), на- ходится в диапазоне [x L , x R ]. Идея заключается в том, чтобы разбить диапа- зон на три равные части [x L , a], [a, b] и [b, x R ], положив 2 3 L R x x a + = и 2 3 L R x x b + = Тогда если f(a) < f(b), то можно заключить, что минимум принадлежит отрезку [x L , b], в противном случае он должен находиться внутри отрезка [a , x R ]. Затем поиск рекурсивно продолжается, пока размер отрезка не ста- нет достаточно мал. На рис. 8.8 показан первый шаг тернарного поиска. Поскольку f(a) > f(b), новым диапазоном становится [a, x R ]. x L a b x R x L a b x R Рис. 8.8. Нахождение минимума методом тернарного поиска 142 Глава 8. Избранные вопросы проектирования алгоритмов На практике часто рассматриваются функции, параметрами которых являются целые числа, а поиск завершается, когда будет найден диапазон, содержащий единственный элемент. Поскольку размер нового диапазона всегда составляет 2/3 от размера предыдущего, временная сложность алго- ритма равна O(log n), где n – число элементов в исходном диапазоне. Отметим, что при работе с целыми параметрами можно использовать бинарный поиск вместо тернарного, поскольку достаточно найти первое значение x, для которого f(x)≤ f(x + 1). 8.3.2. Выпуклые функции Функция называется выпуклой, если отрезок, соединяющий любые две точки на ее графике, целиком лежит выше или ниже соответствующей дуги графика. На рис. 8.9 показан график выпуклой функции f(x)= x 2 . Дейст- вительно, отрезок, соединяющий точки a и b,лежит выше дуги графика. a b Рис. 8.9. Пример выпуклой функции: f(x) = x 2 Если известно, что минимальное значение выпуклой функции находит- ся в диапазоне [x L , x R ], то для его нахождения можно применить тернарный поиск. Отметим, однако, что выпуклая функция может достигать миниму- ма в нескольких точках. Например, функция f(x)= 0 выпуклая, и ее мини- мум равен 0. Выпуклые функции обладают несколькими полезными свойствами: если f(x)и g(x)– выпуклые функции, то f(x) + g(x)и max(f(x), g(x))тоже вы- пуклы. Следовательно, если имеется n выпуклых функций f 1 , f 2 , …, f n , то сразу можно сказать, что функция f 1 + f 2 + … + f n выпуклая, и применить для нахождения ее минимума тернарный поиск. 8.3.3. Минимизация сумм Пусть дано n чисел a 1 , a 2 , …, a n и требуется найти значение x, доставляю- щее минимум сумме |a 1 − x| + |a 2 − x| + … + |a n − x|. Например, для чисел [1, 2, 9, 2, 6] оптимальное решение x = 2, при этом получается сумма |1 − 2| + |2 − 2| + |9 − 2| + |2 − 2| + |6 − 2| = 12. 8.3. Нахождение минимальных значений 143 Поскольку каждая функция |a k − x| выпукла, их сумма также выпукла, поэтому для нахождения оптимального значения x можно применить тер- нарный поиск. Но есть и более простое решение. Оказывается, что опти- мальное значение x всегда равно медиане чисел, т. е. среднему элементу, получающемуся после их сортировки. Так как список [1, 2, 9, 2, 6] после сортировки переходит в [1, 2, 2, 6, 9], то медиана равна 2. Медиана всегда дает оптимальное решение, потому что если x меньше медианы, то сумма уменьшится при увеличении x, а если x больше медиа- ны, то сумма уменьшится при уменьшении x. Если n четно и существует две медианы, то обе они, а также все значения между ними дают опти- мальные решения. Далее рассмотрим задачу о минимизации функции (a 1 − x) 2 + (a 2 − x) 2 + … + (a n − x) 2 . Для чисел [1, 2, 9, 2, 6] оптимальное решение x = 4, при этом получается сумма (1 − 4) 2 + (2 − 4) 2 + (9 − 4) 2 + (2 − 4) 2 + (6 − 4) 2 = 46. И снова функция выпуклая, поэтому задачу можно было бы решить методом тернарного поиска, но есть и более простое решение: минимум достигается, когда x – среднее арифметическое чисел. В нашем примере среднее арифметическое равно (1 + 2 + 9 + 2 + 6)/5 = 4. Это можно доказать, представив сумму в виде nx 2 − 2x(a 1 + a 2 + … + a n )+ (a 1 2 + a 2 2 + … + a n 2 ). Последнее слагаемое не зависит от x, так что его можно игнорировать. А первые два слагаемых образуют функцию nx 2 − 2xs, где s = a 1 + a 2 + … + a n . Это парабола, направленная рогами вверх, ее корни равны x = 0 и x = 2 s/n, а минимальное значение достигается в точке x = s/n, расположенной посередине между корнями, а это и есть среднее арифметическое чисел a 1 , a 2 , …, a n |