知识卡片
排序基准须覆盖输入分布
排序方案应考虑规模、有序程度、重复率、键类型、稳定性、空间限制与最坏延迟。比较字符串可能需要读取多个字符,不能总按常数成本处理;近乎有序也需描述扰动的数量和距离。
基准应覆盖随机、有序、近有序及针对枢轴策略的不利输入,并在目标机器上测量。表中以插入、快排、堆和桶排序给出初步选择,但实际顺序取决于实现与输入。
104的字符串表比较随机、有序、三中值对抗和两类局部交换数据;03233–03234注明对抗数据中的三中值快排仅10次实验并去掉极值,其他通用描述为100次去掉极值。表中并未列出插入排序,因此不能直接从这些表验证文中对插入排序的速度说法。
105的03237–03241列出随机、有序、枢轴不利和两种局部扰动的双精度数据结果;应检查输入分布与NaN等排序规则,再在目标环境比较,不能把固定历史时间直接当成当前性能。
257在凸包排序中比较堆排序与快排;堆排序保证最坏 O(n log n),实际平均速度应在目标环境测试,不能绝对断言哪一种最优。
299的03466汇总排序算法;计数排序需计入键域k,桶排序期望性能依赖分布与桶内算法,二者都不能无条件写为最坏 O(n)。稳定性和更新需求也影响选择。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 排序基准须覆盖输入分布
- · 综合分析基准测试结果
- · 双浮点数的基准测试结果
- · 结论
- · 原则:了解数据
原书出处 · 5 处
- · 查看原书依据
选择排序算法的标准 选择一个排序算法时,考虑表4-6的定性标准。这些标准可能能够帮你做出最初的决定,但是你需要更多量化标准作为指引。 在为不同的数据选择合适的算法的时候,你需要知道输入数据的一些性质。我们创建了一些基准测试数据来比较本章所讲述的算法。注意表中的实际值是并不重要的,因为它们和基准测试运
- · 查看原书依据
综合分析基准测试结果 因为插入排序和选择排序是本章中在随机均匀数据(提升一些数量级)最慢的两个算法,所以我们在表4-7~表4-11中忽略这两个算法。但是,这两个算法值得处理有序数据(表4-8)和几乎有序数据(表4-10和表4-11)。插入排序比其他算法表现要好,通常要快一个数量级。为了得到表4-7~
- · 查看原书依据
双浮点数的基准测试结果 使用双浮点数的基准测试(表4-12~表4-16)消除了很多字符串比较时候产生的总开销我们再一次在这些表中忽略了插入排序和选择排序。
- · 查看原书依据
堆排序获得最好的平均性能,而不是冒着性能有时会退化到O(n2)的危险使用快速排序。但是在平均情况下,快速排序比堆排序好,所以你可以考虑一下快速排序最坏情况发生的概率。
- · 查看原书依据
了解数据 我们谈到了很多通用行为,这些行为需要作用在某些数据之上。也许你需要对数据排序来实现一个特定的顺序,也许你需要在数据之中搜索以定位某些特殊的信息。你的数据可能是可以随机访问的(也就是说,可以在任何时候读取任何一块数据),也可能只能通过迭代器来顺序访问(每次只能处理一个元素)。如果你不了解数据