Heapq로 MinHeap을 구현할 때 지속 상태

Question

get_median()의 연속 호출을 통해 중간 값을 유지하기 위해 StreamingMedian 개체를 구현하려고합니다. 이를 위해 heapq 모듈을 통해 MinHeap 및 MaxHeap 클래스를 구현했습니다.

나는 매우 이상한 버그를 겪었습니다.

print("Before streaming medians", MinHeap(), sep="\t") # is empty 

b = StreamingMedian() 
b.add_val(5) 
b.add_val(100) 

assert b.get_median() == 52.5 

print("After streaming medians, for MaxHeap", MaxHeap(), sep='\t') # is empty 
print("After streaming medians, for MinHeap", MinHeap(), sep='\t') # should be empty 
print("After streaming medians, for MinHeap with input", 
     MinHeap([]), sep="\t") # is empty 

내가 얻을 다음과 같은 출력 : 클래스 구현은 아래에서 확인할 수 있습니다

Before streaming medians  [] 
After streaming medians, for MaxHeap [] 
After streaming medians, for MinHeap [100] 
After streaming medians, for MinHeap with input [] 

어떤 이유로 나는 다음과 같은 명령을 실행할 때. Python 3.5.2 :: Anaconda custom (64-bit)에서 실행하고 있습니다.

import heapq 

class MinHeap(object): 

    def __init__(self, l=[]): 
     self.heap = l 
     heapq.heapify(l) 

    def peek(self): 
     return self.heap[0] 

    def pop(self): 
     return heapq.heappop(self.heap) 

    def push(self, x): 
     heapq.heappush(self.heap, x) 

    def pushpop(self, x): 
     return heapq.heappushpop(self.heap, x) 

    def replace(self, x): 
     return heapq.heapreplace(self.heap, x) 

    def __len__(self): 
     return len(self.heap) 

    def __str__(self): 
     return str(self.heap) 

class MaxHeap(MinHeap): 

    def _invert_sign(self, l): 
     return [-1 * a for a in l] 

    def __init__(self, l=[]): 
     super().__init__(self._invert_sign(l)) 

    def push(self, x): 
     super().push(-1 * x) 

    def pushpop(self, x): 
     return super().pushpop(-1 * x) 
    def replace(self, x): 
     return super().replace(-1 * x) 

    def pop(self): 
     return -1 * super().pop() 

    def peek(self): 
     return -1 * super().peek() 

    def __str__(self): 
     return str(self._invert_sign(self.heap)) 


class StreamingMedian(): 

    def __init__(self): 
     self.min_heap = MinHeap() 
     self.max_heap = MaxHeap() 

    def get_median(self): 
     min_heap_has_x_more = len(self.min_heap) - len(self.max_heap) 
     if min_heap_has_x_more > 0: 
      return self.min_heap.peek() 
     elif min_heap_has_x_more < 0: 
      return self.max_heap.peek() 
     else: 
      return (self.min_heap.peek() + self.max_heap.peek())/2 

    def add_val(self, x): 
     if len(self.min_heap) + len(self.max_heap) == 0: 
      self.max_heap.push(x) 
     else: 
      med = self.get_median() 
      if x > med: 
       self.min_heap.push(x) 
       self._ensure_balance() 
      elif x < med: 
       self.max_heap.push(x) 
       self._ensure_balance() 
      else: 
       self.max_heap.push(x) 
       self._ensure_balance() 

    def _ensure_balance(self): 
     size_diff = len(self.min_heap) - len(self.max_heap) 
     if abs(size_diff) > 1: 
      if size_diff > 0: # min_heap has 2 more elements 
       self.max_heap.push(self.min_heap.pop()) 
      else: # max_heap has 2 more elements 
       self.min_heap.push(self.max_heap.pop()) 
      assert abs(len(self.min_heap) - len(self.max_heap)) < 2 

print("Before streaming medians", MinHeap(), sep="\t") 

b = StreamingMedian() 
b.add_val(5) 
b.add_val(100) 

assert b.get_median() == 52.5 

print("After streaming medians, for MaxHeap", MaxHeap(), sep='\t') # is empty 
print("After streaming medians, for MinHeap", MinHeap(), sep='\t') # should be empty 
print("After streaming medians, for MinHeap with input", MinHeap([]), sep="\t") # is empty 

Answer 1

문제 때문에 기본 인수가 파이썬에서 계산하는 방법으로 발생 된 문제

. 함수가 처음 호출 될 때 계산되고 원래 계산 된 값과 함께 함수가 사용됩니다. 기본값이 변경 가능하면 (목록이있는 경우) 문제가 발생합니다. MinHeap을 위해 무슨 일이 일어 났는지 그래서

했다 :

1. 처음 만들 MinHeap과 l 매개 변수의 기본 인수는 메모리 주소에 할당되었다.
2. StreamingMedian 의 self.heap은 l과 동일합니다.
3. MinHeap을 다시 호출하면 l에 이미 메모리 주소가 있으며이 메모리 주소가 다시 사용되어 self.heap으로 바인드됩니다.

이 MaxHeap 때문에 대한 발생하지 않습니다

1. 처음 만들 MaxHeap과 l 매개 변수의 기본 인수는 메모리 주소에 할당되었다.
2. _invert_sign은 self.heap에 할당 된 새 목록을 만듭니다. 기본 인수 l은 절대로 수정되지 않습니다.
3. MaxHeap을 다시 초기화하면 l에 이미 메모리 주소가 있고 다시 사용되지만 결코 수정되지 않으며 다른 복사본이 구성되지 않으므로 수정되지 않습니다.

솔루션

대신 :

class MinHeap(object): 

def __init__(self, l=[]): 
    self.heap = l 
    heapq.heapify(l) 

우리는 사용한다 : 비슷한 변화가 MaxHeap

을 위해 만들어 져야한다

class MinHeap(object): 

def __init__(self, l=None): 
    if l is None: 
     l = [] 
    self.heap = l 
    heapq.heapify(l)