我使用Python多线程来实现快速排序。
快速排序是在函数中实现的。它是一个递归函数。
每个线程调用 Quicksort 对其拥有的数组进行排序。每个线程都有自己的数组,用于存储需要排序的数字。
如果数组大小较小 (
def partition (array, p, r):
x = array[r]
i = (p-1)
j = p
while (1):
if array[j] <= x:
i = (i+1)
temp = array[j]
array[j] = array[i]
array[i] = temp
j+=1
if j == r:
break
temp = array[i+1]
array[i+1] = array[r]
array[r] = temp
return i+1
def quicksort (array, p, r):
if p < r:
q = partition (array, p, r)
quicksort (array, p, q-1)
quicksort (array, q+1, r)
听起来你真正的问题是“为什么使用线程时递归深度更短”?我将尝试回答这个问题。
首先,背景。每个递归级别都存储在称为堆栈的内存区域中。不幸的是,系统必须提前分配堆栈空间,并且它事先并不知道您的程序可能需要多少堆栈空间。这就是为什么过多的递归会导致“最大递归深度”错误:您的程序已用完所有堆栈空间。
每个线程都需要自己的堆栈来存储当前正在该线程中执行的函数列表。在单线程程序中,系统可以为该线程的堆栈提供一大块内存。在多线程程序中,系统必须更加保守一点,它只为每个线程提供一个小的堆栈。否则,具有多个线程的程序可能会很快用完所有系统内存,仅包括堆栈空间(其中大部分不会被使用)。
所有这些都是由操作系统和/或 C 库完成的,Python(更准确地说,CPython)在 C 库上运行。 Python 尽力阻止您使用整个 C 堆栈,因为这会导致严重崩溃而不仅仅是异常。你可以告诉 Python 如何表现setrecursionlimit
功能,但这并没有改变actual可用的堆栈空间量。
在带有 bash shell 的 UNIX 系统上,您可以使用以下命令更改堆栈大小ulimit -s
命令。类型help ulimit
在 bash shell 提示符处获取更多信息。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)