LINUX.ORG.RU

Как «размазать» поиск медианы?

 


1

1

Нужно считать медиану на последовательности отсчетов длиной 8...128.

Т.к. за один раз считать долго, хочется апдейтить медиану после каждого нового отсчета (или можно заталкивать данные парами, чтобы четность не менялась).

Как это проделать наиболее эффективным образом (с минимумом обращений к памяти)? Можно сделать 2 массива (с нижней половиной и верхней половиной значений). Тогда добавление 2 новых элементов в худшем случае будет ~ 1/2 линейного скана (когда оба элемента попадают в одну половину).

Что-то еще можно придумать? Все для Cortex-m0/m3, где обращение к памяти - 5 тактов.

★★★★★

Ответ на: комментарий от beastie

Не факт. Точнее строго ты прав, но при большом количестве элементов для уменьшения операций вполне могут договориться брать меньшее или большее число.

ТС, а это тебе. https://stackoverflow.com/questions/10657503/find-running-median-from-a-strea...

Хотя можешь начать отсюда https://stackoverflow.com/questions/11361320/data-structure-to-find-median

И да, в гугл с запросом data structure to find median

peregrine ★★★★★ ()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от peregrine

Сенькс, очень годные ссылки именно по моему вопросу.

Я пока погоняю на костыле, который слепил. Неохота ковыряться как gcc соптимизирует навороты с priority_queue под кортекс. Потом посмотрим, делать нормально или плюнуть.

Vit ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

Желающие смогут потом заслать PR-ы :).

Я ж не писатель на сях, поэтому слежу только за архитектурой - чтобы бизнес-логика была правильно нарезана, и не лез связный код. Этого в данный момент достаточно.

Vit ★★★★★ ()
Ответ на: комментарий от Vit

Я ж не писатель на сях

Мать моя женщина! И это чудо-юдо лезет программировать микроконтроллеры...

anonymous ()
Ответ на: комментарий от Vit

Получилось так

#include <stdio.h>

#define QA(A) (sizeof(A)/sizeof((A)[0]))

float yy[][4] = {
//{time, Voltage_V, Current_A, Derivative},from voltage_current_speed.ods
#include "vcs_d.c"
};

float sa = 1.e4, sz = 1.e-10;//для настройки
float x[2] = { 0, 0 };
float p[3] = { 10, 0, 10 };
float t = 0;

void filt(float tot, float izm)
{
    float dt, x1, p1[3];
    float tta, y, s, k0, k1;

    dt = tot - t;
    tta = dt * dt * sa;
    p1[0] = ((tta / 4.0 + p[2]) * dt + 2 * p[1]) * dt + p[0];
    p1[1] = (tta / 2.0 + p[2]) * dt + p[1];
    p1[2] = tta + p[2];
    s = p1[0] + sz;
    k0 = p1[0] / s;
    k1 = p1[1] / s;
    x1 = x[0] + dt * x[1];
    y = izm - x1;
    x[0] = x1 + y * k0;
    x[1] += y * k1;
    p[0] = p1[0] - k0 * p1[0];
    p[1] = p1[1] - k1 * p1[0];
    p[2] = p1[2] - k1 * p1[1];
}

int main()
{
    int i;

    //printf("time; Current, A; filt(Current, A); filt(Derivative)\n");
    for (i = 0; i < QA(yy); i++) {
	filt(yy[i][0], yy[i][2]);
	printf("%.10f %.10f %.10f %.10f\n", yy[i][0], yy[i][2], x[0], x[1]);
        t=yy[i][0];
    }
    return 0;
}
Выделяет б.м. гладкий ток и его производную. (задача была - выделить производную тока для ПИДов, так?) Это для х86(32бит флоат) или stm32F4. Интервал времени между отсчетами м.б. произвольный.

Можно упростить(и соотв. ускорить) если интервал между отсчетами фиксированный, уйдет dt, Сейчас интервал =55.944(+- 1е-5). Тогда можно(легче) затолкать все в int-ы.

anonymous ()
Ответ на: комментарий от peregrine

а зачем в медианном фильтре огромное число элементов? я сейчас на полном серьезе, задача фильтра выкинуть помехи и при скользящем окне даже в 4 отсчета это будет решено до уровня адекватности квантования, для совсем параноиков модно взять 6-8, но это только увеличит время отклика. ну а полученное значение всегда можно заинтегрировать любым способом по вкусу

anonymous ()
Ответ на: комментарий от anonymous

а зачем в медианном фильтре огромное число элементов

Медиану можно не только для фильтра искать, но и для задач мат. статистики. Например, для расчета медианной зарплаты.

peregrine ★★★★★ ()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от peregrine

сейчас речь по конкретной задаче и там статистикой не пахнет

anonymous ()
Ответ на: комментарий от anonymous

Меня не колышет какая конкретная конечная задача у ТС-а, я отвечаю по той, которую он спрашивает. Он не уточняет где ему медиану считать надо.

peregrine ★★★★★ ()
Ответ на: комментарий от peregrine

очень разумный подход :) а надо бы спросить было, впрочем я на первой странице спрашивал, ответа не дождался. это не считая способа измерения скорости по току, про то что двигло обратимая машина что-то никто не вспомнил

anonymous ()
Ответ на: комментарий от anonymous

ТС так и пышет бредовыми идеями.

anonymous ()
Ответ на: комментарий от anonymous

так чем бы не тешилось, лишь бы не бухало :)

anonymous ()
Ответ на: комментарий от Vit

Если интервалы между отсчетами одинаковые (dt=const), то совсем просто:

#include <stdio.h>

#define QA(A) (sizeof(A)/sizeof((A)[0]))

float yy[][4] = {
//{time, Voltage_V, Current_A, Derivative},from voltage_current_speed.ods
#include "vcs_d.c"
};

float d1 = 0.5, d2 = 0.05; //настройки тут
float a = 0, b = 0;

void filt(float izm)
{
    float z;
    a += b;
    z = izm - a;
    a += d1 * z;
    b += d2 * z;
}

int main()
{
    int i;

    //printf("time; Current, A; filt(Current, A); filt(Derivative)\n");
    for (i = 0; i < QA(yy); i++) {
        filt(yy[i][2]);
        printf("%.10f %.10f %.10f %.10f\n", yy[i][0], yy[i][2], a, b);
    }
    return 0;
}
Пять строчек, кто меньше :)

Результат почти совпадает с предыдущим вариантом.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.