最优二维数据结构

Question

我已经认真考虑过这个问题，但实际上还没有想出什么。

假设我想要一个 m X n 的元素集合，可以按任何列和任何行进行排序，并且在 O(m*n) 以下的时间内插入或删除一行... 是否有可能？

我想到了一个链接网格(linked-grid)的方法，其中节点被插入到向量中以便我可以为它们编制索引，并将第一行和第一列编入索引，以消除在任何一个方向上遍历列表的必要性。使用我的方法，我已经实现了以上的复杂度，但我只是想知道是否有可能通过非常数因子进一步减少复杂度。

排序的示例:

1 100 25 34
2 20  15 16
3 165 1  27

按第三行排序：

25 1 34 100
15 2 16 20
 1 3 27 165

按照第一列排序：

 1 3 27 165
15 2 16 20
25 1 34 100

- Vanwaril

---

不，完全不是。我的数据结构课是去年的事了。但如果是这样，那又有什么关系呢？我是在问解决方案还是答案呢？在你的道德准则内，一个关于编程问题是否可以在一定的时间复杂度内解决以及使用哪些数据结构的问题不还是可以回答的吗？ 为什么那些没有明确应用的问题会被立即贴上作业的标签呢？ - Vanwaril

Answer 1

我会创建两个索引数组，一个用于列，另一个用于行。因此，对于您的数据：

1 100 25 34
2 20  15 16
3 165 1  27   

你需要创建两个数组：

• cols = [0, 1, 2, 3]
• rows = [0, 1, 2]

然后，当你想要通过第三行对矩阵进行排序时，你保持原始矩阵不变，只需相应地更改索引数组：

• cols = [2, 0, 3, 1]
• rows = [0, 1, 2]

现在的技巧是使用一次间接访问来访问矩阵。因此，你不再使用 m[x][y] 访问它，而是使用 m[cols[x]][rows[y]] 来访问它。在重新排序行/列数组时，你也必须使用 m[cols[x]][rows[y]]。

这样，排序的复杂度为 O(n*log(n))，访问的复杂度为 O(1)。

对于数据结构，我建议使用一个带有指向另一个数组的链接的数组。

+-+
|0| -> [0 1 2 3 4]
|1| -> [0 1 2 3 4]
|2| -> [0 1 2 3 4]
+-+

为了插入一行，只需将其插入到最后一个位置，并相应地更新rows索引数组，确保正确的位置。例如，当rows为[0, 1, 2]并且您想在最前面插入它时，rows将变为[3, 0, 1, 2]。这样插入一行的复杂度为O(n)。

要插入列，也将其添加为最后一个元素，并相应地更新cols。插入列的复杂度为O(m)，插入行的复杂度为O(n)。

删除同样是O(n)或O(m)，这里只需将要删除的列/行替换为最后一个，然后从索引数组中删除该索引即可。

- martinus

---

但是插入和删除元素的时间复杂度为O(mn)，而行的插入和删除的时间复杂度为O(m^2n)。 - Vanwaril

嗨Vanwaril，我已经更新了条目，我认为插入和删除也可以在O(n)或O(m)中完成。 - martinus

Answer 2

补充一下martinus和Mike的回答：你需要的是本质上的枢轴转换，这正是他们所建议的，并且在几乎所有涉及矩阵的数值算法中都使用了这个非常著名的技术。例如，您可以快速搜索“带有部分枢轴的LU分解”和“带有完全枢轴的LU分解”。存储排列的附加向量称为“枢轴”。

- d..

Answer 3

如果我遇到这个问题，我会创建行和列重映射向量。例如，为了对行进行排序，我会像往常一样确定行的顺序，但不是复制行，而是改变行重映射向量。

它看起来会像这样：

// These need to be set up elsewhere.
size_t nRows, nCols;
std::vector<T> data;

// Remapping vectors.  Initially a straight-through mapping.
std::vector<size_t> rowMapping(nRows), colMapping(nCols);
for(size_t y = 0; y < nRows; ++y)
    rowMapping[y] = y;
for(size_t x = 0; x < nCols; ++x)
    colMapping[x] = x;

// Then you read data(row, col) with
T value = data[rowMapping[row] * nCols + colMapping[col]];

顺便提一下，一个小优化是在rowMapping中存储指针而不是索引。这将使您能够执行T value = rowMapping[row][colMapping[col]];，但是每次data的维度发生变化时都必须重新计算指针，这可能会出现错误。

- Mike DeSimone

---

再次强调，虽然访问和排序速度很快，但插入和删除的速度却不快。 - Vanwaril

如果您预先分配行和列，则插入和删除的时间复杂度为O(n)。此外，快速插入和删除并未被指定为要求。 - Mike DeSimone

Answer 4

您可以使用哈希表并插入 (i,j) -> node，其中 (i,j) 是包含 2 个整数的二元组。您可以编写自己的自定义类，该类定义了 Equals 方法和 GetHash() 方法 ... 或者 Python 免费为您提供。

现在... 您到底是什么意思 - 可以按行或列排序？请给出一个带有值的示例！

- Hamish Grubijan

---

我想到了哈希表，但是排序变得非常麻烦。 - Vanwaril

不，这并不麻烦，但它需要O(m*n)的时间。 - Hamish Grubijan

那么，你的意思是使用哈希表而不是我的向量，但这没有任何区别，因为向量仍然是摊销常数时间插入。节点结构仍将需要4个指针，并且排序和插入逻辑仍将需要处理它们。 - Vanwaril

我不是C++大师。我的感觉是，有时候C++的复杂性会妨碍开发。我喜欢更简单的实现方式，因为它们更不容易出错。在我看来，Python + dict正好可以做到这一点。另外，你的插入/删除行的速度有多快？最后，如果你正在使用C++，请将其添加为标签。 - Hamish Grubijan

@Hamish：我并不太关心实现的编程语言（尽管我使用了C++）。我正在寻找所有单个单元格/行插入和删除操作可达到的最优复杂度。 - Vanwaril

Answer 5

也许可以为此创建一个小型数据库？

数据库排序算法可能比重新发明轮子更好，MySql就行。为了提高性能，表可以在内存中创建。然后您可以像通常的表一样对列进行索引，并让数据库引擎完成脏活（如排序等）。然后您只需获取结果即可。

- oscar

---

这个问题实质上是关于如何实现一个提供这些服务的数据库系统。说“使用数据库”是没有回答的。 - Phil Miller

这取决于你如何理解这个问题，如果是 a）“我该如何对我的MxN矩阵进行排序？”，还是 b）“矩阵排序算法的本质是什么？” - oscar