数据结构案例 — 同一份成绩单,四种装法Copy Anchor Link

这一章讲一件事: 四种数据结构都学完了,可写一个真程序时,到底该用哪个? 原书的办法是干脆不选——同一份成绩单数据,用四种结构各装一遍, 让每种结构的长处和别扭自己暴露出来。读完你会拿到一张「什么场景用什么结构」的选 型直觉,和一张操作快慢的对照表。

1. 这一章讲什么、在全书链条里的位置Copy Anchor Link

这是第三篇(数据结构)的收尾章。第 11–14 章每一种结构都是单独讲的: 列表一章只讲列表,集合一章只讲集合。单学的时候每种都好用; 难的是它们挤在同一个问题里的时候——这份数据该进列表还是进字典?

原书给了一个统一考场:一个班级的成绩册(grade book)¹。十个学生、两次考试, 四个任务——存记录、筛子集、去重、按名查分——每个任务都让四种结构轮流做一遍。

2. 顶层全景:一份数据,四条流水线Copy Anchor Link

  原始数据:names(10 个学号)+ scores1、scores2(两次考试的分数)
      │
      ├─ 装进 list   → 榜单、子集、改字母等级      「顺序与修改」的强项
      ├─ 装进 tuple  → 同样的事,记录变成只读        「改不动」是特性不是缺点
      ├─ 装进 set    → 两次考试出现过哪些分、交集    「去重与集合运算」的强项
      └─ 装进 dict   → 按学号直接查分、两次分装一起  「按键查找」的强项

  图说:同一批原料,四条流水线,产出的东西不一样。

主线例子全程用同一批数(这些数来自原书的一次实际运行): 学生是 STU100 到 STU109 共 10 人;第一次考试的分数是 [85, 66, 89, 87, 100, 98, 86, 93, 74, 66](由程序随机产生,所以每次运行不一样, 书里印的是它那一次跑出来的结果)²。

3. 核心原理:四个机制,各走一遍主线例子Copy Anchor Link

3.1 造数据:随机数加一行推导式Copy Anchor Link

案例不让你手敲十个名字。它用两道工序造数据:

第一道工序,import random 之后用 random.randint(60, 100) 每次随机抽一个 60 到 100 之间的整数当分数。

第二道工序,名字列表用一行推导式生成:['STU' + str(i) for i in range(100, 110)] ——把数字 100 到 109 逐个转成字符串、前面拼上 STU,十行字一眨眼写完。

书里还埋了一个细节:数据规模写在一个叫 SIZE 的变量里(取值 10), 并且全大写的变量名是这本书定的规矩,表示「常量」——一个设定之后不该再改的数³。

3.2 用列表装:顺序、修改、筛选三板斧Copy Anchor Link

