algorithm - 如何在保持顺序的同时用较小的值替换条目？

问题描述

什么是替换图像中的值同时最小化最大值并保持顺序的有效算法？

背景

我有一个 8.5Gb 的图像，它表示为行和列。

假设我们有一个较小的版本（输入中没有重复）：

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

我需要将每个像素的条目替换为整个矩阵中可能的最小正值（大于零），同时保留行和列排序。一种可能的输出（此处允许重复）如下，最大值为 5（我不相信我们可以将其减少到 4）：

  2, 3, 4,
  1, 2, 3,
  5, 4, 1

它起作用的原因：

输入：第一行：4 < 5 < 9和第一列：4 > 2 < 8

输出：第一行：2 < 3 < 4和第一列2 > 1 < 5（列）

订单正在维护中。其他行和列也是如此：

5 > 3 < 6  <=> 3 > 2 < 4
...
...

-----------------------------------------尝试：我的算法错误---- -------------------------------------

1.每一行和每一列都将包含独特的元素。因此，从第一行开始并分配范围内的整数{1, total the number of rows}：

1 2 3
x x x
x x x

该行中的最大值当前为 3。

2.转到下一行 2,3,7 并再次分配范围内的数字{1, total number of rows}。当我们分配 1 时，如果存在冲突，我们会查看所有先前的行。在这种情况下，前一行中已经存在 1。我们需要一个小于 1 的数字。所以在此处放置一个零（稍后我将抵消每个条目）。

 1 2 3 
 0 1 2
 * * *

该行中的最大值当前为 2。

3.转到下一行，再次如上填写。但是 1 之前已经出现过，我们需要一个大于第一行和第二行的数字：所以，尝试 2。下一个数字需要大于 2 和 1（列）且小于 2（行）。这是一个巨大的问题。我每次都需要更改太多单元格。

标签： algorithmmaxrowcell

解决方案

为了清楚起见，我将为您的每个值加 10。

 Input      Ordering     
14 15 19     - - -
12 13 17     - - -
18 16 11     - - -

按从小到大的顺序考虑每个值。每个元素接收一个排序值，该排序值是该位置可用的最小整数。“可用”是指分配的数字大于同一行或列中的任何数字。

11 和 12 不在同一行或同一列，所以我们可以立即分配它们。

 Input      Ordering     
14 15 19     - - -
12 13 17     1 - -
18 16 11     - - 1

当我们考虑 13 时，我们看到它与 a 在同一行1，因此它必须具有下一个更大的值：

 Input      Ordering     
14 15 19     - - -
12 13 17     1 2 -
18 16 11     - - 1

14 有同样的问题，高于 a 1：

 Input      Ordering     
14 15 19     2 - -
12 13 17     1 2 -
18 16 11     - - 1

对每个数字继续此过程。取该数字的行和列中的最大排序。添加 1 并分配该排序。

 Input      Ordering     
14 15 19     2 3 -
12 13 17     1 2 -
18 16 11     - 4 1

 Input      Ordering     
14 15 19     2 3 4
12 13 17     1 2 3
18 16 11     5 4 1

有一个解决方案。“优势”路径 18 > 16 > 15 > [14 或 13] > 12 表明 5 是最低的最大值。

您还可以通过将位置转换为有向图来解决此问题。同一行或同一列的节点有一条边连接它们；边缘从小到大。对这些值进行排序并仅连接相邻的值就足够了：给定 14->15 和 15->19，我们也不需要 14->19。

向没有其他输入边的每个节点添加一个0带有标签和边的节点。0

现在遵循一个典型的标签迭代：所有输入都被标记的任何节点都会收到一个比其最大输入多一个的标签。

这与上面的算法相同，但正确性和极简主义更容易看出。

14 -> 15 -> 19
12 -> 13 -> 17
11 -> 16 -> 18
12 -> 14 -> 18
13 -> 15 -> 16
11 -> 17 -> 19
0 -> 11
0 -> 12

现在，如果我们摆脱这个拓扑，从左边开始，我们得到：

0  11  13  17
   12  14  15  16  18
               19

这使得编号很明显：每个节点都标有从起始节点开始的最长路径的长度。

你的记忆问题应该被编辑到你的问题提案中，或者作为一个新问题给出。您沿行和列具有非平凡的依赖关系。如果您的数据不适合内存，那么您可能需要创建一个磁盘托管数据库来存储您的预处理数据。例如，您可以将图形存储为由依赖项键入的边列表：

您还没有描述数据的形状。在最坏的情况下，您应该能够构建此图形数据库，只需一次执行行，然后每列执行一次 - 或每次执行多列，具体取决于您一次可以放入内存的数量。

然后您可以将该算法应用于数据库中的项目。如果您将其保存在内存中，则可以加快速度，不仅是所有没有依赖关系的节点，还有另一个几乎没有依赖关系的列表——“很少”取决于您的内存可用性。

例如，对数据库进行一次遍历以获取具有 0 或 1 个依赖项的每个单元格。将独立节点放入您的“活动”列表中；当您处理这些时，仅在“1-dependency”列表中添加节点，因为它们已被释放。一旦你用尽了这些子图，然后进行大量传递以（1）更新数据库；(2) 提取具有 0 或 1 个依赖关系的下一组节点。

让我们用你给出的例子来看看这个。首先，我们从原始图表中制作几个列表：

0-dep  11, 12
1-dep  13 (on 12), 14 (on 12)

这个过程很简单：我们分配1给单元格 11 和 12；2到单元格 13 和 14。现在更新图表：

节点 dep 完成（分配值） 15 无 2、2 16 15 1 17 无 1、2 18 16 2 19 15、17

刷新内存列表：

0-dep  15, 17
1-dep  16 (on 15), 18 (on 16)

在此过程中， 15 和 17 都依赖于具有 value 的节点2，因此它们都被赋值3。解析 15 释放节点 16，该节点获得 value 4。这反过来又释放了节点 18，它获得了 value 5。

在最后一次通过中，我们现在有节点 19，没有未解决的依赖项。它的最大上游值是3，所以它得到了值4。

在最坏的情况下——你甚至不能一次将所有独立节点保存在内存中——你仍然可以尽可能多地抓取，在内存中分配它们的值，然后返回磁盘以获取更多信息过程。

你能从这里处理数据操作吗？

algorithm - 如何在保持顺序的同时用较小的值替换条目？

问题描述

解决方案

推荐阅读