параметрический поиск
Feb. 2nd, 2010 01:50 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись будет интересна скорее всего лишь программистам и сочувствующим)
Пару дней назад прочитал о параметрическом поиске - и весьма впечатлился; я бы даже сказал, впервые за много лет мне алгоритм взорвал мозг. Попробую рассказать об этом методе на примере конкретной задачи. Заранее предупреждаю, что в этой записи речь идет о красоте алгоритмов и их идей, а не практической пользе; описываемая идея теоретически эффективна, но из-за больших констант непрактична.
Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 70-х - начале 80-х. Особенно часто он подходит к проблемам в вычислительной геометрии.
Рассмотрим следующую задачу. Даны уравнения n прямых на плоскости, и для простоты предположим, что они находятся в общем положении: то есть, любые две из них пересекаются, и нет трех, пересекающихся в одной точке. У этих прямых есть n(n-1)/2 = O(n2) точек пересечения, которые можно отсортировать по их x-координатам слева направо - опять же для простоты положим, что все x-координаты разные. Проблема: найти k-ю слева точку пересечения, где 1≤k≤n(n-1)/2.
Наивное решение: отсортируем точки пересечения, и возьмем k-ю. Т.к. точек O(n2), это займет примерно O(n2logn) времени. Метод, который я опишу, решает задачу за O(n*log3n) времени. Учитывая то, что сам аргумент k двигается в пределах от 1 до n(n-1)/2, это впечатляет. Метод состоит из трех частей: процедура сравнения, собственно сам параметрический поиск, и его параллелизация.
Процедура сравнения. Обозначим через x* x-координату искомой k-й слева точки пересечения. Нам достаточно найти число x*, потому что тогда найти точки всех прямых в ней, и проверить, отсортировав, какие две пересекаются, тривиально за O(n*logn). Процедура сравнения делает следующее: сравнивает любое данное x с x*, и отвечает, меньше, больше или равно (не зная при этом значения x*). Я покажу, как можно это сделать за O(n*logn).
Посмотрим на наши прямые где-нибудь левее всех точек пересечения, и пронумеруем их снизу вверх от 1 до n по порядку в этой области (т.е. просто согласно их наклонам). Теперь двигаемся слева направо, и замечаем, что каждое прохождение точки пересечения меняет порядок на одну транспозицию соседних прямых. Например, изначальный порядок 1 2 3 4, самая левая точка пересечения - прямых 1 и 2, тогда после нее порядок стал 2 1 3 4. Следующая точка будет точкой пересечения каких-то других двух прямых, соседних в этом порядке, и тоже поменяет их местами, и так далее.
У любой перестановки можно посчитать число инверсий, т.е. число пар, стоящих в обратном порядке: индексов i,j, так что i<j, но ai>aj. Легко видеть, что транспозиция соседних элементов меняет число инверсий ровно на единицу: либо +1, когда "портит" правильный порядок этих двух элементов, либо -1, когда восстанавливает, а на все остальные пары в любом случае не влияет. Но поскольку в нашем случае каждые две прямые пересекаются только один раз, и когда это происходит, меньшая из них по номеру стоит в перестановке перед большей, выходит, что каждая точка пересечения именно увеличивает число инверсий на 1.
Пусть нам дали какую-то точку x, про которую известно, что она - одна из точек пересечения. Мы легко можем найти y-координаты всех прямых в этой точке, и отсорировать их, за O(n*logn). Это даст нам некую перестановку прямых. Если мы теперь найдем число инверсий в этой перестановке, то сравнив его с k, мы узнаем, где лежит x относительно искомой точки x*: если оно меньше k, то слева, больше - справа, равно - x и есть x*.
Осталось объяснить, как найти число инверсий за O(n*logn), хотя само это число может быть порядка О(n2), так что слишком дорого делать одну операцию для каждой инверсии. Произведем merge sort перестановки, глядя на нее, как на список чисел. В процессе сортировки мы получим рекурсивно число инверсий внутри левой половины и правой половины, а во время фазы слияния посчитаем число инверсий между двумя половинами; сложив эти три числа вместе, получим ответ. Во время фазы слияния мы делаем следующее: все время смотрим, какое следующее число ставить в общий список: из отсортированной левой половины или отсортированной правой половины. В первом случае мы ничего нового не делаем, т.к. добавляемое левое число меньше всех правых, и инверсий нет. А вот каждый раз, когда мы выбираем следующее число справа, мы добавим к счетчику инверсий количество оставшихся чисел слева, потому что с каждым из них у выбранного числа есть инверсия. Таким образом во время фазы слияния мы за те же O(n) посчитали число инверсий между двумя половинами.
Вся процедура сравнения вместе занимает O(n*logn), и отвечает, для любой координаты x некой точки пересечения, на вопрос: меньше, равно или больше это число, чем x*.
Параметрический поиск. Теперь я перехожу к главной идее этого метода - той самой, которая взорвала мне мозг. Она на данном примере состоит в следующем. Давайте представим себе, что мы хотим отсортировать y-координаты всех n прямых в точке, лежащей сразу после k-того пересечения. Если k-тое пересечение имеет координату x*, возьмем какое-то x*+ε, посмотрим, в каком порядке идут наши прямые в этом месте, и отсортируем их в соответствии с этим порядком. Скажем, прямая 1 должна быть меньше прямой 5, если она в этом месте все еще ниже ее, и так далее. Правда, мы не знаем, чему равно x*, и не знаем, как найти y-координаты наших прямых в этом месте, но почему нас это должно остановить? Возьмем какой-нибудь алгоритм сортировки сравнениями, любой - тот же merge sort - дадим ему n объектов, обозначающих наши прямые, и скажем: сортируй! Он будет пытаться сортировать, и для этого ему эти прямые надо сравнивать; и каждый раз, когда он хочет сравнить две прямые, мы сделаем это за него следующим образом. Предположим, merge sort пришел к нам и говорит: мне надо знать, прямая i меньше прямой j или больше. Пусть i≤j. Найдем точку пересечения i и j, какое-то xij. Запустим на xij нашу процедуру сравнения из предыдущего пункта, и она скажет нам, находится он слева от x* или справа (если точно x*, то нам повезло и все закончено). Если слева, то прямые уже успели пересечься до x*, и значит прямая j больше прямой i; если справа, то меньше. Мы даем этот ответ алгоритму сортировки, и одновременно записываем в сторонке ограничение на x*, о котором мы узнали: x*, оказывается, больше (или меньше) конкретного числа xij.
Merge sort продолжает сортировать прямые и просить нас сравнить пары прямых, а мы это делаем с помощью процедуры сравнения, и как побочный эффект получаем все время все новые и новые ограничения на x* - собственно, мы храним интервал возможных значений x*, и все время его подправляем. В какой-то момент merge sort закончит сортировать и даст нам порядок прямых в точке x*+ε. И вот какая штука выходит: интервал возможных значений x* к этому моменту будет в точности интервалом между k-й и k+1-й точками пересечения - т.е. его левая граница немедленно даст нам x*. Почему это так? Потому что любая точка из интервала, который мы построили, "подходит" в качестве кандидата для перестановки, к-ю мы получили - в ней обязана быть именно такая перестановка прямых, потому что она дала бы именно такие ответы на все заданные вопросы-сравнения. Но мы видели раньше, что до k-й точки и после k+1-й перестановки обязательно будут другими, из-за все время растущего числа инверсий.
Вот этот трюк меня потряс: что мы делаем что-то с неизвестными нам вообще числами (сортируем по неизвестным нам y-координатам в неизвестной нам точке x*), да и конечный итог наших действий нас совершенно не интересует (эта перестановка нам не нужна вовсе). Но по мере работы мы одновременно ухитряемся сравнить любые два из этих неизвестных чисел, и заодно из этого получить побочные данные, которые в конце концов дают нам именно то, что мы хотим. Очень, очень красиво.
Но все еще, меж тем, неэффективно. Сортировка сравнениями требует O(n*logn) сравнений, и каждое такое сравнение у нас отнимает O(n*logn) - столько стоит запустить процедуру сравнения. Поэтому все вместе работает за O(n2log2n), и тогда непонятно, зачем было все это городить. Остается объяснить один последний фокус.
Параллелизация. Существуют параллельные алгоритмы, которые могут отсортировать n элементов, пользуясь n процессорами, за O(logn) параллельного времени, т.е. каждый процессор делает O(logn) шагов и О(logn) сравнений. Вот пример одного из таких алгоритмов для тех, кто хочет узнать подробности - я не буду в них вдаваться; я подчеркну, что практичным его назвать нельзя из-за огромных констант. Но тем не менее теоретически это возможно.
Мы сделаем следующую странную штуку. Вместо merge sort, в предыдущем пункте, будем пользоваться этим параллельным алгоритмом. Только вместо того, чтобы на самом деле запускать его параллельно, будем его симулировать в обычном последовательном исполнении: сначала выполним один за другим n первых шагов всех n процессоров. Потом n вторых шагов... и так log(n) раз (с точностью до константы, ясно). В итоге наша сортировка все равно займет O(n*logn) шагов, как и merge sort, поэтому неясно, как нам это помогает.
А вот как. Вместо того, чтобы отвечать на каждый вопрос-сравнение по отдельности, мы будем отвечать на них группами из n штук. Ведь в параллельном алгоритме n процессоров работают независимо, так что на каждом шагу они хотят задать нам O(n) вопросов-сравнений, не зависящих друг от друга (т.е. от ответа на первый вопрос не зависит, каким будет второй вопрос, и так далее). Мы возьмем эти n вопросов вместе - это n пар прямых, которые нас просят сравнить друг с другом, или, что то же, n точек пересечения, которые нас просят сравнить с x*. Найдем эти точки пересечения и отсортируем их по x-координатам, за O(n*logn). А теперь вместо того, чтобы сравнить каждую с x* отдельно, как мы делали раньше, найдем место x* среди них двоичным поиском. Это даст нам и новые ограничения на возможный интервал для x*, и ответы на все n вопросов. А сравнений при этом нам надо будет делать только O(logn), как в любом двоичном поиске, и каждое сравнение - вызов нашей процедуры. Поэтому всего мы потратим на это O(n*log2n) времени. Делать это надо будет O(logn) раз, по числу шагов в параллельном алгоритме. Так что конечный ответ - время, за которое мы находим x* - равен O(nlog3n), как и обещано.
Пару дней назад прочитал о параметрическом поиске - и весьма впечатлился; я бы даже сказал, впервые за много лет мне алгоритм взорвал мозг. Попробую рассказать об этом методе на примере конкретной задачи. Заранее предупреждаю, что в этой записи речь идет о красоте алгоритмов и их идей, а не практической пользе; описываемая идея теоретически эффективна, но из-за больших констант непрактична.
Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 70-х - начале 80-х. Особенно часто он подходит к проблемам в вычислительной геометрии.
Рассмотрим следующую задачу. Даны уравнения n прямых на плоскости, и для простоты предположим, что они находятся в общем положении: то есть, любые две из них пересекаются, и нет трех, пересекающихся в одной точке. У этих прямых есть n(n-1)/2 = O(n2) точек пересечения, которые можно отсортировать по их x-координатам слева направо - опять же для простоты положим, что все x-координаты разные. Проблема: найти k-ю слева точку пересечения, где 1≤k≤n(n-1)/2.
Наивное решение: отсортируем точки пересечения, и возьмем k-ю. Т.к. точек O(n2), это займет примерно O(n2logn) времени. Метод, который я опишу, решает задачу за O(n*log3n) времени. Учитывая то, что сам аргумент k двигается в пределах от 1 до n(n-1)/2, это впечатляет. Метод состоит из трех частей: процедура сравнения, собственно сам параметрический поиск, и его параллелизация.
Процедура сравнения. Обозначим через x* x-координату искомой k-й слева точки пересечения. Нам достаточно найти число x*, потому что тогда найти точки всех прямых в ней, и проверить, отсортировав, какие две пересекаются, тривиально за O(n*logn). Процедура сравнения делает следующее: сравнивает любое данное x с x*, и отвечает, меньше, больше или равно (не зная при этом значения x*). Я покажу, как можно это сделать за O(n*logn).
Посмотрим на наши прямые где-нибудь левее всех точек пересечения, и пронумеруем их снизу вверх от 1 до n по порядку в этой области (т.е. просто согласно их наклонам). Теперь двигаемся слева направо, и замечаем, что каждое прохождение точки пересечения меняет порядок на одну транспозицию соседних прямых. Например, изначальный порядок 1 2 3 4, самая левая точка пересечения - прямых 1 и 2, тогда после нее порядок стал 2 1 3 4. Следующая точка будет точкой пересечения каких-то других двух прямых, соседних в этом порядке, и тоже поменяет их местами, и так далее.
У любой перестановки можно посчитать число инверсий, т.е. число пар, стоящих в обратном порядке: индексов i,j, так что i<j, но ai>aj. Легко видеть, что транспозиция соседних элементов меняет число инверсий ровно на единицу: либо +1, когда "портит" правильный порядок этих двух элементов, либо -1, когда восстанавливает, а на все остальные пары в любом случае не влияет. Но поскольку в нашем случае каждые две прямые пересекаются только один раз, и когда это происходит, меньшая из них по номеру стоит в перестановке перед большей, выходит, что каждая точка пересечения именно увеличивает число инверсий на 1.
Пусть нам дали какую-то точку x, про которую известно, что она - одна из точек пересечения. Мы легко можем найти y-координаты всех прямых в этой точке, и отсорировать их, за O(n*logn). Это даст нам некую перестановку прямых. Если мы теперь найдем число инверсий в этой перестановке, то сравнив его с k, мы узнаем, где лежит x относительно искомой точки x*: если оно меньше k, то слева, больше - справа, равно - x и есть x*.
Осталось объяснить, как найти число инверсий за O(n*logn), хотя само это число может быть порядка О(n2), так что слишком дорого делать одну операцию для каждой инверсии. Произведем merge sort перестановки, глядя на нее, как на список чисел. В процессе сортировки мы получим рекурсивно число инверсий внутри левой половины и правой половины, а во время фазы слияния посчитаем число инверсий между двумя половинами; сложив эти три числа вместе, получим ответ. Во время фазы слияния мы делаем следующее: все время смотрим, какое следующее число ставить в общий список: из отсортированной левой половины или отсортированной правой половины. В первом случае мы ничего нового не делаем, т.к. добавляемое левое число меньше всех правых, и инверсий нет. А вот каждый раз, когда мы выбираем следующее число справа, мы добавим к счетчику инверсий количество оставшихся чисел слева, потому что с каждым из них у выбранного числа есть инверсия. Таким образом во время фазы слияния мы за те же O(n) посчитали число инверсий между двумя половинами.
Вся процедура сравнения вместе занимает O(n*logn), и отвечает, для любой координаты x некой точки пересечения, на вопрос: меньше, равно или больше это число, чем x*.
Параметрический поиск. Теперь я перехожу к главной идее этого метода - той самой, которая взорвала мне мозг. Она на данном примере состоит в следующем. Давайте представим себе, что мы хотим отсортировать y-координаты всех n прямых в точке, лежащей сразу после k-того пересечения. Если k-тое пересечение имеет координату x*, возьмем какое-то x*+ε, посмотрим, в каком порядке идут наши прямые в этом месте, и отсортируем их в соответствии с этим порядком. Скажем, прямая 1 должна быть меньше прямой 5, если она в этом месте все еще ниже ее, и так далее. Правда, мы не знаем, чему равно x*, и не знаем, как найти y-координаты наших прямых в этом месте, но почему нас это должно остановить? Возьмем какой-нибудь алгоритм сортировки сравнениями, любой - тот же merge sort - дадим ему n объектов, обозначающих наши прямые, и скажем: сортируй! Он будет пытаться сортировать, и для этого ему эти прямые надо сравнивать; и каждый раз, когда он хочет сравнить две прямые, мы сделаем это за него следующим образом. Предположим, merge sort пришел к нам и говорит: мне надо знать, прямая i меньше прямой j или больше. Пусть i≤j. Найдем точку пересечения i и j, какое-то xij. Запустим на xij нашу процедуру сравнения из предыдущего пункта, и она скажет нам, находится он слева от x* или справа (если точно x*, то нам повезло и все закончено). Если слева, то прямые уже успели пересечься до x*, и значит прямая j больше прямой i; если справа, то меньше. Мы даем этот ответ алгоритму сортировки, и одновременно записываем в сторонке ограничение на x*, о котором мы узнали: x*, оказывается, больше (или меньше) конкретного числа xij.
Merge sort продолжает сортировать прямые и просить нас сравнить пары прямых, а мы это делаем с помощью процедуры сравнения, и как побочный эффект получаем все время все новые и новые ограничения на x* - собственно, мы храним интервал возможных значений x*, и все время его подправляем. В какой-то момент merge sort закончит сортировать и даст нам порядок прямых в точке x*+ε. И вот какая штука выходит: интервал возможных значений x* к этому моменту будет в точности интервалом между k-й и k+1-й точками пересечения - т.е. его левая граница немедленно даст нам x*. Почему это так? Потому что любая точка из интервала, который мы построили, "подходит" в качестве кандидата для перестановки, к-ю мы получили - в ней обязана быть именно такая перестановка прямых, потому что она дала бы именно такие ответы на все заданные вопросы-сравнения. Но мы видели раньше, что до k-й точки и после k+1-й перестановки обязательно будут другими, из-за все время растущего числа инверсий.
Вот этот трюк меня потряс: что мы делаем что-то с неизвестными нам вообще числами (сортируем по неизвестным нам y-координатам в неизвестной нам точке x*), да и конечный итог наших действий нас совершенно не интересует (эта перестановка нам не нужна вовсе). Но по мере работы мы одновременно ухитряемся сравнить любые два из этих неизвестных чисел, и заодно из этого получить побочные данные, которые в конце концов дают нам именно то, что мы хотим. Очень, очень красиво.
Но все еще, меж тем, неэффективно. Сортировка сравнениями требует O(n*logn) сравнений, и каждое такое сравнение у нас отнимает O(n*logn) - столько стоит запустить процедуру сравнения. Поэтому все вместе работает за O(n2log2n), и тогда непонятно, зачем было все это городить. Остается объяснить один последний фокус.
Параллелизация. Существуют параллельные алгоритмы, которые могут отсортировать n элементов, пользуясь n процессорами, за O(logn) параллельного времени, т.е. каждый процессор делает O(logn) шагов и О(logn) сравнений. Вот пример одного из таких алгоритмов для тех, кто хочет узнать подробности - я не буду в них вдаваться; я подчеркну, что практичным его назвать нельзя из-за огромных констант. Но тем не менее теоретически это возможно.
Мы сделаем следующую странную штуку. Вместо merge sort, в предыдущем пункте, будем пользоваться этим параллельным алгоритмом. Только вместо того, чтобы на самом деле запускать его параллельно, будем его симулировать в обычном последовательном исполнении: сначала выполним один за другим n первых шагов всех n процессоров. Потом n вторых шагов... и так log(n) раз (с точностью до константы, ясно). В итоге наша сортировка все равно займет O(n*logn) шагов, как и merge sort, поэтому неясно, как нам это помогает.
А вот как. Вместо того, чтобы отвечать на каждый вопрос-сравнение по отдельности, мы будем отвечать на них группами из n штук. Ведь в параллельном алгоритме n процессоров работают независимо, так что на каждом шагу они хотят задать нам O(n) вопросов-сравнений, не зависящих друг от друга (т.е. от ответа на первый вопрос не зависит, каким будет второй вопрос, и так далее). Мы возьмем эти n вопросов вместе - это n пар прямых, которые нас просят сравнить друг с другом, или, что то же, n точек пересечения, которые нас просят сравнить с x*. Найдем эти точки пересечения и отсортируем их по x-координатам, за O(n*logn). А теперь вместо того, чтобы сравнить каждую с x* отдельно, как мы делали раньше, найдем место x* среди них двоичным поиском. Это даст нам и новые ограничения на возможный интервал для x*, и ответы на все n вопросов. А сравнений при этом нам надо будет делать только O(logn), как в любом двоичном поиске, и каждое сравнение - вызов нашей процедуры. Поэтому всего мы потратим на это O(n*log2n) времени. Делать это надо будет O(logn) раз, по числу шагов в параллельном алгоритме. Так что конечный ответ - время, за которое мы находим x* - равен O(nlog3n), как и обещано.
