计数比较quicksort没有全局Python
我有一个快速排序和计数比较的代码,完美的工作。但每次我调用这个函数时,计数都会一次又一次地加起来。有什么办法可以避免这种情况?计数比较quicksort没有全局Python
count = 0
def quicksort(A, left = None, right =None):
global count
if left is None:
left = 0
if right is None:
right = len(A)
if left >= right:
return
p =A[left]
i = left +1
for j in range(left+1,right):
if A[j] < p:
A[i] , A[j] = A[j], A[i]
i = i + 1
A[left] , A[i-1] = A[i-1], A[left]
quicksort(A,left,i-1)
count += i-1-left
quicksort(A,i,right)
count += right-i-1
return A,count+len(A)
为了使其与全球count
工作,你需要把它递归的第一级复位。要做到这一点的方法之一是你实现移动到一个单独的函数_quicksort
自称递归,以及调用之前重置计数器:
def quicksort(A):
global count
count = 0
return _quicksort(A)
def _quicksort(A, left=None, right=None):
global count
...
_quicksort(A,left,i-1)
...
此外,这简化了您的主函数签名为quicksort
最终用户不真的需要知道left
和right
。现在
,最好不要使用全局变量,就好象它是一个不好的做法。然后,您需要以某种方式将上下文传递给_quicksort
函数,以便知道要处理哪个计数器。所以,你就需要通过一些作为一个参数:
def _quicksort(context, A, left=None, right=None):
...
_quicksort(context, ...)
例如,这context
也能像{'count': 0}
一本字典,然后可以为context['count']
访问,也可以是一个对象使用context.count
。请注意,在这种情况下,这是变得非常接近的类,其中的背景是对象本身和_quicksort
将是一个类方法:
class _Quicksort(object):
count = 0
def _quicksort(self, A, left=None, right=None):
...
self._quicksort(A, ...)
self.count += ...
最后,对付上下文中递归函数的另一种常用的方法是传递和返回变量“按值”,如:
def _quicksort(count, other_context, A, left=None, right=None):
...
count1, other_context1 = _quicksort(count, other_context, A, left, right)
...
return count + count1, other_context
但你最终会得到一个混乱的方法签名,就必须搞清楚什么count
意味着在这种情况下,如何得到相同的结果(这是一个很好的锻炼!)。
感谢您对不同实施方式的详细说明。我了解重置柜台。我最近开始编写代码,所以我对班级了解不多,但在此之后,我对学习非常感兴趣。 – 2014-11-05 17:06:03
@ user3332615,我很乐意帮忙!您应该尽可能避免使用全局状态,并且类会通过创建可以使用的本地上下文来替代全局变量来帮助您。如果你很好奇,这个python类的入门看起来是一个很好的开始:http://www.jesshamrick.com/2011/05/18/an-introduction-to-classes-and-inheritance-in-python/ – 2014-11-05 18:56:31
Sure ,我正在阅读它。再一次非常感谢你。 – 2014-11-05 19:52:47
这正是你要求它做的;你永远不会重置'count = 0'。 – jonrsharpe 2014-11-05 09:10:38
特别是,如果您希望此快速排序实现计算比较次数,请考虑将其计算为返回值 – 2014-11-05 09:22:42
@jonrsharpe如果我删除了count = 0,则得到的错误全局名称计数未定义。 – 2014-11-05 09:37:01