知识卡片
稀疏矩阵只存非零项
大型矩阵通常稀疏,绝大多数元素是 0。用列表的列表存储时,每个 0 也占一个位置,10 亿乘 10 亿的矩阵有 10 的 18 次方个条目,根本存不下。紧凑表示只记录非零位置:来自哪个矩阵、行号、列号、值,存储量与非零个数成正比,比稠密表示小好几个数量级。这种坐标形式的附带好处是适合分布式计算:遍历时只处理真实存在的数据,0 不产生任何中间键/值对,传输量与计算量都随非零数增长,而不是随矩阵维度的乘积增长。代价是随机访问变慢,需要额外的索引结构。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第25章 MapReduce · 查看原书依据
例如,一个 10 亿×10 亿的矩阵有 100 亿亿(10 的 18 次方)个条目,这很难在计算机上存储。但是,如果每行中只有几个非零条目,则此替代表示要小许多个数量级。
参考来源
- 位置:《数据科学入门(第2版)》第25章 MapReduce(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0029.xhtml)
- 结论依据:原文这一段直接给出本卡的核心判断:「例如,一个 10 亿×10 亿的矩阵有 100 亿亿(10 的 18 次方)个条……」
- 原始内容:例如,一个 10 亿×10 亿的矩阵有 100 亿亿(10 的 18 次方)个条目,这很难在计算机上存储。但是,如果每行中只有几个非零条目,则此替代表示要小许多个数量级。