|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 06 Mar 2003 16:44:30
To : Dmitry Statyvka
Subject : Re: как их усреднять?
--------------------------------------------------------------------------------
DS> Там есть одна бяка :
DS> из куч надо выкидывать элемент
DS> выпадающий из окна, а ты
DS> предлагаешь определять выкидываемый
DS> на основании вновь прибывшего.
Почему ? ...
Просто я удаляю не последний поступивший,
и даже не минимальный.
DS> После такого, первый элемент
DS> верхней кучи совсем необязательно
DS> будет медианой текущего окна.
Ага ...
Итак - нам нужен эл-т массива,
стоящий на определённом месте.
Будет пока говорить о
двух массивах (множествах) -
верхнем (элементы, большие медианы),
и нижнем (элементы, меньшие медианы).
Будем считать, что изначально
наименьшим эл-том верхнего множества
будет медиана, потом убедимся,
что это на каждом шаге будет так.
Во-первых, всегда на каждом шаге
нужно убрать последний элемент окна.
Hапример, нужно вести список (в кольцевом буфере)
ссылок на элементы в порядке поступления ...
Точнее, пар (ссылка, номер множества).
Hа каждом шаге будем поддерживать
размер мн-в такой, чтобы в сумме
равнялось размеру окна, а верхний был
на единицу больше, в версии же
с чётным кол-вом два мн-ва одинаковы по размеру.
Итак, убрали последний эл-т.
Мы должны как-то узнать, удалился он
из нижнего множества, или вернего.
Как-то узнали ;-)
Удаляем, и рассматриваем два случая -
когда новый элемент больше, или меньше медианы.
Если он меньше медианы -
добавляем новый элемент к нижнему множеству.
Если старый элемент удалили из верхнего мн-ва,
то извлекаем наибольший элемент из
нижнего множества, и добавляем к верхнему
(и добавляем пару в кучу).
Если новый больше или равен медиане -
добавляем новый элемент к верхнему множеству.
Если старый элемент удалили из нижнего мн-ва,
то извлекаем наибольший элемент из
верхнего множества, и добавляем к нижнему
(и добавляем пару в кучу).
Итак, выполняются условия -
Любой элемент верхнего множества
меньше или равен любому элементу нижнего.
В них соответствующее кол-во элементов.
Если использовать кучи, то можно
находить минимальный (максимальный)
за log2(длина кучи).
Удаление и вставка так же
производятся за log2(длина кучи).
Уфх :)
Сразу думать надо было ...
До встречи, всего наилучшего !
P.S.
Hу уж теперь-то я не ошибся !
А если даже и ошибся, идея-то понятна ? :)
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
