我正在寻找一种在线算法来处理比我可以合理存储的更多的数据。
我只想保留n值v[n]小于任何后续值的数据点。（数值通常在增加。）
这样做的明显方法（不是说唯一的方法，或正确的方法）是使用堆栈。对于每个新点，当它们的值大于当前点的值时，从堆栈中弹出点，然后将当前点压入堆栈。
但是数据非常稀疏。在快速测试中，每 TB 仅节省了大约 3 MB。
问问题
41 次
1 回答
1
您可以分块处理数据。定义一个块的大小，以保证预期的结果大小适合它。所以如果我们说一千万个值被认为是一个块，那么我们也说最小值的数量永远不会超过一千万。然后进行如下操作：
- 预留一个数组来存储 1000 万个值
- 只要有更多数据，就不断重复以下步骤
- 用输入值填充数组的空闲部分
- 向后遍历整个数组以找到最小值。正如您所指出的，这可以在没有堆栈的情况下完成。它可以在数组中就地完成，方法是将找到的最小值保存在数组的右侧。
- 将这些最小值移动到数组的开头，在数组的右侧留下一个空闲部分，可以在下一次迭代中用新的输入值填充。
最后，您将在数组的开头找到最小值。
这可以通过在到达包含先前迭代结果的数组部分时停止向后迭代来优化，并且要与之比较的值也来自该部分。然后应将数组右侧的部分移到数组中此点之后。
该算法可以比您的堆栈版本运行得更快，假设读取数组中的一大块输入数据可以非常快地完成，并且将数组的一部分向左移动也可以非常快地完成（memcopy 类型的操作） .
于 2021-09-15T18:46:32.703 回答