100GB url 文件，使用 1GB 内存计算出出现次数 top100 的 url 和出现的次数。
TOP N、分治、最小堆、多线程、mmap、BKDRHash、crc32
本题目整体使用 TOP N 问题的解题方法，使用 map-reduce 的**解决。
第一步将URL分类放到k个不同的哈希桶。时间复杂度：O(n)，空间复杂度：O(n)。
第二步在不同的线程下统计不同哈希桶下的各个URL的数量，并放入最小堆。 限制最小堆容量为100，URL数量比最小的数更小则不放入堆中。 时间复杂度：O(n)，空间复杂度：O(1)。
第三轮，合并不同哈希桶产生的最小堆。最后得到的最小堆依次输出即为TOP 100 的倒序排列。
在 partition.c 中，我使用 mmap 实现了100G文件直接映射到内存。
传统使用 fread 的方式，实际上是依靠不断调用系统调用 read 实现的。
在用户态和系统态之间频繁切换，带来了更多的资源消耗。
使用 mmap 优势在于：
- 一次映射就够，直接用指针就可以操作；
- 完全不需要考虑内存是否充足问题，内存页的分配由内核负责，不会占用过多的内存空间；
- 文件I/O在内核中完成，读的速度更快。
实际运行时，大多数情况下只占用 308KB 的物理内存。
在遍历过程中，循环只是不断寻找换行符 \n。
当找到 \n 时，则可以计算当前URL的字符串的末尾、大小以及下一个URL的起点。
我使用了特别制作的 BKDRHash 函数，直接用 mmap 内存中的 URL 计算 Hash 值。 本部分大约占用 partition 部分约 30% 的计算资源，因此可以考虑使用其他计算量更小的Hash算法。
对于桶文件（bucket file），我一样用 mmap 的实现方法。
但是，与前者不同的是，桶文件映射的内存空间不仅需要读权限，也提供写权限。
我对全部的桶文件，提供一个默认的尺寸，阈值为 待处理URL文件尺寸 / 桶的个数。
当然，为了便于内存管理，该阈值是以页的大小 PAGE_SIZE 的倍数。
通过 ftruncate 函数，很方便生成指定大小的文件。
写URL到桶文件的实现，其实就是 memcpy 从原文件的映射空间复制到桶文件的映射空间。
同时也带来一个好处，分隔符变为了 \0，更方便下一轮使用 strlen 计算URL长度，更方便从桶文件中抽出 URL。
针对已经写超过阈值的情况，在初始版本中将使用 fwrite （带缓冲区的写）实现，后面有更好的实现办法。
第一步可以实现多线程，由于时间原因，在后期改进中增加思路。
在第一步中，我们已经形成了 k 个包含了全部URL的桶文件。
由于第一步中使用哈希函数将不同的URL分别放到不同的桶中。 因此，每一个桶中的URL绝对不会在其他桶文件中出现，直接统计这个桶中的URL的数目就已经是最终的个数了。
统计时需要使用 hashmap 实现 KV 存储。Key 为 URL，Value 为当前该URL已经出现的次数。
在实际使用中，我选了一个公有领域的 hashmap 实现。它使用 crc32 计算Hash，当出现碰撞时使用链表遍历。
每匹配到一个URL，就获取该URL的已经出现的次数。加1后再放回到 hashmap。
为了减少 hash 的计算，当该 key 已经被找到时，get 函数将会直接返回存储节点，这样在 put 的时候就不需要重新寻找该节点了。
每个桶完成统计后，将会遍历整个 hashmap，将全部URL和次数对放入限制容量为100的最小堆。
最小堆满容量后，插入新的KV，将只会记录当前V比最小堆中最小的数还大的情况，确保最小堆中的全部成员都是当前桶的TOP 100。
原理很简单，就是遍历各个最小堆的全部的成员，插入到一个新的限制容量为100的最小堆。
为了节省资源，实际使用第一个桶内存在数目的最小堆作为基准。 其他桶的最小堆最终都睡插入到基准的最小堆中。
该处理非常快，多次测试仅在1s之内完成。
Device:
- CPU: 2.8 GHz Intel Core i7
- Disk: APPLE SSD AP0512M
- Go version: go version go1.12.9 darwin/amd64
ONE thread, 100G:
partition time: 1571243 ms (26min 11s)
reduce time: 3132900 ms (52min 12s)
merge time: 0ms
通过 DTrace 性能分析可以知道：
- partition 阶段有大约 30% 的时间在计算Hash，约 15% 的时间进行内存复制，少量时间计算
fwrite； - 当某个桶溢出时，
fwrite的时间占比大幅增加，影响写的速度； - 未使用多线程，计算跟不上读写。
因此，可以改进的部分有多线程、Hash 算法和桶满了之后分配新的内存空间。
通过 DTrace 性能分析可以知道：
- hashmap 中的 crc32 算法占用 reduce 的 58% - 99% 的时间，由于 hashmap_get 和 hashmap_put 都需要重复计算；
- 未使用多线程，计算跟不上读写。
因此，可以改进的部分有多线程、Hashmap的实现。
最小堆的合并基本不占时间。根据 8:2 原则，可以忽略优化。
通过测试结果和分析的结论可以看出，实际上计算的效率不及读写的效率。 由于目前只是单核计算，所以可以通过多线程的方式实现更高效的计算。
最容易实现多线程的是 reduce，每一个桶都是独立的统计单位，可以用单独的线程跑 traversing 函数。
partition 多线程实现稍微复杂，可以通过提前计算不同的分片的起始点和终点，并行计算不同分片的 partition。
最直接可以优化的部分是 get 和 put 重复计算 Hash 的问题。
【已实现】在 get 阶段可以直接返回底层存储的节点指针，在 put 阶段直接修改节点的值，即可减少目前一半的时间。
其次，利用多线程计算不同桶数据的问题。
目前，partition 使用的 BKDRHash 消耗的时间比 crc32 更多。能否使用 crc32 替代 BKDRHash？还需要继续优化。