原则:了解数据

我们谈到了很多通用行为,这些行为需要作用在某些数据之上。也许你需要对数据排序来实现一个特定的顺序,也许你需要在数据之中搜索以定位某些特殊的信息。你的数据可能是可以随机访问的(也就是说,可以在任何时候读取任何一块数据),也可能只能通过迭代器来顺序访问(每次只能处理一个元素)。如果你不了解数据的特性,就只能使用一些较为通用的算法。

如果你需要对数据排序,没有“一刀切”的方法可以总能获得最好的性能。表11-1汇总了第4章谈到的排序算法的结论。你是要对一个整数集合进行排序,而这些整数的范围是有限的吗?那么最快的算法莫过于计数排序了,尽管它比其他算法需要更多的存储空间。你需要对已经几乎有序的复杂数据进行排序吗?那么插入排序将更适合。你需要关心那些相等元素的相对位置?那么你需要稳定排序算法。你确定数据提取自均匀分布吗?那么你一定要试试桶排序,因为它能够利用这个特性来获得额外的性能提升。如果你对这些都十分了解,那么就能够通过数据来选择最合适的算法。

阅读 ‧ 电子书库