在每个给定的区域中寻找最小值的高效方法

Question

在每个给定的区域中寻找最小值的高效方法

performancealgorithmoptimizationhashmatrix

6

给定一个

，我们首先定义两个实值函数 enter image description here

和

，如下所示：

我们还定义每个矩阵的值m（X）如下：

enter image description here

现在，给定一个

，我们有许多区域G，表示为 enter image description here

。这里，G的一个区域由G的一些列和一些行中随机选择的子矩阵组成。我们的问题是尽可能少地计算 enter image description here

。是否有像构建哈希表或排序之类的方法来更快地获得结果？谢谢！

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

例如，如果 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可能重叠，因此可能存在其他更有效的方法。非常感谢您的关注！

- John Smith

1

编辑您的问题以提高可读性，否则我们将不会阅读它。 - High Performance Mark

12

我帮他编辑了。 - David G

2

@David：很遗憾你不能因为这样的惊人编辑而获得声望。但它确实有助于社区。 - ereOn

4

实际上问题是，为什么我们不能在这里拥有与math.stackexchange相同的功能？ - Mr Lister

1

@MrLister：我会说：是时候在 Meta 上问了 :) - ereOn

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Wes Miller · Accepted Answer

根据需要使用min/max类型数据的次数，您可以考虑在矩阵值之间即插值处保存min/max信息的矩阵。因此，对于您的示例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矩阵沿主对角线反射，并且可以声明“等于”被称为小于（表示C只有两个值）。根据原始矩阵G，如果知道行或列已排序，则可以获得其他优化。

由于一些计算机（大型机、超级计算机等）按列主序将数据存储到RAM中，请存储数据集以使其填充行和列转置，从而实际上允许列与列之间的类型操作（向量计算）支持列。检查您的架构。