缓存友好的数据结构

就是 cache friendly data structure。不知道如此中译是否合适了。

之前在 cJSON 链表的缺陷 文中提到过双向链表很可能是 cJSON 的 array 添加 item 所存在的效率问题的原因。

这次在解 POJ 的时候也遇到了同样的问题。于是就顺便做下代码示例。
题目是 POJ3253,Fence Repair简单而言解法利用 Huffman 编码的思想。

看如下两个实现:

我首先写出的是 std::vector 的实现,提交后顺利通过。注意41行至52行的在已排序数列中插入元素的算法用二分查找会更快,但目前也不影响AC。
然后,注意到程序中完全没有使用数列的随机存取功能(上面只使用了线性搜索而非二分搜索),于是打算改用列表实现来节省 std::vector 的 erase 和 insert 造成的内存复制的额外开销。将 std::vector 换成 std::list,代码对应有少量修改。接下来出乎意料的是,提交后直接超时。
于是在本地简单用随机数据测试,20000大小的数据,列表实现要比数组实现慢近10倍,几乎全部的CPU时间都花在46行的 merge 函数上。内存访问对性能的影响极其显著。

关于缓存友好这个问题本身,个人并没有看到特别专门的论述。
一个简单的建议是注意时间和空间的局部性(temporal locality and spatial locality),因为这两点就是缓存的软硬件实现的基本思想。
另一个更全面的参考是著名的 What Every Programmer Should Know About Memory。其中一章有详尽介绍。

Advertisements
This entry was posted in Computer and Internet, Programming and Algorithm and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s