我正在寻找最快的方法,从列表中获得所有可能的对组合之间的最小绝对差
我做了两个解决方案,但没有一个是可以接受的
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
解决方案
另一种可能让您更快获得结果的方法:
首先对值进行排序,然后对其进行迭代以找到最小差异:
使用numpy执行相同操作的速度更快:
机制
要处理的阵列:
让我们对数组进行排序:
获取值之间的差异:
取这些差值中的最小值,在本例中为0。这相当于原始阵列成对组合的最小距离
时代
以下是我的机器上的相应时间:
解释
有关其背后的原因,请参见@Yves Daoust的详细解释
是的,使用组合也可以对结果进行排序。然而,主要的操作不是排序,而是自己进行组合
Here您可以阅读有关
itertools.combinations
时间复杂性的更多信息与此相比,这里最昂贵的操作是排序,仅此而已
如果对元素进行递增排序,则最接近每个元素的是前一个元素或后一个元素。因此,尝试每一个连续的配对就足够了
这样做,您可以用O(n²)的复杂性换取O(n),这是一个显著的改进。除非您的数据允许基于非比较的排序,否则排序将采用O(n log n)并控制成本(仍然优于O(n²))
相关问题 更多 >
编程相关推荐