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

Question

我正在使用的数据集的一些特征显示出以下趋势：-

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

   • 如果我将插入排序部分替换为shell排序会有效吗？
     

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

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

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

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

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

Answer 1

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

我将重复我的评论中的建议：首先描述它！

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