有效地发现列表元素的差异

Question

我正在尝试找到列表的元素与该列表的每个元素的所有元素之间的差异。我认为这就是我的描述吗？让我们使用一个示例：

idx = [1, 4, 8, 10, 22]

基于这个问题，只需将元素扎在一起，这将是足够简单的，但这只会导致每个元素的成对比较，而我需要对每个元素进行多个成对比较。

我的方法是执行以下操作：

diffs = [abs(i-j) for i in idx for j in idx]

但这效率非常低。计算以下所有元组的差异的最有效方法是什么？

comparisons = [(1,4), (1,8), (1,10), (1, 22), 
               (4,8), (4,10), (4,22), 
               (8,10, 8,22)]

注意：

我更喜欢使用基本Python 2.7的答案，但也想知道如何使用Numpy做到这一点，因为我敢肯定，该软件包使其更容易。

Answer 1

您可以编写一个生成器：

idx = [1, 4, 8, 10, 22]
def differences(nums):
    n = len(nums)
    for i in xrange(n-1):
        for j in xrange(i+1,n):
            yield abs(nums[i]-nums[j])
for d in differences(idx): print d

输出：

3
7
9
21
4
6
18
2
14
12

这会一一产生差异，几乎没有内存开销。另外，使用@RoryDaulton的想法，这不会打扰计算冗余或已知为零的差异。

Answer 2

请注意，您的结果实际上将容纳n*n元素。因此，如果您的长度是25,039（如评论中所述），则必须注意不要使用这6.3亿个元素击中MemoryError。

一种方法是numpy并选择一个足够小的 dtype：

import numpy as np
arr = np.array(your_list, dtype=np.int16)
diffs = arr[:, None] - arr   # this will be a 25039 x 25039 array containing your desired differences.

即使使用np.int16，您也需要大量内存（我在此处使用了25000的数组大小）：

>>> diffs.nbytes
1_250_000_000

如果您在int32上进行操作，则大致需要2.5GB才能保持结果 - longs（pythons默认值（如果您不在无限的精度整数范围）中），则可以忽略5GB，忽略任何python对象。请注意，int16的值范围仅为−32768到32767，因此您可能需要在需要时选择较大的DTYPE。

除了记忆发行外，还无法以此类操作的效率来击败Numpy。我的计算机上大约需要1.2秒才能计算25k x 25k的差异。

---

如果您需要差异小于某些值的事件数量，则Numpy再次提供了一个简单的解决方案：

num = np.sum(np.abs(diffs) < some_value)