好吧,这让我抓狂了。我创建了一个简单的Quicksort实现(从CLR),并随机选择透视:
def qsr(l, s, e):
def qsrpartition(l, s, e):
pivotindex=random.randrange(s,e+1)
l[e], l[pivotindex] = l[pivotindex], l[e]
p = l[e]
i = s - 1
for j in range(s, e):
if l[j] <= p:
i = i+1
l[i], l[j] = l[j], l[i]
l[i+1], l[e] = l[e], l[i+1]
return i+1
if s < e:
q = qsrpartition(l, s, e)
qsr(l, s, q-1)
qsr(l, q+1, e)
我还有一个静态选择pivot的版本(注解掉qsrpartition的前两行),如果我在一个随机数组上运行这两个版本,上面的随机版本比总是选择最后一个元素作为pivot的版本快100倍(1s对10s)。
li = random.choices(range(5000), k=5000)
li2 = random.choices(range(5000), k=5000)
r1 = timeit.timeit(lambda:qs(li, 0, len(li)-1),number=10)
r2 = timeit.timeit(lambda:qsr(li2, 0, len(li2)-1),number=10)
print(r1, r2)
11.10 0.08
上面的结果在运行、数组长度、有或没有替换的样本使用、运行函数的顺序等方面都具有概率性。对于一个随机选择的数组,枢轴的选择应该不重要,因为最后一个元素应该和任何中间元素一样好。我觉得有一个明显的解释,我在这里遗漏了。
2条答案
按热度按时间tjrkku2a1#
您的基准测试代码没有度量您想要的内容。
如前所述,列表
li
和li2
在10次运行中的第一次中排序,而其他9次运行是对已经排序的列表排序。当分区已经排序时,选择最后一个条目作为主元代表最坏的情况,这使得随机主元变体在10次运行中的9次中具有优势。我也会做更多的运行,以获得更好的估计。
以下是更正:
这样的输出稍微偏向于非随机透视版本,原因很简单,它不需要执行这两个额外的语句,在www.example.com上repl.it我得到了这样的输出:
dwthyt8l2#
除了静态与随机选取之外,您还可以测量绘制随机数和交换与不交换。
要衡量随机与非随机透视,不要只注解掉前两行:
无条件地抽取该随机数,使用静态交换(
l[0], l[-1] = l[-1], l[0]
)与随机交换。但是吉恩指出了主要的错误:快速排序有序数组。
目前,您正在测量最坏情况与“平均”/“随机”。