Вопрос по heap, algorithm – Найти бегущую медиану из потока целых чисел [дубликат]

206

Possible Duplicate:
Rolling median algorithm in C

Given that integers are read from a data stream. Find median of elements read so far in efficient way.

Решение, которое я прочитал: мы можем использовать максимальную кучу на левой стороне для представления элементов, которые меньше эффективной медианы, и минимальную кучу на правой стороне для представления элементов, которые превышают эффективную медиану.

После обработки входящего элемента количество элементов в кучах отличается не более чем на 1 элемент. Когда обе кучи содержат одинаковое количество элементов, мы находим среднее значение корневых данных кучи как эффективную медиану. Когда кучи не сбалансированы, мы выбираем эффективную медиану из корня кучи, содержащей больше элементов.

Но как мы можем построить максимальную кучу и минимальную кучу, то есть как узнать эффективную медиану здесь? Я думаю, что мы вставили бы 1 элемент в max-heap, а затем следующий 1 элемент в min-heap и так далее для всех элементов. Поправь меня, если я здесь не прав.

Решение визиря выглядит хорошо для меня, за исключением того, что я предполагал (хотя вы не утверждали), что этот поток может быть произвольно длинным, поэтому вы не можете хранить все в памяти. Это тот случай? Running Wild
@RunningWild Для произвольно длинных потоков вы можете получить медиану последних N элементов, используя кучи Фибоначчи (таким образом, вы получаете удаления log (N)) и сохраняя указатели на вставленные элементы по порядку (например, в deque), затем удаляя самые старые элемент на каждом шаге, как только кучи заполнены (возможно, также перемещая вещи из одной кучи в другую). Вы можете получить несколько лучше, чем N, сохранив количество повторяющихся элементов (если имеется много повторов), но в целом, я думаю, вам нужно сделать какие-то предположения о распределении, если вы хотите получить медиану всего потока. Dougal
Вы можете начать с обеих куч пустыми. Первый int идет в одну кучу; второй идет либо в другой, либо вы перемещаете первый элемент в другую кучу, а затем вставляете. Это обобщает то, что «не позволять одной куче становиться больше, чем другая + 1»; и никакой специальный регистр не требуется («корневое значение» пустой кучи может быть определено как 0) Jon Watte
Умный алгоритм, использующий кучи. Из названия я не мог сразу придумать решение. Mooing Duck
Я только что получил этот вопрос на интервью MSFT. Спасибо за публикацию R Claven

Ваш Ответ

8   ответов
40

Если дисперсия входных данных статистически распределена (например, нормальная, логарифмическая нормальная ... и т. Д.), То выборка из резервуара является разумным способом оценки процентилей / медиан из произвольно длинного потока чисел.

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;
      }
  }
}

& Quot; резервуар & Quot; затем выполняется беговая, равномерная (справедливая) выборка всех входных данных - независимо от размера. Поиск медианы (или любого процентиля) - это прямая задача сортировки резервуара и опроса интересующей точки.

Поскольку резервуар имеет фиксированный размер, сортировка может считаться эффективной O (1) - и этот метод работает с постоянным временем и потреблением памяти.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
-1

Не можете ли вы сделать это только с одной кучей?Update: нет. Смотрите комментарий.

Инвариант: после прочтения2*n входы, мин-куча содержитn самый большой из них.

Цикл: чтение 2 входов. Добавьте их обоих в кучу и удалите кучу мин. Это восстанавливает инвариант.

Так когда2n считаны входные данные, минимальная куча является n-й по величине. Для усреднения двух элементов вокруг медианной позиции и обработки запросов после нечетного числа входных данных потребуется небольшое дополнительное усложнение.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
25

Самый эффективный способ вычислить процентиль потока, который я нашел, - это P & # xB2; алгоритм:Радж Джайн, Имрич Хламтак: P & # xB2; Алгоритм динамического расчета квантилей и гистограмм без сохранения наблюдений. Commun. ACM 28 (10): 1076-1085 (1985)

Алгоритм прост в реализации и работает очень хорошо. Это оценка, однако, имейте это в виду. Из аннотации:

A heuristic algorithm is proposed for dynamic calculation qf the median and other quantiles. The estimates are produced dynamically as the observations are generated. The observations are not stored; therefore, the algorithm has a very small and fixed storage requirement regardless of the number of observations. This makes it ideal for implementing in a quantile chip that can be used in industrial controllers and recorders. The algorithm is further extended to histogram plotting. The accuracy of the algorithm is analyzed.

