用于从大列表计算所有差值的算法

Question

我有一个问题,现在我有一个300万条记录的列表,我希望得到每两条记录之间的所有差值.一个简单的嵌套循环可能需要永远.任何人都可以建议我能够处理这个问题的算法吗？

Answer 1

如果要计算所有绝对差异的平均值并对时间戳进行排序,则只需要一个循环:

t[i] <= t[i + 1]    -->    abs(t[i] - t[j]) = t[j] - t[i]    for    i < j

也就是说,对于每个N时间戳差异,存在具有正号的加数和具有负号的另一个加数.让我们看一个有4个时间戳的例子:

sum = (t[3] - t[2]) + (t[3] - t[1]) + (t[3] - t[0])
    + (t[2] - t[1]) + (t[2] - t[0]) 
    + (t[1] - t[0])

在这里,t[3]总是添加,t[2]添加两次并减去一次,t[1]添加一次并减去两次,最后t[0]总是减去最低值.

矿石,更一般:第一个时间戳,即具有最低值的时间戳,总是负号,N - 1时间.第二个有N - 2负号和正号一次,即比较第一个时间戳时.第三N - 3次有负号和正号两次.

所以你的循环是这样的:

sum = 0;
for i = 0 to N:
    sum = sum + (2*i - N + 1) * t[i]

其中i是从零开始的索引和N独有的上限,C风格.要获得平均值,除以(N - 1) * N / 2.

如果你的数组没有排序,你必须先对它进行排序,这通常比二次时间具有更好的性能,所以你应该比使用嵌套循环更好.

可能发生的一件事是,通过总结大值,您可以达到数据类型的极限.您可以尝试通过将循环减半并从两端开始求和来解决这个问题,希望差异可以取消.或者,您可能已经除以循环内部的差异总数,可能会引入一些令人讨厌的浮点舍入错误.