Редактирование: Параллельный алгоритм нахождения выпуклой оболочки

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 53: Строка 53:
 
Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <tex>O(log^2(n))</tex>, а можно сделать его за <tex>work = O(n)</tex>, при этом уменьшив span
 
Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <tex>O(log^2(n))</tex>, а можно сделать его за <tex>work = O(n)</tex>, при этом уменьшив span
  
Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на <tex>\sqrt{n}</tex> частей.
+
Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на <tex>\sqrt(n)</tex> частей.
  
Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на <tex>\sqrt{n}</tex> различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:
+
Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на <tex>\sqrt(n)</tex> различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:
  
1) Берем <tex>\sqrt{n}</tex>, <tex>2\sqrt{n}</tex>, <tex>3\sqrt{n}</tex>, ..., <tex>\sqrt{n}\sqrt{n}</tex> и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает <tex>0</tex> или <tex>1</tex> - левее или правее они результата. Каждый результат считает за себя <tex>k\sqrt{n}</tex> и за соседа <tex>(k + 1)\sqrt{n}</tex>.  
+
1) Берем <tex>\sqrt{n}</tex>, <tex>2\sqrt{n}</tex>, <tex>3\sqrt{n}</tex>, ..., <tex>\sqrt{n}\sqrt{n}</tex> и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает <tex>0</tex> или <tex>1</tex> - левее или правее они результата. Каждый результат считает за себя <tex>k\sqrt{n}</tex> и за соседа <tex>(k + 1)\sqrt{n}</tex>. Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.
 
 
2) Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.
 
 
 
Таким образом, у нас выходит примерно такой алгоритм -
 
 
 
1) Создаем функцию, которая находит касательную для точки из первого многоугольника на второй многоугольник.
 
 
 
fun getFromPoint(K):
 
    '''int''' startAfter
 
    '''pfor''' i = 0...sqrt(n):
 
        '''int''' startCurrent = sqrt(n) * i
 
        '''int''' startNext = sqrt(n) * i + 1
 
        '''int''' finishCurrent = sqrt(n) * i
 
        '''int''' finishNext = sqrt(n) * i + 1
 
        '''boolean''' isStartBeforeAnswer = left_turn(startCurrent, K, startNext) > 0
 
        '''boolean''' isFinishBeforeAnswer = left_turn(finishCurrent, K, finishNext) > 0
 
        if (isStartBeforeAnswer != isFinishBeforeAnswer) startAfter = startCurrent
 
    '''pfor''' i = 0..sqrt(n):
 
        '''int''' start = i + startAfter
 
        '''int''' middle = i + startAfter + 1
 
        '''int''' finish = i + startAfter + 2
 
        if (left_turn(start, K, middle) != left_turn(middle, K, finish)) return middle
 
 
 
Его <tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>
 
 
 
2) Создадим функцию, которая находит касательную $AB$ между двумя многоугольниками (она будет сильно похожа на предыдущую функцию)
 
 
 
{{Теорема
 
|about=
 
|statement=Если предыдущая точка $prev$ и следующая точка $next$ лежат по одну сторону (в нашем случае ниже) от касательной на второй многоугольник, то эта точка $x$ является точкой искомой касательной. Иначе - если $prev$ находится выше касательной, то мы дальше $A$, иначе - до $A$.
 
|proof=
 
 
 
Многоугольник выпуклый, значит, что если одна точка лежит на прямой, а две соседние по одну сторону от нее, значит, что эта прямая является касательной.
 
 
 
Если $prev$ находится выше касательной, то это значит, что его касательная находится выше, значит, что AB тоже находится выше, а значит, что A находится раньше. Аналогично для обратного случая.
 
}}
 
 
 
Здесь у нас совершенно тот же код, просто мы вместо предиката левый поворот смотрим, где будет находиться предыдущая точка и следующая.
 
 
 
<tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>
 
 
 
Итоговое время работы: <tex>work = n</tex>, <tex>span = \log{n}</tex>
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)