Подсчет сравнений quicksort без глобального Python

Question

У меня есть код быстрых и сравнительных сравнений, который отлично работает. Но каждый раз, когда я вызываю функцию, счетчик продолжает складываться снова и снова. Есть ли способ избежать этого?

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) 

Answer 1

Для того, чтобы заставить его работать с глобальным 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 означает в этом случае и как получить тот же результат (который это хорошее упражнение!).