有效的方法来实现每一个到每一个互动？

给出一个元素列表，如果每个元素都需要关于这个列表中每个其他元素的状态的知识，那么如何处理所有元素？有效的方法来实现每一个到每一个互动？

例如，直接的方式来实现它在Python可能是：

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

但它是非常缓慢的O（N²）如果要素的数量是巨大的。还必须有另一种有效的方法，包括并发。你可以帮我吗？

2010-02-18 psihodelia

如果你的起始算法是O（n^2），并且你可以简化它，那就去做吧。实现语言的关注与此是正交的。 – jldupont 2010-02-18 13:29:49

如前所述，没有通用的方法可以让这一切变得更好。现在，实际上，元素实际上只需要事先知道从所有元素计算出的* some *其他元素或* summary information *。它可能会变得更快。但是这个问题并没有提供足够的信息来推测什么是正确的把戏。 – 2010-02-18 15:48:40

如果您需要处理每一对物品，则有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你日常所以它可以在多个对工作的一种方式。没有更多的信息，我们可以建议的不多。

2010-02-18 13:29:52

一个确定的选择是让它在FPGA中实现，并使它们同时工作。除此之外 - 如果没有例外，并且确实需要所有 - 而不是“需要一些”，那么您将被判为标准方法。

2010-02-18 14:05:36

给定任务的适用性，以在多进程的方式进行处理依赖于性质任务和相互依赖的（或缺乏）的各种子任务，不上的方式生成子任务列表。
换句话说，利用问题的措词，对于这个问题的能力，不会那么慢通过涉及并发取决于以下事实process_it（）方法或者是这样的：

而且它不依赖于一个事实，即顺序的一系列调用到process_it（）由列表的笛卡尔积（该每到每一个问题的）或生产通过一些预先建立的清单或其他方式。

另外，的问题（在问题为O（n^2））的复杂性不会减少，因为该问题在多处理方式递。事实上，多进程逻辑经常会引入额外的复杂性（为了组织和提供多个线程并组合它们的结果“付费”）;然而，这种增加的难度通常是问题的其他数量级（例如常数，或者可能是n的线性），因此不会改变整体的复杂性。

无关到进程的能力，以在多个异步子任务被分割，它可能是这样的，该问题的复杂性可以降低，如在一些其他的答案暗示（例如，如果process_it （a，b）与process_it（b，a）相同，或者如果基础数据是先排序它可以减少process_it需要调用的次数等）。

另外，编程语言或库/环境可以更容易地管理多处理，这个问题通常是语言不可知的;也许python标签和说明片断会以某种方式混淆问题。

2010-02-18 14:31:36 mjv

回答