一个好的计算机工程师需要了解计算机的存储结构，特别是想要成为能够写系统程序的工程师，就必须对此有充分的了解，否则无法真正控制自己写的程序的执行效率——《计算之魂》
引言
例题1：给定一个32位或者64位的二进制，如何高效地输出其中1地数量； 例如：1001 1010 0000 0011 0001 0001 1010 1000 和0001 1001 1010 0000 1101 1010 0110 0011 分别有11个1和14个1
解题思路：
- 最直观地解法为顺序遍历，时间复杂度为O(n)；
- x & (x-1) 算法，可以降低平均运行时间，但是最糟糕地情况还是O(n)；
- “空间换时间”思想，将二进制数以8位为一个单元，分成n/k(k=8)部分，将8位二进制对应的256种可能性存为哈希表。即时间复杂度降至O(n/k)；
进阶思考：是否k越大越好呢？
答案是否定的：因为真实的计算机中，处理器通常从高速缓存（cache）的存储器中读数据，高速缓存的容量很小，存不下很大的数据。（例如酷睿i7-3770k处理器，单核第一级高速缓存的容量只有32KB）当缓存存不下时，只能存到内存当中，这样一来读取的速度就会慢一个数量级；
顺序访问和随机访问
顺序访问：适合读或写大量的数据；
随机访问：访问任意一个特定的数据；
例题2：高频单词二元组问题 如何用一台服务器从海量文本（语料库）中，比如1TB的数据中，统计出频率最高的100万个单词二元组；
工程上行不通的方法：
- 定义二维数组存储每个二元组出现的次数；
假设20W个单词，即20W * 20W的二维数组，存储每个二元组出现的次数需要4字节，共需要1600亿个字节，即160GB，内存存不下；
- 利用哈希表存储所有的二元组；
占用的存储空间太多，1TB原始文本，将二元组统计一遍，结果存起来需要1/4 ~ 1/2TB（齐普夫定律）
- 优先队列也不能实现，优先队列只能统计前100万个出现的，不能统计出现频率前100万的二元组
工程上的近似实现：
- 随机抽样1GB，占比0.1%，统计前1000万二元组，假定前100万个出现在这1000万个二元组中，不在的不进行考虑；
- 利用齐普夫定律来限定范围，近似估算；先统计词频进行排序，含有低频词的二元数组不考虑；
工程上的精准实现：
利用分治算法+哈希表进行实现；
将数据划分为1000份后，每一份为1GB数据，相应的哈希表内存就装的下了。
然后对二元数组进行排序，批量写回磁盘进行顺序存储（其中磁盘备份时间占主要，计数和排序相比微不足道）
然后双指针归并两个不同的序列（序列的选取也可以读一部分、处理一部分、写一部分）合并为一个序列后，利用寻找中值的做法（利用快速排序的思想）找出前100万个频率最高的二元组（MapReduce单机版的思想）
解决这个问题的关键，就是如何尽可能地将算法中需要随机访问存储器地部分，用顺序访问存储器的方式代替； 核心思想有两个：首先是将大问题分解成很多小问题，这是分治算法的灵魂；其次是在第二步合并时，按照结果（二元组序列）的编号把结果文件分为多份，而不是按照原始的数据进行划分。这样做的优点是，结果的每一个部分之间没有重复，省去了很多存储空间和计算时间——《计算之魂》
处理器的多级存储
衡量存储器的性能需要考虑三个指标：
- 大量顺序访问数据时的速率，这在通信上称为传输的宽带；
- 访问一个存储单元的时间；
- 一次访问的准备时间；
从CPU高速缓存到云存储分级
- 第一级高速缓存L1有64KB的容量，其中一般用于存储指令，一般用于存储数据。只要四个时钟周期就可以完成一次数据的访问，同时i7四核处理器有四路指令通道和八路数据通道，这样正好保证一个时钟周期可以读入一个指令，同时读入两个数据。一般英特尔处理器上L1缓存未命中率在5%~10%
- 第二级高速缓存L2有256KB的容量，不分指令和数据，L的访问时间为10个时钟周期，设置了八个通道，基本保证两个时间周期为计算提供一个数据。为什么比L1慢：L1距离处理单元物理距离更近，他们之间的电路连接更加直接；L1缓存容量较小，而缓存访问时间和容量的开方成正比。
- 第三级高速缓存L3有8MB，每个核上2MB，需要35个时间周期，有16个数据通道；
- 内存：常见的有16/32GB内存，处理器访问一次内存的时间通常在100个时钟周期以上；
- 硬盘：硬盘容量要比内存大两到三个数量级，但是从硬盘上访问数据时，数据传输速率比内存低两个数量级左右（这还是大量顺序读取数据的速度，单次大约需要10毫秒）
- 云存储：云存储背后是大量磁盘列阵，数据访问和传输速率受限于网络，而网络又比服务器内部慢一个数量级
缓存和内存适合随机访问，而外部存储设备和云存储只适合顺序访问，而且每一次读写的量需要很大才能有效率。
《计算之魂》中描述的真实案例 问题：查找N元组的列表很大，查找时占据90%以上的运行时间；如果缓存命中率低，需要不断地访问内存。 优化方案：1.根据用户输入引导到不同的服务器中，每个服务器存储不同字母开头的短语，提高缓存命中率；2.根据用户历史搜索不同关键词的频率，将常见短语做成很小的模块，能够适合高速缓存的容量，剩余短语做成很大的模块。
索引：地址和内容
哈希表容易实现随机访问数据，但是很难根据所查询的内容（比如数值）实现顺序访问；
有序索引则相反，容易实现顺序访问，但访问单个数据时需要进行折半查找；