4

我有一张非常稀疏的桌子，尺寸很大。

即，我的表的索引可能非常大，但表中的元素数量非常少。

我一直在为此考虑一个数据结构。

我排除了rows x cols表格，因为查找行/列中的所有元素需要太多内存和太多时间。

相反，我想到了使用两个地图：rows和cols。

让我们看看rows。键是行索引，键的值是 rowk中所有元素的列号列表k。

示例（1 表示那里存在一个元素）：

0 1 0
1 0 1

将是这张rows地图：

0: [1]
1: [0, 2]

我会保留一个类似的cols映射，其中键是列号，键的值k是列中所有元素的行号列表k。

当我想删除k表中的一行时，我会这样做： del rows[k]

但这不会从cols地图中删除顶点。我将不得不遍历删除某些元素的所有列，并从cols地图中删除每个元素。

有没有O(1)办法做到这一点？

4

5 回答 5

2

解决这个问题的一种非常非正统的方法是将矩阵实现为k d-tree，k = 2。您可以通过访问与该行或列相交的所有单元格来删除该行或列；如果矩阵是正方形并且它有非零条目，我相信n您需要检查的平均单元格数是。sqrt(n)（我已经在 Stackoverflow 上的一些答案中写了一个证明——如果你需要，我可以查一下。）

以非常相似的方式，您可以使用四叉树；我理解这些术语的方式是，不同之处在于单元格边界是预先定义的，以始终在四叉树中将 x 和 y 范围分成两半（对于每个非叶子中的四个相同的子单元格），而节点确定k d-tree中的边界（对于每个非叶中的两个不同的子单元）。

我认为对于这两个版本，此解决方案的性能以复杂的方式取决于稀疏性。首先，如果数据确实非常稀疏，例如，每行/列的平均非零条目数远少于一个，那么此解决方案将比您建议的解决方案更节省内存，但可能更少省时。c如果非零条目的数量是条目总数的某个恒定比例，并且您的矩阵是m * k，则此解决方案可能更有效：对于您的解决方案，要删除一列，您需要平均更改c*m行列表。对于每个这样的行列表，您需要找到您的列所在的位置，并将其后的所有条目向前移动。这是每行中的平均c*k/2 = O(k)条目，总共c^2*m*k/2 = O(m*k)操作。我们将有n = c*m*k，因此平均操作总数将是，而对于此处提出的解决方案c*n/2 = O(n)而言，它将是。O(sqrt(n))同样，如果您假设矩阵大致为正方形，例如m*m，并且每行/列f(m)平均有非零条目（因此n = f(m)*m），那么操作数O(f(m)^2)适用于您的解决方案和O(sqrt(m*f(m)))这个解决方案；这意味着，如果f(m) = ω(m^(1/3)). （请注意，这是一个小写的 omega；它基本上意味着，f(m)渐近地增长得比 快m^(1/3)，例如 likesqrt(m)或c*m。）

（我假设rows地图的每个条目都是您的解决方案中的一个数组；链表会给出相同的复杂性，因为在列表中找到正确的列需要线性时间。您可以通过让每一行和列表示，不是由数组，而是由一个自平衡树 - 然后你可以摆脱O(log(k))每一行的操作，并且O(m * log(k)) = O(sqrt(n)*log(n))假设矩阵离正方形不太远。仍然不比这个树业务更好，但如果您真的需要最佳性能，可能值得实施以查看它在实践中的工作原理。）

如果你的矩阵的密度确实是一个常数c，那么密集的矩阵表示也会进行O(sqrt(n))运算，所以渐近行为应该是相同的。常数因素将取决于c，所以再一次，您需要同时实现两者以确定哪个更快。

为了使四叉树解决方案具有良好的性能，您还需要不将非零值集中在一个小区域中；分布不需要特别均匀，只要不是非常集中即可。

如果您还希望频繁添加和删除任意条目，那么k d-tree 很难做好 - 我认为没有简单的方案可以使树平衡本身，如红黑或 AVL 或类似一维树。四叉树仍然可以工作。

于 2013-10-10T22:39:22.820 回答
1

