这些场景中的性能可以通过自定义Timsort来有效地提高吗？
这些场景中的性能可以通过自定义Timsort来有效地提高吗？
提问于 2012-10-07 09:50:52
我正在研究的数据集的一些特征特征显示了以下趋势：
- 前50%-70%的阵列几乎与最后30%的完全置乱排序。
- Will it be effective if I replace the insertion sort part with shell sort?
- 前50%-70%的阵列几乎被排序，最后30%包含了很多海龟。
- Does the occurrence of turtles matter so much that I should ditch Timsort in favor of this Comb sort variation - [here](http://en.wikipedia.org/wiki/Comb_sort#Combsort_with_different_end). Their best case performances show O(n) but avg case performance is better for Tim sort with O(n log n), whereas Comb sort has Ω (n log n) but does this take the modified version of Comb sort or density of turtles into account?
- 与第二个场景相同，但是如果能够提高性能，那么部分排序的输出是可以的。例如，包含1,000,000个元素的数组可以在数组的前1%槽中有最小的1% (即10,000个元素)，但不需要在内部排序。
- Can this be done by pulling out after a certain recursion depth in Quick sort to place the elements approximately near their deserved place.
如果是相关的话，下面是我正在尝试修改的Timsort 代码。
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-10-07 12:02:25
我认为最好的答案是，无法可靠地预测自定义TimSort是否会为您的数据集带来有价值的性能改进。你只要试试看就行了。
我将从我的评论中重复我的建议:先把它描述一下！
在对运行在具有代表性的数据上运行的应用程序进行分析之前，您无法知道这是否有可能有所帮助。例如，如果计算只花费5%的时间对数据进行排序，那么排序算法的50%的加速比只会导致应用程序加速2.5%。这根本不值得浪费你的时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12767750
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号