Как многопоточность или многопроцессорность работают с рекурсиями

Question

Фон

Я немного новичок в разработке и у меня был общий вопрос по питону / программированию. Если у вас есть метод, который является рекурсией, что означает включение нескольких потоков или многопроцессорности? Я сделал небольшое чтение и несколько примеров, но они, кажется, применяют синтаксис для нового кода (и не очень трудоемких задач), мне больше интересно, как мне перепроектировать существующий код, чтобы сделать это?

Скажем, у меня есть что-то, что интенсивно использует процессор (в основном продолжает добавлять к себе, пока не достигнут предел):

def adderExample(sum, number):
    if sum > 1000:
        print 'sum is larger than 10. Stoping'
    else:
        sum = sum + number
        print sum
        number = number + 1
        adderExample(sum, number)


adderExample(0,0)

Вопрос (ы) / Хотя процесс

Как мне подойти к этому, чтобы заставить его работать быстрее, если у меня есть несколько доступных ядер (я хочу, чтобы он в конечном итоге захотел охватить машины, но я думаю, что это отдельная проблема с hadoop, поэтому я оставлю этот пример только для одной системы с несколько процессоров)? Кажется, что многопоточность - не лучший выбор (из-за времени, которое требуется для создания новых потоков), если это правда, я должен сосредоточиться только на многопроцессорности? Если да, могут ли рекурсии быть разделены на разные процессоры (я полагаю, что очереди vai и затем возвращаются после того, как это сделано)? Могу ли я создать несколько потоков для каждого процесса, чем разделить эти процессы на несколько процессоров? Наконец, ограничивает ли глубина рекурсии общий лимит или он основан на потоках / процессах, если так, то обходится ли многопроцессорность / многопоточность?

Другой вопрос (связанный), как эти парни, пытающиеся кодировать (rsa, беспроводные ключи и т. Д.) С помощью грубой силы, преодолевают эту проблему? Я предполагаю, что они как-то масштабируют свои математические процессы по нескольким процессорам. Этот или любой другой пример для моего понимания был бы великолепен.

Любые советы / предложения будут великолепны

Спасибо!

Answer 1

Такой цикл не принесет много пользы от многопоточности. Учтите, что вы делаете серию дополнений, промежуточные значения которых зависят от предыдущих итераций. Это нельзя распараллелить, потому что потоки будут топтать значения друг друга и перезаписывать вещи. Вы можете заблокировать данные так, чтобы за один раз работал только один поток, но тогда вы потеряете все преимущества работы нескольких потоков над этими данными.

Потоки работают лучше всего, когда они имеют независимые наборы данных. например графический рендерер - прекрасный пример. Каждый поток отображает подмножество большего изображения - они могут совместно использовать общие источники данных для данных текстуры / вершины / цвета / и т. Д., Но каждый поток имеет свой собственный небольшой участок общего изображения, чтобы работать один, и не касается другие области изображения. Что бы ни делал поток # 1 в своем небольшом разделе пикселей, это не повлияет на то, что поток # 2 делает в другом месте изображения.

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

Как только потоки становятся взаимозависимыми, вы теряете много преимуществ, связанных с несколькими потоками. Они будут тратить больше времени на ожидание окончания, чем на выполнение реальной работы. Конечно, это не значит, что вы никогда не должны использовать потоки. Иногда имеет смысл иметь несколько потоков, даже если они взаимозависимы. Например. графический поток + поток звуковых эффектов + поток процессора действий + А.И. расчёты потока и т.д ... в игре. каждый из них номинально зависит друг от друга, но в то время как звуковая нить занята генерацией звука bang + ricochet для пистолета, который игрок только что выстрелил, a.i. поток выключен, подсчитывается, что делают мобы в игре, графический поток рисует облака на заднем плане и т. д ...

Answer 2

Threading kinda sorta подразумевает множественные стеки, рекурсивные одиночные стеки.Тем не менее, если вы доберетесь до части recurse-left, recurse-right и решите порождать потоки для подзадач, если текущее число потоков «низкое», и выполнять прямую рекурсию, в противном случае вы можете объединить концепции.

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

Answer 3

Phunctor прав, что библиотека потоков является плохим выбором для распараллеливания этого типа проблемы из-за «глобальной блокировки интерпретатора», которая препятствует параллельному выполнению кода Python несколькими потоками.

Тем не менее, библиотека потоков может быть очень полезна, когда код каждого потока тратит много времени на ожидание ввода-вывода. Так, например, если вы реализуете сервер, который должен нажать на диск или ждать ответа по сети, обслуживание запроса в каждом потоке может быть очень эффективным, поскольку библиотека потоков может предпочесть те, которые не ожидают I / O и, следовательно, максимально использовать интерпретатор Python. (В одном потоке вам пришлось бы использовать жесткий цикл, проверяющий состояния ваших запросов ввода-вывода, что, как правило, приводит к расточительству при высокой нагрузке.)