performance - 在每个给定区域找到最小值的有效方法

Question

给定一个 我们首先定义两个实值函数 和 如下:

我们还为每个矩阵 X 定义了一个值 m(X) 如下:

现在给定一个 ，我们有许多 G 区域，表示为 .这里，G 的一个区域是由 G 的子矩阵组成的，该子矩阵是从 G 的某些列和某些行中随机选择的。我们的问题是计算 尽可能少的操作。有没有建散列表、排序之类的方法可以更快的得到结果？谢谢!

========================

例如，如果G={{1,2,3},{4,5,6},{7,8,9}}，则

G_1 could be {{1,2},{7,8}}
G_2 could be {{1,3},{4,6},{7,9}}
G_3 could be {{5,6},{8,9}}

=======================

目前，对于每个 G_i，我们需要 mxn 比较来计算 m(G_i)。因此，对于 m(G_1),...,m(G_r) 应该有 rxmxn 比较。但是，我注意到 G_i 和 G_j 可能重叠，所以会有一些其他更有效的方法。任何关注将不胜感激!

Answer 1

根据需要最小/最大类型数据的次数，您可以考虑在矩阵值之间保存最小/最大信息的矩阵，即在值之间的间隙中。因此，对于您的示例 G= {{1,2,3},{4,5,6},{7,8,9}} 我们将定义一个关系矩阵 R 大小为 ((mxn),(mxn),(mxn)) 并具有来自集合 C = {-1 = 小于，0 = 等于，1 = 大于}。

R 将有九个关系对 (n,1)、(n,2) 到 (n,9)，其中每个值都是 C 的成员。注意(n,n 已定义并将等于 0)。因此，R[4,,) = (1,1,1,0,-1,-1,-1,-1,-1)。现在考虑您的任何子集 G_1 ...，了解子集成员的位置关系将为您提供 R 的偏移量，它将解析为每个 R(N,,) 的索引，这将直接返回所需的关系信息而无需比较。

当然，您必须决定构建 R 的空间开销和计算开销是否超过每次只计算所需内容的成本。某些优化包括实现 R 矩阵沿主对角线反射(reflect)以及您可以声明要调用的“等于”，比方说，小于(意味着 C 只有两个值)是可用的。根据原始矩阵 G，如果知道行或列已排序，则可以进行其他优化。

并且由于某些计算机(大型机、 super 计算机等)以列优先顺序将数据存储到 RAM 中，因此存储您的数据集以使其填充行和列转置，从而允许列到列类型的操作(向量计算) 以实际支持列。检查您的架构。