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

Использовать heap для хранения? И хранить только половину элементов. Максимальный элемент это медиана. Добавление за логарифм обращений к памяти.

Только связные списки помогут тебе. Каждое новое значение будешь втыкать в соответствующее место уже отсортированного ряда. Но, сам понимаешь, это долго.

И еще раз повторю тебе: бросай эту кулибинщину и калокубство! Почитай книжки для начала.

Почему бы тебе не перестать засирать каждую мою тему своими тупыми постами? Мне не интересны твои пионерские достижения.

А с какой длины профит начнется? Если через референсы бегать, обращений к памяти сразу вдвое больше как минимум.

Наверное что-то такое: https://rcoh.me/posts/linear-time-median-finding/

Там единоразово 2n обращений к памяти для вычисления медианы.

А у меня 1/2n на каждом добавлении данных - в сумме дольше, но зато время блокировки меньше (данные добавляют по прерыванию, по мере равномерного поступления).

Какие еще референсы? Двоичная куча это массив

Тогда я не понял, в чем суть предлагаемого улучшения. По сравнения с тем что я описал.

Это кто здесь пионер?

Ты настолько офигенную пургу несешь, что просто смешно! Когда уже почитаешь спецлитературу, прежде чем лезть в программирование?

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

Связный список тоже придется проходить линейно - бинарный поиск здесь не используешь.

Просто сделай несколько реализаций и сравни. Делов-то!

// но медиана для переменного количества объектов звучит странно

Насколько я понял таое решие квадратичное. Или я не понял. Если отсчеты призодят в случайном порядке то теье нпдо для каждого просканировать массив чтобы понять куда вставить. А мое nlogn в худшем случае

У меня прилетает по одному отсчету за прерывание. Смысл в том чтобы не блочиться надолго. В моем случае вставка одного отсчета => скан 1/2 от набранных элементов.

Если в максимуме 128 отсчетов, значит на последнем прерывании будет скан с 64 обращениями к памяти.

Если все просуммировать, то конечно дольше. Но вот каждое отдельное прерывание лочится существенно меньше, и мне это важнее.

И еще в моем случае нужно хранить строго половину последовательности

Если предыдущие отсчёты отсортированы, то скан бинарным поиском места вставки будет в log_2 128 элементов,то есть 7 чтений.

В моем решении на вставку потребуется log2(128) это кажется меньше 64

Память менее критична, там небольшой размер. Мне критична максимально возможная блокировка проца.

А как делается быстрая вставка с сохранением возможности доступа по индексу?

Если простой связный список, то вставка будет быстрой, а доступ по индексу - сканом, и методом половинного длеления искать не выйдет.

Про это в топике не было. Зачем тебе доступ? Медиана будет всегда в одном месте в нулевом или в последнем элементе, смотря какая куча - minheap или maxheap

Бинарный поиск требует доступа по индексу. Как можно иметь одновременно и доступ по индексу и быструю вставку?

Если на вставке начнет копироваться кусок массива, это затрат примерно столько же сколько на скан. Оцениваю самый худший случай.

мне одному кажется, что ты хочешь странного?

Зачем тебе доступ?

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

Всякую торсионщину вроде сегментированных массивов пропустим, это не будет эффективно на столь малых размерах.

Я никогда не скрывал, что хочу странного. Хобби же.

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

Кажется мое решение тебе не подойдет. Но есть улучшенное твое.

https://stackoverflow.com/questions/15319561/how-to-implement-a-median-heap

Доступ по индексу - ну это массив. Правда это куча и тебе по индексу там так просто не поискать. Вставка- прочитай на википедии, это тривиально. По сути идея в том сто тв хранишь отсортированный список, который быстро обновлять

Binary heap и трюки для оптового обращения к памяти.

Прочитай что такое куча...

https://ru.m.wikipedia.org/wiki/Куча_(структура_данных)

Мое решение будет работать после n/2 отсчетов. По ссылке начнет сразу после первого. Оно похоже на твое с лвумя массивами но не квадратичное а логарифмическое

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

вы точно хотите медиану (то есть получить вектор из типичных соседних), а не типичное значение «отсчёта» ? формулировка задачи подхрамывает на все три имеющиеся лапы :-)

медиану можно быстро считать асемблером - всё равно есть чтение исходного массива и запись результата, а сами сравнения (поиск среднего из 3-х) можно сделать на регистрах:

4 общих регистра, R0,R1,R2 - значения, R4 - результат.
2 адресных - src,dst
1.инициализация : R0=src[0], R1=src[1], R2=src[2], src+=2 
2.считаем медиану R4=median R0,R1,R2 , *dst=R4, dst++
3.R0=*src++;
4.считаем медиану (см.2)
5.R1=*src++;
6.считаем медаину
7.R2=*src++;
8.считаем медиану
9. jmp 3
контроль за границами массивов добавить по вкусу  
Код вам тут по просьбе сделают. 

Медиана это не вектор из типичных соседних.. Это средний элемент в отсортированном наборе значений.

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

