java - 通过自定义Timsort能否有效提升这些场景下的性能？

Question

我正在处理的数据集的一些特征显示出以下趋势:-

1. 数组的前 50-70% 几乎已排序，最后 30% 已完全打乱。

   • 把插入排序部分换成shell排序会不会有效？
     

2. 数组的前 50-70% 几乎已排序，最后 30% 包含大量海龟。

   • 海龟的出现是否如此重要以至于我应该放弃 Timsort 以支持这种梳状排序变体 - here .他们的最佳案例表现显示为 O(n)，但 Tim 的平均案例表现更好用 O(n log n) 排序，而 Comb 排序有 Ω (n log n) 但这是否需要修改版的梳状排序或海龟密度考虑？
     

3. 与第二种情况相同，但如果可以提高性能，部分排序的输出就可以了。例如，一个包含 1,000,000 个元素的数组可以有其最小的 1%(即10,000 个元素)在数组的前 1% 个槽中，但不需要在内部排序。

   • 这可以通过在快速排序中的某个递归深度后拉出来完成吗？将元素大致放置在它们应得的位置附近。

如果相关，这是我正在尝试修改的 Java Timsort 代码 - code .

Answer 1

我认为最好的答案是无法可靠地预测自定义 TimSort 是否会为您的数据集带来有值(value)的性能改进。您只需要尝试一下就知道了。

我要重复我的评论中的建议:先分析它!

除非您分析了在代表性数据上运行的应用程序，否则您无法知道这是否有帮助。例如，如果计算仅花费其 5% 的时间对数据进行排序，则排序算法加速 50% 只会导致应用程序加速 2.5%。这根本不值得浪费您的时间。