我有一个非常稀疏且规模巨大的表格。
也就是说，我的表格索引可能非常大，但表格中的元素数量非常少。
我一直在考虑如何处理这个数据结构。
我排除了使用行x列的表格，因为它占用了太多的内存，并且查找行/列中所有元素需要太多的时间。
相反，我想到了使用两个映射：行和列。
让我们看一下行。密钥是行索引，键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)方法可以做到这一点？
n个非零条目，则您需要检查的平均单元格数量为sqrt(n)，我相信。（我在Stackoverflow的某个答案中写了一个证明 - 如果您需要，我可以查找它。）c^2*m*k/2 = O(m*k)次操作。我们有，因此平均操作总数为，而对于此处提出的解决方案，则为O(sqrt(n))。同样，如果假设矩阵大致为正方形，例如m*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)增长得更快，例如像sqrt(m)或c*m。rows map的每个条目都是一个数组；链表会得到相同的复杂度，因为在列表中找到正确的列需要线性时间。你可以通过使用自平衡树来表示每行和每列，而不是数组，这样你每行就可以获得O(log(k))的操作，而每列则需要O(m * log(k)) = O(sqrt(n)*log(n))的时间，在矩阵不太远离正方形的情况下。虽然仍然不如这个树结构好，但如果你确实需要最好的性能，实现一下看看实际效果可能是值得的。c，那么密集矩阵表示法也会进行O(sqrt(n))次操作，因此渐近行为应该是相同的。常数系数将取决于c，因此你需要同时实现两者才能确定哪个更快。sqrt(n)个元素才能找到哪些元素在给定的行/列中。你能解释一下吗？ - batman让我们看看你的理解是否正确:
当删除一行时，您只需将其关联的列列表设置为空。但在执行此操作之前，为什么不使用该列表来处理该列表中每个列的行列表？
一个简单的例子。假设您有以下矩阵:
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 [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)，但仍存在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
由于您主要使用 cols 映射只是为了尽快计算列数，而不是从中获取数据，我建议创建一个带有嵌套映射和 colCount 映射的 table，而不是使用 rows 和 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}
然后，当您删除行k时，只需递减在该行中找到的每个列的计数器。以下是一些伪代码：
for key in table[k].keys()
colCount[key] = colCount[key] - 1
delete table[k]
cols 的目的不仅仅是为了计算列中元素的数量。 - batman
O(<# 行中的条目数>*<# 行中元素列的条目数>)。在平均情况下，这可能少于几个操作。 - clwhisk