同样的数据,摆法不同,取一次的时间能差一百倍。这一章讲清楚差在哪
1.4 章讲的是「程序怎么被翻译成机器码」。这一章换个角度:
程序真正要处理的是数据,而数据得先有地方待着。
内存是一排编号的格子,你能做的只有「往第 N 号格子写」和「从第 N 号格子读」,
就这两件事。
所谓数据结构,就是把一堆数据摆进这排格子里,摆成什么形状、取的时候按什么规矩找。
摆得紧凑,一次搬回来的东西就多;摆得松散,插入就方便。
这个取舍在纸面上看不出来(都是 O(n),都是 O(1)),
落到真机上却能差五到十倍——因为现代 CPU 取一次内存要几十纳秒,
而算一次只要零点几纳秒,于是「取了几次」远比「算了几步」重要。
| 编号 | 标题 | 它解决什么 | 状态 |
|---|---|---|---|
1.5.1 |
数组、链表、栈、队列:四种最基础的装东西的方式 | 下标为什么能直接算地址;链表为什么理论更快实际更慢;栈和队列只允许在哪儿动手 | 已完稿 |
1.5.2 |
哈希表:为什么它能一秒查到一百万人里的你 | 哈希函数在做什么;冲突了怎么办;为什么扩容要重新散列 | 已完稿 |
1.5.3 |
树与索引:数据库为什么能翻得那么快 | 二叉树、B 树、B+ 树各解决什么;为什么磁盘上的树要长得又矮又胖 | 已完稿 |
1.5.4 |
复杂度:为什么有的程序一秒钟能做完,有的要一年 | 大 O 到底在比什么;为什么常数因子常常比阶数更重要 | 已完稿 |