Может быть, я не ищу / ищу правильные ключевые слова (не могу найти решение).
Я пытаюсь вычислить медиану для списка чисел (который постоянно обновляется) эффективным способом.
Для вычисления среднего значения есть хороший метод, запоминающий количество элементов в списке и взвешивающий старое среднее. Например (псевдокод):
// Initialize values
noList = [8,10,4,6]
mean = 0
noItems = 0
// Now we want to update the mean continually with further values.
for (value : noList) {
mean = (noItems / (noItems + 1)) * mean + (1 / (noItems + 1)) * value
noItems = noItems + 1
}
// After iteration 1: wholeList = [8] ; mean = 8 ; noItems = 1
// After iteration 2: wholeList = [8,10] ; mean = 9 ; noItems = 2
// After iteration 3: wholeList = [8,10,4] ; mean = 7.33; noItems = 3
// After iteration 4: wholeList = [8,10,4,6]; mean = 7 ; noItems = 4
Вопрос:
Существует ли подобный (экономичный по площади) метод для вычисления медианы?
ОБНОВЛЕНО
Я обновил вопрос (спасибо @WillemVanOnsem). Я не только постоянно обновляю медиану, но и экономлю пространство.
Согласно его подсказке, мы можем сохранить две структуры данных.
Example:
// 1) We have a list for which we want to find the median.
noList = [9,10,4,6,13,12]
// 2) We devide it into two list or datastructures (additionally we sort it).
smallerList = [4,6,9]
biggerList = [10,12,13]
// 3) Both list have the same length, so the median is between the last element of smallerList und the first element of biggerList.
median = (9 + 10) / 2 = 9.5
// 4) Next, we add a further element and want to update our median.
// We add the number 5 to our datastructures. So the new list is:
noList = [9,10,4,6,13,12,5]
// 5) Obviously 5 is smaller than our current median of 9.5. So we insert it in a sorted way into smallerList:
smallerList = [4,5,6,9]
biggerList = [10,12,13]
// 6) Now length(smallerList) > length(biggerList), So, we know, that the updated median should be the last element of smallerList.
median = 9
// 7) Next, we add a further element and want to update our median.
// We add the number 2 to our datastructures. So the new list is:
noList = [9,10,4,6,13,12,5,2]
// 8) Obviously 2 is smaller than our current median of 9. So we insert it again in a sorted way into smallerList:
smallerList = [2,4,5,6,9]
biggerList = [10,12,13]
// 9) Now the length of smallerList is much bigger than the length of biggerList and we need to "balance" our list by taking one element from one list and inserting it into the other list.
// We remove the element 9 from smallerList and insert it into biggerList.
smallerList = [2,4,5,6]
biggerList = [9,10,12,13]
// 10) Both list have the same length, so the median is between the last element of smallerList und the first element of biggerList.
median = (6 + 9) / 2 = 7.5
Надеюсь, это проясняет. Я думаю, это был твой намек (@WillemVanOnsem).
Да, это может ответить на мой первоначальный вопрос ... но проблема с этим решением состоит в том, что оба списка (smallList и largeList) могут вырасти до значительного размера. Допустим, у нас есть поток из 10 ^ 18 чисел, и мы хотим найти медиану для всех чисел, не выходя из памяти. Как решить эту проблему экономичным способом?