Error: User Rate Limit Exceededresearch.neustar.biz/2013/09/16/…Error: User Rate Limit Exceededarxiv.org/pdf/1407.1121v1.pdfError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Count-Min SketchError: User Rate Limit Exceeded
15

Интуитивно понятный способ думать об этом заключается в том, что если бы у вас было полностью сбалансированное бинарное дерево поиска, тогда корнем был бы медианный элемент, поскольку там было бы одинаковое количество меньших и больших элементов. Теперь, если дерево не заполнено, этого не произойдет, поскольку на последнем уровне будут отсутствовать элементы.

Поэтому вместо этого мы можем получить медиану и два сбалансированных бинарных дерева, одно для элементов, меньших, чем медиана, и одно для элементов, превышающих медиану. Два дерева должны быть одинакового размера.

Когда мы получаем новое целое число из потока данных, мы сравниваем его с медианой. Если оно больше, чем медиана, мы добавляем его к правильному дереву. Если два размера дерева отличаются более чем на 1, мы удаляем элемент min правого дерева, делаем его новой медианой и помещаем старую медиану в левое дерево. Аналогично для меньших.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
6

Эффективное - это слово, которое зависит от контекста. Решение этой проблемы зависит от количества выполненных запросов относительно количества вставок. Предположим, вы вводите N чисел и K раз к концу, который вас интересовал медианой. Сложность алгоритма на основе кучи была бы O (N log N + K).

Рассмотрим следующую альтернативу. Вставьте числа в массив, и для каждого запроса запустите алгоритм линейного выбора (скажем, с помощью стержня быстрой сортировки). Теперь у вас есть алгоритм с временем выполнения O (K N).

Теперь, если K достаточно мало (редкие запросы), последний алгоритм на самом деле более эффективен, и наоборот.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
46

Если вы не можете одновременно хранить все элементы в памяти, эта проблема становится намного сложнее. Решение для кучи требует, чтобы вы держали все элементы в памяти одновременно. Это невозможно в большинстве реальных применений этой проблемы.

Вместо этого, когда вы видите цифры, следите заcount от количества раз вы видите каждое целое число. Предполагая 4-байтовые целые, то есть 2 ^ 32 сегмента, или не более 2 ^ 33 целых чисел (ключ и число для каждого целого), что составляет 2 ^ 35 байтов или 32 ГБ. Вероятно, это будет намного меньше, чем это, потому что вам не нужно хранить ключ или счет для тех записей, которые равны 0 (то есть, как defaultdict в python). Требуется постоянное время для вставки каждого нового целого числа.

Затем в любой момент, чтобы найти медиану, просто используйте количество, чтобы определить, какое целое число является средним элементом. Это занимает постоянное время (хотя и большое постоянное, но, тем не менее, постоянное).

Error: User Rate Limit ExceededmoreError: User Rate Limit ExceededmassiveError: User Rate Limit Exceeded
Error: User Rate Limit Exceededmathworld.wolfram.com/BirthdayProblem.htmlError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
24

Эта проблема имеет точное решение, которое требует толькоn последние просмотренные элементы должны быть сохранены в памяти. Это быстро и хорошо масштабируется.

индексируемый скиплист поддерживает O (ln n) вставку, удаление и индексированный поиск произвольных элементов при сохранении отсортированного порядка. Когда в сочетании сОчередь FIFO который отслеживает n-ую самую старую запись, решение простое:

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]

Вот ссылки на полный рабочий код (простая для понимания версия класса и оптимизированная версия генератора с индексируемым кодом пропускаемого списка):

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededsubsetError: User Rate Limit Exceeded
358

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

Вопрос о деталях конкретного решения (макс. Кучи / мин. Кучи) и о том, как работает решение на основе кучи, объясняется ниже:

Для первых двух элементов добавьте меньший к 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

Теперь я расскажу о проблеме в целом, как и было обещано в начале ответа. Найти медиану из потока данных - сложная задача, и найтиexact solution с ограничениями памяти эффективно, вероятно, невозможно в общем случае. С другой стороны, если данные имеют некоторые характеристики, которые мы можем использовать, мы можем разработать эффективные специализированные решения. Например, если мы знаем, что данные являются целочисленным типом, то мы можем использоватьсортировка, который может дать вам постоянную память постоянного алгоритма времени. Решение на основе кучи является более общим решением, поскольку оно может использоваться и для других типов данных (удваивается). И, наконец, если точная медиана не требуется и достаточно приближения, вы можете просто попытаться оценить функцию плотности вероятности для данных и оценить медиану, используя ее.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededgithub.com/PythonAlgo/DataStruct
Error: User Rate Limit Exceededhere.
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы