计算机是怎么长出来的
总目录/ 第 1 部 电、逻辑与指令/ 1.5 数据怎么组织

CHAPTER 1.5 数据怎么组织:摆法决定速度

同样的数据,摆法不同,取一次的时间能差一百倍。这一章讲清楚差在哪

1.4 章讲的是「程序怎么被翻译成机器码」。这一章换个角度: 程序真正要处理的是数据,而数据得先有地方待着。 内存是一排编号的格子,你能做的只有「往第 N 号格子写」和「从第 N 号格子读」, 就这两件事。

所谓数据结构,就是把一堆数据摆进这排格子里,摆成什么形状、取的时候按什么规矩找。 摆得紧凑,一次搬回来的东西就多;摆得松散,插入就方便。 这个取舍在纸面上看不出来(都是 O(n),都是 O(1)), 落到真机上却能差五到十倍——因为现代 CPU 取一次内存要几十纳秒, 而算一次只要零点几纳秒,于是「取了几次」远比「算了几步」重要。

编号标题它解决什么状态
1.5.1 数组、链表、栈、队列:四种最基础的装东西的方式 下标为什么能直接算地址;链表为什么理论更快实际更慢;栈和队列只允许在哪儿动手 已完稿
1.5.2 哈希表:为什么它能一秒查到一百万人里的你 哈希函数在做什么;冲突了怎么办;为什么扩容要重新散列 已完稿
1.5.3 树与索引:数据库为什么能翻得那么快 二叉树、B 树、B+ 树各解决什么;为什么磁盘上的树要长得又矮又胖 已完稿
1.5.4 复杂度:为什么有的程序一秒钟能做完,有的要一年 大 O 到底在比什么;为什么常数因子常常比阶数更重要 已完稿
← 第 1 部目录