|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 14 Feb 2003 19:00:09
To : Aleksey Vaneev
Subject : Re: Максимум в " бегущем окне"
--------------------------------------------------------------------------------
Я так думаю, надо поступить вот как:
1. Значения точек хранить в дереве. Можно - в бинарном,
а можно - и в дереве с большей связностью.
В таком случае и время поиска, и время вставки в дерево
будет Log(N). Далее будем рассматривать бинарное дерево
как наиболее компактное по памяти.
2. Имеем кольцевой список длины N, которуй указывает на элементы
дерева в порядке их "прихода".
Про поиск максимума - понятно. Там просто надо пройти по дереву
и найти макс. элемент.
Замену же самого старого элемента на вновь прибывший делаем так:
1. По указателю, взятому из кольцевого списка, идем в самый старый
элемент дерева.
2. Исключаем этот элемент из дерева.
3. Заносим в этот элемент новое значение.
4. вставляем этот элемент в дерево.
5. Сдвигаем указатель кольцевого списка.
Hетрудно видеть, что при такой организации данных
в дереве всегда находится N элементов. Поэтому дерево и
кольцевой список можно организовать не в динамич. памяти,
а группой массивов. Если же N < 2^16, то массивы
"указателей" и кольцевой список можно вообще сделать
из unsigned_short-ов.
Итого, на каждый элемент в буфере имеем 8
дополнительных байт данных, обеспечивающих
быстрое манипулирование.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Максимум в " бегущем окне" 