0

我有这样的数据

row1: x1 x2 x3... xn, y1,y2,...yn
row2: x2,x3,....xj, y4,y5,...ym
.....
row 1 million, x6,x2,x7...xk, y2,y3,...yl

每一行，x和y的数量可以是一百万甚至更多

每一行，某些数量的 x 或 y 可以具有相同的值。就像第 1 行和第 2 行一样，x2 有共同点。

我的目标是找出哪一行给了我最小的 x 和 y 之和。例如，第 1 行的总和是 sum(x1+x2,..+xn+y1+y2+...yn)。

详尽的方法可以工作，但会很慢，因为会有一百万*一百万次操作，我相信有一些聪明的方法可以工作。

谢谢

更新：

实际上，上述问题来自矩阵分区：，给出一个如下所示的 5x5 矩阵

1 2 3 4 5
2 3 4 5 6
2 3 4 5 8
9 1 2 3 5
1 5 2 5 6

至少有五种方法可以将此矩阵划分为两个子矩阵，例如，

1 2 | 3 4 5
2 3 | 4 5 6
----+------
2 3 | 4 5 8
9 1 | 2 3 5
1 5 | 2 5 6

我得到两个子矩阵 

1 2
2 3

和

4 5 8 
2 3 5
2 5 6

所以实际上 1 2 2 3 是我提到的 x，而 4 5 8 2 3 5 2 5 6 是我提到的 y。所以每一行都是矩阵中的一种分裂。我不确定我是否清楚？请添加评论。

4

1 回答 1

0

从我上面看到的是 x 和 y 模式在两行上重叠，所以给定一个列表 {x1, x2, ... xn} 和 {y1, y2, .. ym}

给定 (1, n) 中的 i,j,k,l

和 (1, m) 中的 o,p,q,r

第一行是： { xi, xi+1, ... ,xj }{ yo, yo+1, ... , yp }

第二行是： { xk, xk+1, ... ,xl }{ yq, yq+1, ... , yr }

因此，您真正需要找到的是行之间的差异并进行比较，并且仅将其相加，因为重叠（具有相同值的部分）将具有相同的总和。

关于这两个列表，您还有什么可以告诉我们的吗？他们排序了吗？你知道 x 和 y 的列表与行无关吗？x列表中的值可以出现在y列表中吗？他们是否以任何方式排序？

知道这些东西会让你更快地弄清楚你需要什么。

如果不是，您将不得不走行并确定重叠。

更新：

这假设我们只通过对角线进行分解，但您可以将算法推广到其他算法。

使用上面的示例让我们看看我们是否可以工作，我按 x 和 y 集对数字进行分组。

第 1 行：{1}{3 4 5 6 3 4 5 8 1 2 3 5 5 2 5 6}
第 2 行：{1 2 2 3} {4 5 8 2 3 5 2 5 6} 所以我们添加到 x { 2 3} 来自第二列，{2} 来自第二行。
我们从 y 中删除了第二列的 {3 3 1 5} 和第二行的 {4 5 6}
第 3 行：{1 2 3 2 3 4 2 3 4}{3 5 5 6} 所以我们添加到 x { 3 4 4} 来自第三列，{2 3} 来自第三行。
我们从第三列的 y {4 2 2 } 和第三行的 {5 8} 中删除

注意我没有计算总和。只是与第 1 行的区别

因此，如果我们对除 1 之外的每一行进行概括。（如果您不需要总和，则根本不计算第 1 行）

对于 nxn 矩阵 M

延迟第 1 行 = 0；

对于 r = 2 到 r < n

对于 i=1 到 i <= r，并且 j=1 到 j < r（所以我们不计算 elemtn M(r,r) 两次）

增量行 r = 增量行 (r-1) + sum M(r, i) + sum M(j, r) - sum M(r, ni) - sum M(nj, r)

小于第 1 行的行将是负数。你可以只保留你所看到的最小的行增量，你会知道哪个 decomp sum 是最小的。

这有意义吗？

于 2012-05-01T12:16:37.690 回答