Effective ways to implement Every-to-Every interaction?

Question

Given a list of elements, how to process all elements if every element requires knowledge about states of every other element of this list?

For example, direct way to implement it in Python could be:

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

but it is very slow O(n²) if number of elements is huge. There must be another effective way, involving concurrency as well. Can you help me?

Answer 1

If you need to process every pair of items, there are O(n²) pairs, so you will have to make that many calls!

If you only need the combinations (ab, ac, bc), not all the permutations (ab,ba,ac,ca,bc,cb), then you can do this, to halve the number of calls (and skip the if):

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

The only way to improve it is to find a way of breaking down you process_it routine so it can work on multiple pairs. Without any more info, not much we can suggest.

Answer 2

One sure option is to get it implemented in FPGA and have them all work concurrently. Other than that - if there are no exceptions and really -all- need -all-, not "some need some", you're sentenced to the standard approach.