Эффективные способы реализации взаимодействия Every-to-Every?

Question

Учитывая список элементов, как обработать все элементы, если каждый элемент требует знания о состояниях каждого другого элемента этого списка?

Например, прямой способ реализовать это в Python может быть:

S = [1,2,3,4]
for e in S:
  for j in S:
    if e!=j:
      process_it(e,j)

но это очень медленно O (n²), если количество элементов огромно. Должен быть другой эффективный способ, включающий также параллелизм. Вы можете мне помочь?

Answer 1

Если вам нужно обработать каждую пару элементов, есть O (n ² ) пар, поэтому вам нужно будет сделать столько звонков!

Если вам нужны только комбинации (ab, ac, bc), а не все перестановки (ab, ba, ac, ca, bc, cb), то вы можете сделать это, чтобы вдвое сократить количество вызовов (и пропустить if):

for idA,val in enumerate(items):
    for idB in range(0, idA):
        process_it(val,items[idB]) 

Единственный способ улучшить это - найти способ сломать вашу process_it рутину, чтобы она могла работать на нескольких парах. Без дополнительной информации мы мало что можем предложить.

Answer 2

Пригодность данной задачи для многопроцессной обработки зависит от характера задачи и взаимозависимости (или ее отсутствия) различных подзадач, not on способ составления списка подзадач .
Другими словами, используя формулировку вопроса, способность этой проблемы не быть такой медленной на с участием параллелизма зависит от факта что метод process_it () таков, что:

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

И это не зависит от того факта, что порядок, в котором последовательность вызовов process_it () производится декартовым произведением списка (вопрос Every-to-Every вопроса) или каким-то заранее составленным списком, или каким-либо другим способом.

Кроме того, сложность проблемы (O (n ^ 2) в вопросе) не уменьшается, поскольку задача решается многопроцессно . Фактически, многопроцессная логика часто вносит дополнительную сложность («платить» за организацию и подачу нескольких потоков и объединять их результаты); однако такая сложность обычно имеет другой порядок величины проблемы (скажем, постоянная или, возможно, линейная по n) и, следовательно, не меняет общую сложность.

Не связано с возможностью разделения процесса на несколько асинхронных подзадач, может быть так, что сложность задачи может быть уменьшена , как подсказано в некоторых других ответах (например, если process_it (a, b) совпадает с process_it (b, a)), или если базовые данные таковы, что их сортировка может уменьшить количество вызовов process_it и т. д. .)

Кроме того, и хотя некоторые языки программирования или библиотеки / среды упрощают управление многопроцессорной обработкой, вопрос, как правило, не зависит от языка; возможно, тег python и иллюстративный фрагмент каким-то образом запутывают проблему.

Answer 3

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