gpt4 book ai didi

python - python 中的 Mergesort - 太慢了吗?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:56:27 24 4
gpt4 key购买 nike

<分区>

我正在尝试学习归并排序,但不确定我是否完全正确。它有效,我已经尝试优化它,例如为 leftpop 使用双端队列,但我仍然得到比内置 sorted() 函数慢大约 4 倍的时间。这应该发生吗?还是我遗漏了一些明显的瓶颈?

import random
from time import time
from collections import deque

unsorted = [random.randint(0, 1000) for r in xrange(101101)]


def merge_sort(unsorted_list):
length = len(unsorted_list)
if length <= 1:
return unsorted_list

left = unsorted_list[:length / 2]
right = unsorted_list[length / 2:]

left_sorted = deque(merge_sort(left))
right_sorted = deque(merge_sort(right))

new = []
while left_sorted and right_sorted:
if left_sorted[0] < right_sorted[0]:
new.append(left_sorted.popleft())
if not left_sorted:
new += right_sorted
else:
new.append(right_sorted.popleft())
if not right_sorted:
new += left_sorted
return new


s = time()
print merge_sort(unsorted)
e = time()
print e - s

s = time()
print sorted(unsorted)
e = time()
print e - s

编辑:下面稍微优化的版本:

def merge_sort(unsorted_list):
length = len(unsorted_list)
if length <= 1:
return unsorted_list

left = unsorted_list[:length / 2]
right = unsorted_list[length / 2:]

left_sorted = deque(merge_sort(left))
right_sorted = deque(merge_sort(right))

new = []

new_append = new.append
left_pop = left_sorted.popleft
right_pop = right_sorted.popleft

while left_sorted and right_sorted:
if left_sorted[0] < right_sorted[0]:
new_append(left_pop())
else:
new_append(right_pop())

if not left_sorted:
new += right_sorted
if not right_sorted:
new += left_sorted

return new

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com