第一种装法,成绩册是一个列表,每个元素本身又是一个小列表 [名字, 分数]:

  gradebook = [['STU100', 85], ['STU101', 66], ['STU102', 89], … 共 10 行

原书给了两种造法,结果一模一样⁴:一种是老实的循环加 append(); 另一种是一行推导式 [[name, score] for name, score in zip(names, scores1)]—— zip() 把两个列表按位置配对,一次配出一对名字和分数。

列表在这里展示了它的三板斧,每板都砍在主线例子上:

注意第四板:先把 10 个分数加起来除以 10 得到平均分,再回头筛—— 分数低于平均的是 66、74、66 三行⁵。

最后一道工序,把分数换算成字母等级(A/B/C/D/F)。原书的做法很巧: 先写好一张对照表 letters = ['F','F','F','F','F','F','D','C','B','A','A'], 然后用 letters[score // 10] 查表——// 是整除:85//10 得 8,查第 8 项是 'B'; 100//10 得 10,查第 10 项是 'A'。一行 // 加一张表,把五个分支全省了⁶。

3.3 用元组装:同一套操作,记录焊死Copy Anchor Link

第二种装法,只是把内层的小列表换成小元组 (名字, 分数)。 造法、筛法、换算字母等级,每一行都和列表版几乎一样,推导式原样照搬⁷。

那为什么要换元组? 回看第 12 章的结论:元组是只读容器。 成绩一旦录入就不该被程序改花脸——这是「改不动」反而是卖点的那种数据。 这一章的用意正在于此:同一道题,列表做得顺的地方,元组一样做得顺; 两者真正的差别不在「能不能做」,而在「允不允许改」。

3.4 用集合装:去重与集合运算是主场Copy Anchor Link

第三种装法才真正换赛道。把两次考试的分数各自装进集合:

  set1 = {66, 74, 85, 86, 87, 89, 93, 98, 100}   (10 个分数,重复的 66 只剩一个)
  set2 = {60, 64, 67, 72, 73, 75, 91, 92, 97}    (第二次考试,无重复)

注意 set1 只有 9 个元素:原数据里 66 出现了两次,集合自动只留一份⁸。 然后三问,正好是第 13 章的三件套:

• 并集 set1 | set2:两次考试一共出现过多少种分数?18 种。
• 交集 set1 & set2:两次都考出过的分数?空集——set(),一个都没有。 书里特意印了这个结果,因为它反直觉:两次都 60–100 分,居然没有重合的分数。 这就是随机数的脾气,也正是集合能一句话答上来、列表答不上来的那种问题。
• 差集 set1 - set2:只在第一次出现过的分数?9 种,也就是 set1 全部。

3.5 用字典装:按名字查,一步到位Copy Anchor Link

第四种装法,按键值对存:{'STU100': 85, 'STU101': 66, …}。 它的主场是查:问「STU103 考了多少?」,直接 d1['STU103'],87,一步⁹。

接着加码:把两次考试合到一个字典里,值从小数字换成小列表—— {'STU100': [85, 75], 'STU101': [66, 60], …}。 然后筛「两次都上 90 的学霸」:推导式里写 if d3[s][0] >= 90 and d3[s][1] >= 90],筛出来只有一个人——STU104: [100, 97]¹⁰。

这个嵌套结构值得多看一眼:字典的值可以是任何东西,包括列表。 「名字 → 列表」两层结构,是真实数据分析里最常见的第一形态。

4. 作者的判断与证据Copy Anchor Link

作者明说的: 选结构看场景——「We select a data structure for a specific scenario based on its time and space complexity」(我们按时间和空间复杂度为具体 场景选数据结构)¹¹。这是全书第一次出现「复杂度」这个词,作者紧接着就摆手: 这本书不展开讲,只给一张表,想深究的自己去网上找资源。

表里给了什么证据: 一张四种结构的操作快慢对照表(下节展开)。这是全书唯一 一处用数字比较结构的地方——虽然用的是大 O 记号这种「相对比较」而非秒表实测。

我们的解读(不是书里的): 这一章的教法本身是证据——它不讲理论,而是让你 亲手把同一份数据装四种箱子。装过一遍的人不会问「哪个结构最好」, 只会问「我这个动作在哪个箱子上最快」——而这就是作者那张表要回答的问题。

判断(我们的,不是书里的): 「同一道题四种装法」是入门阶段最划算的练习 设计——四种结构的知识点在第 11–14 章是分散的,只有同台对打一次, 它们的边界才真正立起来(交集为空这个结果,列表要绕好几个弯才能答)。 如果错,会错在: 成绩册场景天然偏向列表和字典(有顺序、要按名查), 元组和集合的长处(只读安全、去重)在这个场景里显得勉强——若只按这一章的经验 选型,会低估元组和集合在别的场景(坐标记录、标签系统)里的主场优势。

5. 边界与局限Copy Anchor Link

大 O 表只给了结论,没教怎么读。 表上写的 O(1)、O(n) 这些记号,原书没有解释 含义,只推荐给想深入的人去网上找资源¹¹。这是有意的留白——对入门书来说, 记住「查字典快、在列表里按值找人慢」这个结论比会推公式要紧。我们把读法补在下面。

「随机数每次运行都不一样」既是特点也是麻烦。 成绩单数据由 random.randint 现场抽,你照着书跑一遍,得到的分数和书里的对不上——书里自己也印了 「eliminated to save space」式的省略。别慌,这不是书印错了。

规模实验只开了个头。 章末「Furthermore」一节只留了一句话:把 SIZE 从 10 改成 100、1000、10000,自己动手感受四种结构在数据变大时的差别¹²。 怎么感受、看什么指标,没有下文——这是一次没给实验手册的实验。

6. 可带走的Copy Anchor Link

1. 选型口诀:要顺序和修改用 list,要只读用 tuple,要去重和集合运算用 set, 要按名字查用 dict——这一章用同一道题把这四句话演了一遍;
2. zip(名单, 分数) 按位置配对,是「把两列数据合成记录」的标准动作;
3. 字母等级那种多分支换算,可以压成「整除定位 + 查表」:letters[score // 10];
4. set(列表) 一行去重;|、&、- 三个符号就是「或、且、减」的集合版;
5. 字典的值可以是列表,「名字 → [分数1, 分数2]」是成绩单的标准装法;
6. 全大写变量名(SIZE)在这本书里表示常量——设定后不该再改;
7. 大 O 记号读法(补充,不在书里):O(1) 表示无论数据多大都一步搞定, O(n) 表示数据翻几倍、操作就慢几倍;表上 dict 和 set 的查找是 O(1), list 按值找人(如 remove)是 O(n)——所以「按名字查」是字典的主场¹³。

7. 原文地图Copy Anchor Link