为什么奇偶分裂“更快”？用于归并排序？

发布于 2024-11-09 22:34:34 字数 917 浏览 0 评论 0原文

MergeSort 是一种分而治之的算法，它将输入分为几个部分并递归地求解这些部分。
...split 函数有多种方法。一种方法是从中间分开。这种方法有一些很好的特性，但是，我们将重点关注一种更快的方法：奇偶分割。这个想法是将每个偶数位置的元素放在一个列表中，将每个奇数位置的元素放在另一个列表中。

这直接来自我的讲义。究竟为什么偶数奇数分割比数组中间的分割要快？

我推测这与传递到 MergeSort 的列表以及已经排序的质量有关，但我不完全确定。

有人能解释一下吗？

编辑：我尝试在Python中运行以下命令...

global K
K = []
for i in range (1, 100000):
    K.append(i)


def testMergeSort():
"""
testMergeSort shows the proper functionality for the
Merge Sort Algorithm implemented above.
"""

t = Timer("mergeSort([K])", "from __main__ import *")
print(t.timeit(1000000))

p = Timer("mergeSort2([K])", "from __main__ import *")
print(p.timeit(1000000))

（MergeSort是奇偶合并排序，MergeSort2向下划分中心）

结果是：

<块引用> <块引用>
0.771506746608
0.843161219237

原文

MergeSort is a divide-and-conquer algorithm that divides the input into several parts and solves the parts recursively.
...There are several approaches for the split function. One way is to split down the middle. That approach has some nice properties, however, we'll focus on a method that's a little bit faster: even-odd split. The idea is to put every even-position element in one list, and every odd-position in another.

This is straight from my lecture notes. Why exactly is it the case that the even-odd split is faster than down the middle of the array?

I'm speculating it has something to do with the list being passed into MergeSort and having the quality of already already sorted, but I'm not entirely sure.

Could anyone shed some light on this?

Edit: I tried running the following in Python...

global K
K = []
for i in range (1, 100000):
    K.append(i)


def testMergeSort():
"""
testMergeSort shows the proper functionality for the
Merge Sort Algorithm implemented above.
"""

t = Timer("mergeSort([K])", "from __main__ import *")
print(t.timeit(1000000))

p = Timer("mergeSort2([K])", "from __main__ import *")
print(p.timeit(1000000))

(MergeSort is the even-odd MergeSort, MergeSort2 divides down the center)

And the result was:

0.771506746608
0.843161219237

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

捎一片雪花 2024-11-16 22:34:34

我可以看到，它可能会更好，因为将其与替代元素分开意味着您不必知道输入从多长时间开始 - 您只需取出元素并将它们放入交替列表中，直到用完为止。

此外，如果您小心地允许更好的并行处理，您可能会在完成第一个列表的迭代之前开始分割结果列表。

我应该补充一点，我不是这些问题的专家，它们只是想到的事情......

回复收藏 0 原文

迷离° 2024-11-16 22:34:34

输入列表越接近已排序，运行时就越短（这是因为如果所有内容都已排序，则合并过程不必移动任何值）以正确的顺序；它只执行 O(n) 次比较，因为 MergeSort 在拆分的每一半上递归地调用自身，因此需要选择一个 split< /code> 函数，增加了列表的结果一半按排序顺序的可能性如果列表大部分已排序，偶数-奇数分割将比中间分割做得更好。例如，

MergeSort([2, 1, 4, 3, 5, 7])

如果我们从中间拆分（请注意，两个子列表都有排序错误），则结果是

Merge(MergeSort([2, 1, 4]), MergeSort([3, 5, 7]))

，而如果我们进行奇数拆分，我们将得到

Merge(MergeSort([2, 4, 5]), MergeSort([1, 3, 7]))

两个已排序的列表（以及最佳情况性能）。但是，在不了解有关输入列表的任何信息的情况下，拆分函数的选择不应渐进地影响运行时。

The closer the input list is to already being sorted, the lower the runtime (this is because the merge procedure doesn't have to move any of the values if everything is already in the correct order; it just performs O(n) comparisons. Since MergeSort recursively calls itself on each half of the split, one wants to choose a split function that increases the likelihood that the resulting halves of the list are in sorted order. If the list is mostly sorted, even-odd split will do a better job of this than splitting down the middle. For example,

MergeSort([2, 1, 4, 3, 5, 7])

would result in

Merge(MergeSort([2, 1, 4]), MergeSort([3, 5, 7]))

if we split down the middle (note that both sub-lists have sorting errors), whereas if we did even-odd split we would get

Merge(MergeSort([2, 4, 5]), MergeSort([1, 3, 7]))

which results in two already-sorted lists (and best-case performance for the subsequent calls to MergeSort). Without knowing anything about the input lists, though, the choice of splitting function shouldn't affect runtime asymptotically.

回复收藏 0 原文