поиск бегущей среды из потока

Проблема: учитывая, что целые числа читаются из потока данных. Эффективно найдите медиану прочитанных до сих пор элементов.

Я нашел решение здесь

У меня вопрос: почему нам нужно использовать кучи, а не просто добавлять числа в вектор?

Например, предполагая, что мы используем вектор для хранения входящих данных, мы вызываем метод для вычисления медианы следующим образом:

if vector size is even
   return (element at size/2 + element at size/2-1);
else
   return (element at size/2);

Подойдет ли вышеуказанное решение?


median algorithm
person firefly    schedule 20.10.2015    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Ваше решение не может работать, если элементы в вашем векторе не в порядке. И если вы добавите элементы в конец вектора, они будут не в порядке.

С другой стороны, элементы в порядке в куче.

Кроме того, в первом операторе возврата отсутствует деление на два.

person ChronoTrigger    schedule 20.10.2015
comment
Спасибо за разъяснение! Не уверен, что это правильно, но, насколько я понимаю, при условии, что у вас есть n целых чисел, поступающих из потока данных; поскольку для вставки элемента в кучу требуется o (lg (n)), поэтому общая временная сложность будет o (nlg (n)). С другой стороны, мы можем сначала вставить данные в вектор, который занимает линейное время, а затем вызвать алгоритм сортировки, который также является o (nlg (n)). Поэтому я не вижу преимущества использования сложной структуры данных для решения этой проблемы. - person firefly; 20.10.2015
comment
Разница в том, что если вы сортируете вектор каждый раз, когда хотите вычислить медиану, вы выполняете дополнительную работу, потому что не пользуетесь преимуществами уже отсортированных элементов. Рассмотрим этот случай: получить n элементов из потока, вычислить медиану, получить еще один элемент, снова вычислить медиану. С кучей у вас есть O (nlogn) + O (logn) + O (logn) + O (logn). С вектором у вас есть O (n) + O (nlogn) + O (1) + O (nlogn). Итак, помимо проблем с памятью, это зависит от того, как часто вы хотите вычислять медианное значение. - person ChronoTrigger; 20.10.2015

arrow_upward
1
arrow_downward

Есть как минимум две причины, по которым предлагаемое вами решение обычно не используется:

  1. Обычно предполагается, что если вы обрабатываете поток данных, этот поток огромен или даже бесконечен, поэтому хранить все значения нецелесообразно.
  2. Как говорит @ChronoTrigger, вам нужно будет отсортировать свой вектор, чтобы использовать его. Проблема обычно предполагает, что вы хотите иметь возможность запрашивать медиану снова и снова в качестве нового потока данных. Чтобы сделать это с вашим решением, вам придется снова и снова сортировать свой вектор, что будет медленным.

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

person Oliver Dain    schedule 20.10.2015
comment
Спасибо, Оливер! Я понимаю вашу точку зрения на постоянную сортировку вектора, однако, для подхода кучи, разве нам все еще не нужно хранить весь поток данных? - person firefly; 20.10.2015
comment
Да, для подхода кучи вам все равно нужно хранить весь поток. Обратите внимание, что первый ответ на сообщение SO, которое вы связали, говорит о проблемах с памятью при таком подходе. - person Oliver Dain; 20.10.2015

arrow_upward
0
arrow_downward

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

Например: поток: 8 3 4 1 10 12

Медиана на каждом шаге, если вы просто добавляете элемент в конец вектора:

step 1: vector: 8 median: 8
step 2: vector: 8, 3 median: (8+3)/2
step 3: vector: 8, 3, 4 median: 3 (when actually it should be 4)

Надеюсь, вы уловили идею

person pgiitu    schedule 20.10.2015