让我们看看我是否理解您的内容：

  • 对于每一行，您维护一个被占用的列的列表。
  • 对于每一列，您维护一个被占用的行列表。
  • 这些结构中的每一个都足以描述矩阵。

当一行被删除时，您只需将其关联的列列表设置为空。但在此之前，为什么不使用此列表来处理该列表中每一列的行列表呢？

一个简单的例子。假设您有以下矩阵：

   1 0 0 0 1 1
   0 1 0 0 0 0
   0 1 1 0 0 0
   0 0 0 0 0 1

每行的列列表将是：

   0 [0, 4, 5]
   1 [1]
   2 [1, 2]
   3 [5]

每列的行列表将是：

   0 [1]
   1 [1, 2]
   2 [2]
   3 []
   4 [0]
   5 [0, 3]

如果要删除第 2 行，那么您将处理与该行关联的列列表，在这种情况下：2 [1, 2]. 这些是行列表将包含“2”的列。不需要查看其他行列表。

   Delete row 2: 
    -Column list for row 2: [1, 2]
    -Remove row '2' from the row list for columns 1 and 2
    -Set column list for row 2 to []
   done.

更新后的列列表为：

   0 [0, 4, 5]
   1 [1]
   2 []   <== updated
   3 [5]

更新的行列表是：

   0 [1]
   1 [1]  <== updated
   2 []   <== updated
   3 []
   4 [0]
   5 [0, 3]

这两种结构都描述了以下矩阵：

   1 0 0 0 1 1
   0 1 0 0 0 0
   0 0 0 0 0 0
   0 0 0 0 0 1

这不是您正在寻找的 O(1) 算法，但它对于非常稀疏的矩阵应该是相当有效的。

于 2013-10-11T19:39:59.203 回答
0

好吧，我一直在思考和思考，我认为这是可能的。

然而，解决方案并不理想，因为它可能在一开始是 O(1)，但 O(n) 依赖仍然存在，但是对于某些类型的数据和使用，它应该接近恒定时间。因此，这取决于它是否对您有用（与数组长度和/或操作数量相比，更改的数量要少得多）。

对于每次删除，您应该将更改添加到“更改列表”中。例如，您删除行号。10，所以你添加到你的列表中：“10 号以上，减去 1”。

在计算正确的行时，您必须通过“更改列表”进行减法/加法。

此外，您还需要一个数组，其中包含最后使用的减去/添加的数字和“更改列表”的数量，因此您不必计算已为该行计算的更改。

在最坏的情况下，它仍然是“a*n”，其中 a 是某个常数。

例子 ：

rows, cols = 1000;
delete(row,573);
//=> list_of_changes[0] = {573, 'deleted'}
access_row(581)
//=> help_array[581] = {-1, 1}
//=> help_array.structure = {"how much add/subtract on this line", "number of changes used"}
access_row(581)
//=> look at the help_array[581] seeing having used 1 change,
//   the size of list_of_change is 1, so you don't have to count
//   anything, using the -1 value. - constant time

当然，如果我删除 row[0] 然后访问所有 0..998 值，这将是 O(n)，因为它必须计算 n 次 help_array。

于 2013-10-10T17:43:44.727 回答
0

Donald Knuth 的舞蹈技巧总是有的。您在每一行和每一列都使用双向链表。删除行或列需要与行或列中的元素数量成线性关系的时间。

于 2013-10-17T02:04:24.397 回答
0

由于您对cols地图的主要用途是尽可能快地计算列数，而不是从中获取数据，因此我将创建一个table带有嵌套地图的地图，以及一个colCount地图而不是rowsand cols。

此解决方案比 O(1) 更接近 O(n)，但您不会在row x cols结构中出现浪费的循环。

因此，对于您的示例，table将如下所示：

{0: {1:"Value"},
{1: {0:"Value", 2:"Value"}}

colCount看起来像这样：

#Each column in the example only had one value

{0:1,
 1:1,
 2:1}

然后，当您删除 row 时k，您只需为该行中找到的每一列递减计数器。这是一些伪代码：

for key in table[k].keys()
    colCount[key] = colCount[key] - 1
delete table[k]
于 2013-10-10T21:11:31.877 回答