|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Zahar Kiselev 2:5030/382.1 02 Mar 2003 01:05:54
To : Evgenij Masherov
Subject : как их усреднять?
--------------------------------------------------------------------------------
Mar 01 09:18 03, Evgenij Masherov wrote to Zahar Kiselev:
EM>>> Примером метода второй группы является замена среднего
EM>>> арифметического
EM>>> медианой - значением, находящимся посредине упорядоченной по
EM>>> величине выборки
ZK>> Осталось придумать алгоритм, позволяющий делать такую выборку в виде
ZK>> "скользящего окна" по последовательности отсчетов.
EM> Первые N сортируем, медиана посредине. Запоминаем позиции элементов
EM> в исходном сигнале. При сдвиге выбрасываем ушедший из выборки элемент
EM> (сложность O(N)) и добавляем новый (сложность O(N))
Да, примерно такая мысль пришла и мне в голову - именно об этом я и писал, когда
имел в виду использование "частичной отсортированности" масива и применение
алгоритма сортировки, хорошо работающего именно с такими массивами
(сортировка вставками?).
Hо вот красивая реализация этого на Си что-то за день не придумалась. А
"красивая реализация" тут нужна, так как этот код после отладки предполагается
запихивать в процессор, встроенный в прибор. И от сложности этого кода будут
зависеть требования к этому процессору.
EM> При использовании деревьев можно, похоже, снизить до логарифмической, но
EM> навскидку описать не могу.
С деревьями у меня в голове чтоже что-то не складывается...
А вот с массивами есть следующая мысль.
Создать два вспомогательных массива указателей. Один указывает на собственно
сами обрабатываемые значения, а указатели из второго массива указывают на
указатели в первом массиве. Двойная косвенная адресация весьма эффективна, так
как ее аппаратная поддержка есть в большинстве процессоров.
При этом переставлять при сортировке будем не сами значения, а указывающие на
них указатели из первого массива, "глядя" на значения при помощи косвенной
адресации. При этом при каждой перестановке будем корректировать указатели
второго массива, чтобы они продолжали указывать на одни и те же указатели в
первом массиве и соответственно за счет двойной косвенной адресации - на те же
самые значения. То есть несмотря на перестановки при сортировке, в результате мы
как бы имеем массив значений как в сорированном виде, так и в своем исходном
порядке. Первое нам нужно для получения среднего значения, а второе - для
циклической замены элементов при продвижении окна. Первое очевидно, а замену
производим циклически перемещаясь по второму массиву и заменяя после каждого
вычисления один следующий по порядку элемент в исходном массиве значений,
обращаясь к нему через двойную косвенную адресацию. Причем фактически там будет
даже не замена элемента как такового, и не двойная косвенная адресация, а
одиночная - корректировка указателя в первом массиве так, чтобы он указывал на
следующий элемент в большом буфере, куда поступают новые значения. Поступать-то
они вероятнее всего будут асинхронно по отношению к процедуре усреднения - так
как темп работы датчика фиксированный и довольно высокий.
Таким вот извращенным образом я надеюсь избавиться от дополнительных циклов,
ищущих элемент, над которым надо совершить какое-то действие между выполнениями
алгоритма сортировки, а заодно и от копирования значений во временный массив.
И все равно не уверен, что быстродействия хватит:(
Zahar(@spbdept.rbc.ru)
--- Msged/LNX 6.1.1
* Origin: Остров Большой Березовый: http://birch-island.spb.ru (2:5030/382.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
