LINUX.ORG.RU

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

 


1

1

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

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

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

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

★★★★★

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

OxiD ★★★ ()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Vit ★★★★★ ()

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

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

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

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

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

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

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

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

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

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

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

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

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

OxiD ★★★ ()

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

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

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

OxiD ★★★ ()

считать медиану на последовательности отсчетов длиной 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
контроль за границами массивов добавить по вкусу  
Код вам тут по просьбе сделают. 
MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

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

OxiD ★★★ ()

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

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

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

deep-purple ★★★★★ ()

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

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

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

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

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

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

MKuznetsov ★★★★★ ()

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

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

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

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

А?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Vit ★★★★★ ()

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

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

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

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

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);
}

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

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

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

shkolnick-kun ★★★★ ()
Последнее исправление: shkolnick-kun (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.