[algorithm] 정수 스트림에서 연속 중앙값 찾기

스트리밍 된 데이터에서 실행되는 중앙값을 찾는 데에는 여러 가지 솔루션이 있습니다. 답변의 마지막 부분에 대해 간단히 이야기하겠습니다.

문제는 특정 솔루션 (최대 힙 / 최소 힙 솔루션)의 세부 사항에 관한 것이며 힙 기반 솔루션의 작동 방식은 다음과 같습니다.

처음 두 요소의 경우 왼쪽의 maxHeap에 작은 것을 추가하고 오른쪽의 minHeap에 더 큰 것을 추가하십시오. 그런 다음 스트림 데이터를 하나씩 처리하고

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

그런 다음 언제든지 다음과 같은 중앙값을 계산할 수 있습니다.

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

이제 답변의 시작 부분에서 약속 한 일반적인 문제에 대해 이야기하겠습니다. 데이터 스트림에서 중간 값을 찾는 것은 어려운 문제이며 , 일반적으로 메모리 제약이 있는 정확한 솔루션 을 찾는 것은 불가능할 것입니다. 반면에 데이터에 활용 가능한 특성이있는 경우 효율적인 특수 솔루션을 개발할 수 있습니다. 예를 들어, 데이터가 정수 유형이라는 것을 알고 있다면 계산 정렬을 사용할 수 있습니다일정한 메모리 상수 시간 알고리즘을 제공 할 수 있습니다. 힙 기반 솔루션은 다른 데이터 유형 (더블)에도 사용할 수 있으므로보다 일반적인 솔루션입니다. 마지막으로 정확한 중앙값이 필요하지 않고 근사값이 충분하면 데이터의 확률 밀도 함수를 추정하고이를 사용하여 중앙값을 추정하면됩니다.

답변

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }
  else
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]