对所有可能的组合执行操作的最快方法

Question

我正在寻找最快的方法，从列表中获得所有可能的对组合之间的最小绝对差。

我做了两个解决方案，但没有一个是可以接受的。

arr = [x for x in range(10000)]
minAbsDiff1(arr)
minAbsDiff2(arr)

def absDiff(elem):
    return abs(elem[0]-elem[1])

# first solution takes 5.96 sec
def minAbsDiff1(arr):
    seq = itertools.combinations(arr, 2)
    m = min(seq, key=absDiff)
return absDiff(m)

# second solution takes 6.96 sec
def minAbsDiff2(arr):
    seq = itertools.combinations(arr, 2)
    test = [abs(tup[0]-tup[1]) for tup in seq]
return min(test)

输入示例：[3，-7，0]

所有组合：（3，-7），（3，0），（-7，0）

输出最小abs差值：3

解释： 3-0=3

Answer 1

如果对元素进行递增排序，则最接近每个元素的是前一个元素或后一个元素。因此，尝试每一个连续的配对就足够了。

这样做，您可以用O（n²）的复杂性换取O（n），这是一个显著的改进。除非您的数据允许基于非比较的排序，否则排序将采用O（n log n）并控制成本（仍然优于O（n²））。

Answer 2

另一种可能让您更快获得结果的方法：

首先对值进行排序，然后对其进行迭代以找到最小差异：

def minAbsDiffSorted(arr):
    sorted_arr = sorted(arr)
    min_val = sorted_arr[-1] - sorted_arr[0]
    for i, j in zip(sorted_arr[:-1], sorted_arr[1:]):
        min_val = min(min_val, j - i)
    return min_val

使用numpy执行相同操作的速度更快：

import numpy as np
def minAbsDiffNumpy(arr):
    return np.diff(np.sort(np.array(arr))).min()

要处理的阵列：

import numpy as np
import random
arr = np.array([random.randint(0, 100) for _ in range(20)])
>>>
array([55, 76, 88,  2, 68,  9, 24, 50, 15, 86, 19, 31, 80, 39, 14, 48, 32,
       32, 35, 26])

让我们对数组进行排序：

arr = np.sort(arr)
>>>
array([ 2,  9, 14, 15, 19, 24, 26, 31, 32, 32, 35, 39, 48, 50, 55, 68, 76,
       80, 86, 88])

获取值之间的差异：

np.diff(arr)
>>>
array([ 7,  5,  1,  4,  5,  2,  5,  1,  0,  3,  4,  9,  2,  5, 13,  8,  4,
        6,  2])

取这些差值中的最小值，在本例中为0。这相当于原始阵列成对组合的最小距离。

以下是我机器上的相应时间：

%%timeit
minAbsDiff1(arr)
17.3 s ± 438 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
minAbsDiff2(arr)
19.1 s ± 1.16 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
minAbsDiffSorted(arr)
7.85 ms ± 498 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit
minAbsDiffNumpy(arr)
444 µs ± 3.73 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

背后的原因，请参阅@Yves Daoust详细解释。

是的，使用组合也可以对结果进行排序。然而，主要的操作不是排序，而是自己进行组合。

在这里，您可以阅读有关itertools的更多信息。组合时间复杂度。

与此相比，这里最昂贵的操作是排序，仅此而已。