Сейчас искал так: https://stackoverflow.com/search?q=waveform zoom

Но не нашел тот классный ответ как это делается правильно чтобы работало быстро. Пошурши в эту сторону.

Раз уж переключились на «скользяшие методы», м.б. попробуете мой исходничек из вашей предыдущей темы ( Посоветуте оптимальный алгоритм поиска медианы (комментарий) )

А лучше - выложите сигнал со входа фильтра, сам попробую.

Ваще мало данных (что за сигнал и помеха, их параметры. Цель - по каким параметрам оптимизируется), деятельность напоминает тыканье пальцем в небо.

Медиана это не вектор из типичных соседних.. Это средний элемент в отсортированном наборе значений

помниться TC в предыдущих своих темах делал медианные фильтры с разными окнами, поэтому то что он сейчас хочет читается то-ли фильтром, то ли-ли поиском средней статистики.

поставь какой-нибудь атом в свою сверлилку :)

Я не очень понимаю, как такое возможно одновременно.

Одновременно используй и связный список, и массив: после того, как впихнешь очередное значение в связный список, копируй весь список в массив. Далее для поиска нового индекса будешь использовать бинарный поиск. Нашел в массиве индекс места, куда сделать вставку — сделал в цикле *ptr = *ptr->next нужное количество раз, сделал вставку, скопировал в массив...

А?

Еще один вариант — обычное дерево. Кстати, почему бы тебе действительно не воспользоваться деревьями для вычисления медианы?

Судя по темам ТС, он делает инструмент пыток, который будет менять скорость сверления (зубов? костей?) в зависимости от тональности и громкости воплей поцЫента.

да и вообще обработку сигналов можно на десктопе делать, а управляющие сигналы по проводам слать

тогда и проблемы с быстрым подсчётом медианы не будет

Ну, не всегда нужно тащить комп. Некоторые задачи вполне решаемы микроконтроллерами.

Правда, надо все же понимать некие границы: скажем, нет никакого смысла корячиться с TCP/IP на STM32F407, если за 600 рублей можно взять Orange Pi zero, где нормальный линукс, а отсутствие GPIO решается довесом дешевых МК.

Order statistic tree, например.

 l = sorted(l) 

- это линейно?

А ваще-то у медианного фильтра - дребезг фронтов, а у устредняющих - задержка, одинаковая по восходящему и падающему (т.е ШИМ сохранится)

- это линейно?

Пардон, не дочитал до конца ссылку.

Кстати, можно твой массив отсортировать за линейное время с помощью radix-sort и взять средний элемент. Может это самое простое.

https://github.com/speedcontrols/ac_sc_grinder/tree/master/doc/data

Там вычисляется скорость по каждой паре отсчетов. Но из-за помех результаты мотыляет. Зато результатов много :) . Поэтому медиана должна нормально прокатить.

Надо брать только тот кусок, где ток нарастает, и пока напряжение не упадет до нуля. Остальное - мусор.

Это несомненно будет хорошо работать на больших массивах. Но там есть накладные расходы, которые скушают профит при малых размерах.

Случайно не знаешь с какого момента профит начинает соответствовать логарифмическому?

Да, ты прав, с добавлением парами я переборщил. Это не улучшит код. Сделал как на SO описывали:

https://github.com/speedcontrols/ac_sc_grinder/blob/median/src/median.h

У тебя нет примерной оценки, с какого размера данных binary heap станет эффективной? Явно ведь в фильтр для 8 элементов совать не стоит.

С оптовом обращением к памяти пока повременим. Там сложность возрастает не пропорционально профиту. Вроде скорости и так должно хватить на 64 элемента, а дальше результат скорее всего уже не улучшится.

{2, 4, 6, 8} Что тут медиана?

Почитай на википедии?

{2, 4, 6, 8} Что тут медиана?

5 по определению медианы.

Что-то мне подсказывает, что задача поставлена некорректно.

Если я правильно помню, то тебе нужно убрать выбросы из сигнала,
для этого необязательно вычислять именно медиану.

Если что - вот мой прошлый пост на эту тему: Посоветуте оптимальный алгоритм поиска медианы (комментарий)

только там надо поправить чутка:

int16_t tr_mean(int16_t input)
{
    int32_t delta = (int32_t)input - (mean / denom);
    int32_t nz = delta * delta; /*Оцениваем квадрат отклонения*/
    
    int32_t alpha = (nz > noise * 9)?med:fast; /*Изменения < 3s будем копить быстрее*/
    mean  += delta * alpha;

    noise += (nz - (noise / denom)) * slow; /*Оценку шума делаем медленнее всего*/
    return (int16_t)(mean / denom);
}

Там небольшое постоянное количество обращений к памяти и
постоянное небольшое время вычисления.

Как раз для быстрой нелинейной фильтрации.

И да, зачем ты создаешь новый тред, когда можно продолжить в старом?

ААААААААААААААААА!!!
МОИ ГЛАЗААААААААААААААА!!!