想出以矩阵形式处理巨型数据的数据结构(可以把它想象成一个excel表)
问题是要想出一个可以与巨大的excel工作表一起工作的数据结构(显然不适合主内存)
假设下面的内容是excel表格的一部分，其中e表示一个空单元格。
A B C D ...
1 3 9 e e ...
2 e e e e ...
3 e e 5 e ...
4 e e e e ...
5 e e 6 e ...因此，数据结构应该允许我将excel表存储到内存中(我们知道只有excel表中的值才能放入主内存)，并支持以下操作
getByColumn(Column col); -给出某一列的所有值，比如C列的5,6
getByRow(Row row); -给出某一行的所有值，比如第1行的值为3和9，甚至更多
insertCell(Column col, Row row, int value); -插入或覆盖单元格的值
getExcelSheet(FileName); -以压缩形式给出整个excel工作表(数据结构)
这是一种可以想象的数据结构？我正在为面试做准备，这不是家庭作业。WOuld喜欢从不同的人那里获得一些见解。
只是给出一个感觉:假设excel表是1TB，我们有8 8GB的内存。1 the的excel工作表只有许多空单元格，但值分布在不同的单元格中。
回答 4
Stack Overflow用户
发布于 2012-10-01 05:20:44
使用映射/字典将单元格坐标映射到值，对于未明确设置的所有内容，返回默认值EMPTY_CELL。
在此基础上实现所需的方法。
Stack Overflow用户
发布于 2012-10-01 09:03:13
有大量关于sparse matrices主题的文献，这是一个被广泛使用的术语，您所说的巨大的Excel工作表。文献涵盖了数据结构以及用于创建和修改数据结构的合适算法；Wikipedia文章为您的研究提供了一个很好的起点。它可能会告诉你足够的信息来为面试做准备。
Stack Overflow用户
发布于 2012-10-01 16:53:07
Tass的评论和Mark的回答(对于which +1)的详细说明：
如果你使用维基百科所说的Dictionary Of Keys或DOK (本质上就是Jens的答案)，你就可以有效地插入单元格值，但正如你正确评论的那样，getByRow和getByColumn将会相当慢。
一个更好的选择是维基百科所说的坐标列表或COO:一组三元组(rowindex，columnindex，value)。实际上，您可能会将其存储为三个数组。为了快速插入，保留一组排序和未排序的条目，并插入到未排序的集合中；每当未排序的条目的数量超过阈值T(可能取决于非空单元格的总数K)时，将它们排序到已排序的集合中。
您可能希望将它们全部按行索引进行排序，并将另一个具有索引的数组保存到数组中，以提供按列索引排序的版本。
对于getByRow，您将获取按行索引排序的数组的正确部分，并在未排序的集合中进行搜索。
所有这些都假设您确实有足够的内存来为矩阵中的每个非空条目存储几个单词。如果不是，则需要将其与某种外部存储器方法相结合。
https://stackoverflow.com/questions/12667836
复制
腾讯云开发者
