самостоятельная ссылка в python внутри методов

Question

Вот куча, который имеет дополнительную функциональность; "Балансировка нагрузки" на основе по модулю 2:

#! /usr/bin/env python 
class Lifo: 
    def __init__(self): 
    # repr using tuple 
    self.lifo =() 
    def push(self, data): 
    # pack data using tuple 
    self.lifo = (data, self.lifo) 
    def pop(self): 
    # unpack data using tuple 
    # raise ValueError when empty 
    data, self.lifo = self.lifo 
    return data 
    def __len__(self): 
    return len(self.lifo) 
    def __repr__(self): 
    return str(self.lifo) 


class HeapNode: 
    def __init__(self, value, left=None, right=None): 
    self.data = value 
    self.left = left 
    self.right = right 

    def __repr__(self): 
    if self.left is None and self.right is None: 
     return '(%s)'%(self.data) 
    repr_left = '*' if self.left is None else repr(self.left) 
    repr_right = '*' if self.right is None else repr(self.right) 
    return '(%s L%s R%s)'%(self.data, repr_left, repr_right) 

    def add(self,data,count): 
    # do traversal with stack 
    lifo = Lifo() 
    lifo.push(self) 
    print 'push\'d self is %s, lifo is %s'%(self,lifo) 
    while len(lifo) > 0 : 
     # self's modified here 
     self = lifo.pop() 
     print 'popp\'d self is %s, lifo is %s'%(self,lifo) 
     if count % 2 == 0 : 
      if self.right is None: 
       self.right = HeapNode(data) 
      else: 
       lifo.push(self.right) 
     else: 
      if self.left is None: 
       self.left = HeapNode(data) 
      else: 
       lifo.push(self.left) 
    print 'returning self is %s'%(self,) 
    return self 

if __name__ == '__main__': 
    heap = HeapNode(11) 
    heap.add(7,0).add(4,1).add(10,2) 

выход:

push'd self is (11), lifo is ((11),()) 
popp'd self is (11), lifo is() 
returning self is (11 L* R(7)) 
heap [(11 L* R(7))] 
push'd self is (11 L* R(7)), lifo is ((11 L* R(7)),()) 
popp'd self is (11 L* R(7)), lifo is() 
returning self is (11 L(4) R(7)) 
heap [(11 L(4) R(7))] 
push'd self is (11 L(4) R(7)), lifo is ((11 L(4) R(7)),()) 
popp'd self is (11 L(4) R(7)), lifo is() 
popp'd self is (7), lifo is() 
returning self is (7 L* R(10)) 
heap [(11 L(4) R(7 L* R(10)))] 

