Эффективные способы реализации взаимодействия 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

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

Answer 3

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

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

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

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

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

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