Параллельный двоичный алгоритм рубки

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

• Нажмите элемент
• Предположим, что элемент раньше, ищите здесь
• Предположим, элементпосле, ищите там

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

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

Answer 4

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

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