Как выше произойдет, то есть self (в дополнение функция) является (7 L* R(10) но куча отсчитывается (11 L(4) R(7 L* R(10)))?

Я понимаю, что в главном, если бы: heap = heap.add_stack(10,2), тогда возвращаемое значение - куча.

Но то, что я не могу понять, что добавляет элементы 11 L(4) в (7 L* R(10)), это некоторые ссылки и значение мимоходом, что причиной этого?

Может кто-нибудь объяснить это ясно?

Answer 1

Ваш метод add кажется, что эквивалентно этой рекурсивной версии:

def add(self, data, count): 
    if count % 2: 
     if self.right is None: 
      self.right = HeapNode(data) 
      return self # note, returning the node before the new leaf 
     else: 
      return self.right.add(data, count) # recurse 
    else: 
     if self.left is None: 
      self.left = HeapNode(data) 
      return self 
     else: 
      return self.left.add(data, count) # recurse 

Так что является «хвостовой рекурсией», он может быть легко преобразован в ierative версию, которая выглядит очень похоже на то, что уже иметь. Замечу, однако, что ни один стек не требуется, так как есть только один current значения в любой момент времени (вы никогда не называя push дважды без pop между ними):

def add(self, data, count): 
    current = self # lets use a different variable name rather than rewriting self 
    while True: # loop until broken by a return 
     if count % 2: 
      if current.right is None: 
       current.right = HeapNode(data) 
       return current 
      else: 
       current = current.right 
     else: 
      if current.left is None: 
       current.left = HeapNode(data) 
       return current 
      else: 
       current = current.left 

Я избегал ловушки вашего кода из подмены в self имя переменной, которое может быть очень запутанным. Гораздо лучше сохранить self как объект, на который был вызван метод, и использовать другое имя для объекта, который мы сейчас обрабатываем.

Я подозреваю, что в этой реализации есть скрытая ошибка, и что вы хотите изменить count на каждом рекурсивном шаге (возможно, разделяя на два?), Но без лучшего понимания того, что должен делать ваш код I точно не знаю.

Вещь, о которой я думаю, вы запутались в том, как возвращаемые значения взаимодействуют с цепочками вызовов. Возвращаемое значение всегда будет последним нелистовым узлом, который был достигнут. Поэтому, если вы вызываете node.add(a, b), а затем отдельный звонок node.add(c, d), вы можете получить другой результат, чем если бы вы вызвали node.add(a, b).add(c, d) за один раз. Причина в том, что в первом случае переменная node не изменилась бы, тогда как объект, который вызывается add, может быть разным между двумя вызовами в цепочной версии. Вторая версия эквивалентна следующему:

temp = node.add(a, b) 
temp.add(c, d) 
del temp 

Если вы хотите, чтобы результаты сцепленных вызовов быть таким же, как повторные вызовы функции на корневой узел, то вам нужно изменить код, чтобы всегда возвращать корневой элемент , а не результат рекурсивного или итеративного обхода. В рекурсивной версии кода просто верните self, а не возвращайте результаты рекурсивного вызова. В итеративной версии верните self, а не current.

Или вы можете покончить с цепью и не возвращать ничего (что в Python эквивалентно возврату None).Это может быть самым «питоновым» решением (подобные методы вроде list.append и set.add ничего не возвращают).

Редактировать: Вот объяснение вывода.

Вы начинаете с одного узла (11). Первым шагом является то, что вы вызываете на нем add с аргументами 7 и 0. Этот призыв отвечает за первые три строки вывода:

push'd self is (11), lifo is ((11),()) 
popp'd self is (11), lifo is() 
returning self is (11 L* R(7)) 

Корневой узел толкает себя на свой стек, а затем получает выскочил обратно снова. Создается новый узел (7) и добавляется как правый ребенок (11), превращая его в (11 L* R(7)).

Я не уверен, где следующая строка вашего выхода приходит от:

heap [(11 L* R(7))] 

Это не печатается ни кода вы показали, так что я буду игнорировать его (и аналогичные строки позже).

Первый звонок add возвратил вызываемый, а затем вы вызываете следующий add на нем. Это все тот же узел, поэтому цепочка не делает ничего сложного. add вызова имеет аргументы 4 и 1 и производит еще три строки вывода:

push'd self is (11 L* R(7)), lifo is ((11 L* R(7)),()) 
popp'd self is (11 L* R(7)), lifo is() 
returning self is (11 L(4) R(7)) 

На этот раз он добавляет новый узел (4) в качестве левого потомка корневого узла. В противном случае это то же самое, что и выше. Третий add снова вызывается на том же узле, но на этот раз он немного работает. Я объясню, что происходит в это время за строкой.

push'd self is (11 L(4) R(7)), lifo is ((11 L(4) R(7)),()) 
popp'd self is (11 L(4) R(7)), lifo is() 

Эти первые две строки такие же, как то, что мы видим до сих пор, как корневой узел выталкивается затем выталкивается из стека. Однако на этот раз код видит, что на узле self уже есть правильный ребенок, поэтому он снова выталкивает этот дочерний элемент и петли. Обратите внимание, что этот второй push не имеет никакого связанного с ним оператора print, поэтому может показаться, что у вас нет одинакового количества нажатий и всплывающих окон. Но если вы работаете по логике, на каждом проходе через цикл всегда есть по одному.

popp'd self is (7), lifo is() 
returning self is (7 L* R(10)) 

После очередного узла выталкивается, self теперь (7) узел, а не корневого узла он был на любой другой перспективе. Новый нулевой узел (10) добавляется как его правый дочерний элемент, и узел (теперь возвращается (7 L* R(10)).На данный момент ваша цепочка, скорее всего, начнет действовать странно. Если бы вы связались с другим добавлением, это было бы применено к возвращенному узлу, а не к . к корню, как и раньше Так что, если вы начали с (0) узла в переменной heap, heap.add(1,0).add(2,1).add(3,2).add(4,3) будет вести себя странно: heap бы стать (0 L(2) R(1 L(4) R(3))), а не (0 L(2 L(4) R*) R(1 L* R(3))) что то, что вы получите, если вы не сделали цепи звонки

.