Параллельный алгоритм бинарной измельчения

Question

Есть ли способ (или теоретически возможно) реализовать алгоритм бинарного поиска одновременно? Я угадал ответ вполне может быть не по двум причинам:

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

Однако, я хотел бы получить разъяснения на этом фронте (и, если это возможно, какие-либо ссылки или примеры?)

Answer 1

Сначала, похоже, бинарный поиск полностью непараллелен. Но обратите внимание, что есть только три возможных результата:

• Вы попали элемент
• элемент искали это до того, как элемент, который вы попали
• элемент после

Итак, мы начинаем три параллельные процессы:

• попал в элемент
• Предположим, что элемент прежде, искать здесь
• Пусть элемент после, искать там

Как только мы знаем, результат с первого из них, мы можем убить тот, который не собирается найти элемент. Но в то же время процесс, который искал в нужном месте, удвоил скорость поиска, то есть текущее ускорение является 2 из возможных 3.

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

Answer 2

Я думаю, вы можете понять ответ! Чтобы распараллелить, должна быть какая-то работа, которую можно разделить. В случае поиска бина нет ничего, что можно было бы разделить и распараллелить. bin-search попадает в середину массива значений. Эта работа не может быть разделена. Etc .. пока не найдет решение.

Что, по вашему мнению, можно распараллелить?

Answer 3

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

Answer 4

Вы всегда можете попробовать не-бинарный поиск, по существу, если у вас есть n ядер, вы можете разделить массив на n + 1 штуку. Оттуда вы просматриваете каждую из «точек вырезания» и видите, больше или меньше значение точки вырезания, это приводит к тому, что у вас есть пятая часть исходного пространства, а не половина, так как вы сможете выбрать меньший раздел.