知识卡片
边列表换成邻接表
社交网络最直接的存法是边列表:每对 ID 一条记录,如 (0,1)、(0,2)。缺点是查“1 的朋友有哪些”必须扫描全部记录,边越多越慢,而这类查询在后续每一步都要反复做。改成邻接表——以用户 ID 为键、朋友 ID 的列表为值——只在构建时遍历一次全部边,之后每次查询都是按键取值,代价是与边数成正比的内存和一次性的建表时间。这是典型的“预处理换查询速度”:读多写少时值得,若图会频繁增删边,则要额外维护两侧的对称关系(给 i 加 j 时也要给 j 加 i,漏掉一边就得到有向图,度会算错)。同样的手法用于兴趣数据,就得到“兴趣→用户”与“用户→兴趣”两个方向的索引。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第1章 导论
原书出处 · 1 处
- 第1章 导论 · 查看原书依据
将朋友关系表示为成对的列表项并不是最简单的表示方法。如果要找到用户 1 的所有朋友,你必须迭代每个元组对以寻找哪个包含 1。如果你有很多元组对,则会需要很长时间。
参考来源
- 位置:《数据科学入门(第2版)》第1章 导论(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0005.xhtml)
- 结论依据:原文这一段直接给出本卡的核心判断:「将朋友关系表示为成对的列表项并不是最简单的表示方法……」
- 原始内容:将朋友关系表示为成对的列表项并不是最简单的表示方法。如果要找到用户 1 的所有朋友,你必须迭代每个元组对以寻找哪个包含 1。如果你有很多元组对,则会需要很长时间。