以优化方式计算列表元素间的所有可能差值

Question

我有一个列表，里面又包含了很多小列表，比如说 [[0], [1, 1], [4, 2, 4], ...]。我想要逐个查看每个小列表，然后创建一个新的列表，这个新列表里包含了每个小列表中数值之间的所有差值。以这个例子来说，最后得到的列表会是：

differences = [[0], [0, 0, 0, 0], [0, 2, 0, -2, 0, -2, 0, 2, 0],....]

我已经用一种比较简单的方法实现了这个功能，里面用了三个嵌套的 for 循环。第一个 for 循环用来遍历所有的小列表，另外两个 for 循环则是用来在某个特定的小列表中找出所有可能的差值。

我在想有没有人能想出一个更快的算法，让这个过程运行得更高效呢？谢谢！

Answer 1

正如评论中明确指出的，对于一个包含 n 个元素的子列表，你无法做到比 O(n^2) 更快的速度。不过，你可以稍微提高效率，比如你提到的只进行 n(n-1) / 2 次减法。

下面是你想法的具体化：

假设有一个大小为 n = 3 的子列表 L = [a,b,c]。

考虑一个大小为 n X n 的矩阵 A 来存储这些差值。这样一来，

A = |a-a  a-b  a-c| = |   0      a-b   a-c|
    |b-a  b-b  b-c|   |-(a-b)     0    b-c|
    |c-a  c-b  c-c|   |-(a-c)  -(b-c)   0 |

你只需要计算上三角部分，这里有 n(n-1) / 2 个值。对角线上的值都是 0。下三角的值可以从上三角填充，因为 A 是一个斜对称矩阵。

最后但同样重要的是，你需要按照行优先的顺序把 A 序列化，得到你想要的“差值列表” D。注意，a_{i,j} 的值会放在 D 的第 i*n + j 个位置。[我假设使用的是像 C 语言那样的从 0 开始的索引方式.]