Comments 128
Если массив уже отсортирован по возрастанию, то куча "max_heap" будет постоянно расти, потому что "удаленные" элементы внутри неё никогда не станут её корнями.
Навскидку, можно попробовать хранить в кучах не сами значения элементов, а их индексы в массиве. В хэш-таблице для каждого индекса хранить его позицию в куче (обновлять эти данные при просеивании), потому что зная эту позицию, можно быстро удалить элемент из кучи, даже если он не корневой. Причем вместо хэш-таблицы тогда достаточно массива длиной k, ведь "хэш" для индекса можно считать как i % k. У нас в любой момент времени всего k элементов в работе, и когда вываливается i-й элемент с хэшем h1 = i % k, то добавляется элемент h2 = (i + k) % k = h1, то есть заезжает в ту же ячейку
торможу с утра, рано встал но эта задачка напомнила мне старые схемы, типа "интегратор - линия задержки - вычитатель":
cumsum - интегратор
линия задержки - на выход идет cumsum[i-n] где n ширина фильтра
вычитатель вычитает задержанный сигнал cumsum[i-n] из текущего сигнала с интегратора cumsum[i] : window_sum = cumsum[i] - cumsum[i-n]
делитель на n - moving_average[i] = window_sum / n.
остается проверить наличие ближайщих целых значений в буфере по вычисленному среднему из 4го шага (хеш мап значения элемента на массив/лист индекса элемента в буфере использовать - reverse index типа) или просто округлить (в реальной задаче, в этой элемент так понял нужно брать из существующих а не просто округление)? Пойду кофе попью
Как то сложно. Вставка в отсортированный массив не решает ту же задачу?
Решает, но медленнее. Тут делается O(log(W)) операций при сдвиге окна, а для вставки в отсортированный массив надо O(W), где W - размер окна. Если же вместо массива делать какое-нибудь балансированное бинарное дерево, то там константа чуть хуже, потому что эти деревья чуть-чуть медленнее куч.
С утра не сразу проснулся когда статью открыл. Почитал, хороший алгоритм:
Добавление нового значения: O(log N)
Удаление старого значения: O(log N)
Получение медианы: O(1)
Амортизированная стоимость на операцию: O(log N)
Две кучи: 2-4 операции O(log N) + балансировка
Простая сортировка: O(1) для малых N
На 15 элементах почти в 3 раза быстрее чем алгоритм со вставкой в сортированный массив но и требует 3 раза больше памяти (обмен память на скорость).
В сбалансированное дерево тогда уж, чтоб вставка/удаление дорогими не были.
Сбалансированные деревья скорее всего дадут не точную медиану, а значение медианы с погрешностью.
С чего бы? Сбалансированное дерево позволяет получить элемент с заданным номером за O(log N).
С погрешностью – это если на гистограммах делать или приближать гистограмму моментами.
Нужно поставить решающий эксперимент.
Зачем? Контейнер для хранения чисел внутри окна – чёрный ящик. Мы в него на каждом шаге кладём одно число, убираем одно число и извлекаем медиану.
Референсная реализация – отсортировать массив и взять из средней позиции. Легко доказать, что результат будет тот же.
Эксперимент был бы интересен для приближения гистограммы моментами и тому подобных приближённых методов (позволяющих считать за O(1) независимо от размера окна)
Или вы имели в виду эксперимент по скорости?
Нет, в сбалансированных деревьях можно найти элемент по его номеру. Правда, для этого надо хранить в каждой вершине размер поддерева и стандартные реализации в большинстве языков так не умеют.
Проблема со сбалансированным деревом в том, что там для поиска медианы надо писать его руками и хранить в каждой вершине размер поддерева. Стандартные реализации в большинстве языков так не умеют. Так что реализация с двумя кучами или двумя деревьями получается проще и даже быстрее.
Timsort вот еще посмотрите может ускорит
Вот вам яркий пример. Вы измеряете расстояние UWB трансиверами между радиопередатчиками и вдруг у вас образуются единичные редкие отбросы, которые никак не характеризует измеряемую величину. Или вы опрашиваете емкостную кнопку и от скача питания она тоже может дать редкие, но высокие значения семпла.
С примером графика сырых и отфильтрованных данных получившимся фильтром было бы интереснее)
Допустим, окно из 16 элементов. Делаем сдвиговый регистр(линию задержки) на 16 элементов. С каждым новым элементом считаем добавляем к некому числу текущий элемент и вычитаем 16й. Это число есть сумма последних 16 элементов. Добавляйте свою логику для контроля единичных выбросов. Так у меня сделано на fpga. Окно при использовании RAM блоков может быть весьма большим, на одном из проектов 2*1024 элемента. Без всяких куч и прочего.
Это немного не тот алгоритм.
Скользящее среднее – совсем другой фильтр. Лучше убирает гауссовский шум, хуже удаляет выбросы. Разница очень заметна при обработке изображений: медиана убирает одиночные точки/пятнышки на изображении, оставляя границы резкими, бегущее среднее – размывает границы, а точки полностью не удаляет.
Это не в том смысле, что медианный фильтр лучше – он просто решает другие задачи.
Неужели так сложно догадаться как с помощью скользящего среднего решить задачу удаления выбросов? Без всяких куч или даже просто массивов?
Это, наверно, из тоже же серии задач про Метод инверсии или методика проектирования «от противного», абсурдной перестановки. или проще?
Да, сложно.
в ВУЗах обычно про медианный фильтр даже не вспоминают,
Вы же знаете почему про него не вспоминают в ВУЗах? Почему на нем нельзя построить никакой математики цифровой обработки сигналов? Почему с точки зрения ЦОС это изобретение, вообще говоря, не является фильтром?
Хотя в качестве упражнения по программированию вполне себе интересно, пока вы не пытаетесь строить ЦОС на этой основе.
Как человек, 10 лет занимавшийся разработкой софта для анализа изображений, могу ответить: да, сложно.
Конечно, скользящее среднее – это база, если в вашей задаче можно им воспользоваться – ура, мы сэкономили кучу ресурсов. Но оно (как и дешёвые решения на его основе) подходит не всегда. Могут понадобиться оба фильтра – и медиана, и скользящее среднее (возможно, повторённое 2-3 раза, чтобы приблизить к гауссовскому фильтру).
Ещё, кстати, в копилку дешёвых методов – open и close фильтры. Вначале выполняем бегущий минимум (эрозия), потом бегущий максимум (дилатация). Ну или наоборот. Убирает светлые или тёмные пятна соответственно. Для изображений есть усовершенствование – open/close with reconstruction. Но тоже особо не используется отдельно.
Кстати, бегущий максимум/минимум, не зависящий от размера окна – сам по себе интересный алгоритм. Изобрели, если я правильно помню, только в 80-х. Попробуйте до него додуматься сами, не подглядывая – это правда интересно (делается без сложных структур данных).
бегущий максимум/минимум, не зависящий от размера окна
https://leetcode.com/problems/sliding-window-maximum - этот?
Да, это оно. Конечно, для leetcode задачка так себе, т.к. она больше на знание алгоритма (не думаю, что многие смогут придумать его сами). Интересно, уложится ли в тайминги литкода решение с логарифмической сложностью.
Там по факту два разных решения, одно из которых легко придумать по мотивам реализации очереди на двух стеках и хранении максимумов для стека (у меня так и вышло)
Не понял. Короче, у вас решение за O(1) работает или за O(log N)? Для O(1) есть хитрость, просто хранить две кучи и обновлять их на каждом шаге – получите O(log N).
У меня работает за амортизированное O(1) на элемент, то есть за O(N) на всё про всё. Вот, опубликовал. Раз в k итераций собираю стек максимумов по окну справа налево, далее на следующих k итерациях благодаря этому под рукой имеется максимум среди тех элементов, которые покидают окно
Угу, это тот самый алгоритм, который изобрели удивительно поздно, несмотря на его простоту.
Кстати, если не ошибаюсь, тут можно добиться не амортизированного, а "истинного" O(1) на элемент, если вместо базовой идеи очереди на двух стеках, использовать великую и ужасную очередь на 6 стеках (и соответственно к ним стеки с максимумами). Насколько это будет оптимально, не берусь судить, но факт любопытный
Я б скользящее окно размером порядка фильтра сохранял и удалял последний старый элемент на каждой итерации из соответствующей кучи, добавляя новый.
При работе с бинарной кучей удалять можно только то, что лежит в корне кучи.
Если число закопано, то ничего быстро не сделаешь.
Долго искать элемент внутри кучи. Но если знаем его позицию, то можно быстро удалить (переносим на его место последний элемент, потом просеивание вниз или вверх)
Это в базовой куче. Если завести массив отслеживания позиций элементов в куче (в код кучи вносится модификация - при каждом свапе элементов этот массив корректируем) - то можно вполне быстро.
Спасибо. Но... проверьте правописание и пропущенные фрагменты предложений.
Где ещё остались опечатки?
При использовании этого метода элементы которые надо удалить помечаются словом откладываются
Я в этот момент решил, что статья - перевод без тега "перевод".
Перебалансировка куч выполняется после каждой операции добавления или удаления, чтобы свойство половинного размера двух куч.
Как насчет использования бесплатных или дешевых сервисов проверки текстов, таких как Яндекс Спеллер, Text.ru, Орфограммка? А то обидно получается: элементарные ошибки затрудняют восприятие достойного контента.
По оборванным предложениям - ответили @Nemoumbra и @Mike-M.
"но не удалены физически из кучей."
"В случае сильного разрастания кучей можно вручную удалить ненужные более элементы"
"Реальные же размеры кучей не должны участвовать, как управляющие данные для алгоритма."
Строго говоря, алгоритм довольно несложно доработать так, чтобы устаревшие элементы удалялись из куч в тот же момент, когда они вышли из окна. Но для этого потребуется заменить кучу на ваше любимое дерево поиска — тогда удаление станет возможно за O(log N) на каждый новый элемент, где N — размер окна. А реализация какого-нибудь КЧД это уже далековато от "несложно" =)
Однако же альтернативный вариант можно подглядеть здесь: https://stackoverflow.com/a/10696252 — там предлагается аналогичное решение, но с заменой кучи/дерева на список с пропусками, который обладает примерно теми же преимуществами и без необходимости реализовывать балансировку. Но в худшем случае он потребует O(N), что становится практически аналогично quicksort.
В целом, задача как ни крути сводится к поддержанию сортированного списка и быстрее чем O(log N) её решить в общем случае вряд ли выйдет. Учитывая что N (размер окна) довольно мало, то боюсь что любой выигрыш от сложных структур данных запросто будет нивелирован прямолинейностью quicksort.
Если числа целые и ограничены например 00-FF, то ту наверное обычный массив который в ячейке с индексом равным этому числу храниться количество раз, когда это число встретилось в потоке может быть проще и быстрее для вычисления медианы и по памяти не очень затратно.
интересно. я не понял, а зачем сортировку делать. Gap_buffer мне это вспомнилось
есть еще емуляция буферного окна, это когда просто есть мгновенный доступ к нужным позициям-курсор в окне, тоесть установить курсор(и проделать фильтр)
тогда получается есть 1 heap-array(cм. ниже) для всех семплов например песня, если надо его можно поделить на части более маленькие, тогда окно будет выборка тоесть get[i] или нужного количества семплов из общего количества семплов.
если это перводить на рельсы сленга gap-buffer, тогда мы получаем на выходе следующее:
есть абстракция array-heap кусочек - строка
есть абстракция buffer-heaps которая знает сколько кусочков и где они, в ней есть курсор и определение строки(в примере это размер array-heap)
тогда МФ будет просто работа с кусочками[n] из buffer(по типо как в окно программы помещается 40 строк эти строки мы рисуем и управляем курсором и позицией)
тоесть, вычисляем общее количество семплов, потом делим, добавляем семплы в array-heap-это 1 кусок, а буфер хранит эти строки так называемые и даёт доступ к адресам этих строк-семпловых
typedef struct {
char *data;
size_t length;
size_t capacity;
} String;
typedef struct {
String **line; //pointer to lines
size_t nlines; //number of lines
size_t capacity; //
size_t currLine;
size_t totalSizeChars;
int stateFlag;//0 scratch,1 openFile
} Buffer;
Удаление или замена элемента в куче – O(log N), можно не хранить удалённые элементы.
Хорошо. А как реализация этого на си выглядит?
Уффф... Спросите у чатгпт, я на память не воспроизведу. Вкратце – заменяем элемент (для удаления – на последний из кучи) и восстанавливаем порядок в куче операциями siftUp/siftDown, там не надо всю кучу перелопачивать.
static bool min_heap_make_down(BinHeapHandle_t* Node, int32_t index) {
bool res = true;
while(index < Node->size) {
int32_t left_child, right_child, smallest;
left_child = 2 * index + 1;
right_child = 2 * index + 2;
smallest = index;
if(left_child < Node->size && Node->array[left_child] < Node->array[smallest]) {
smallest = left_child;
}
if(right_child < Node->size && Node->array[right_child] < Node->array[smallest]) {
smallest = right_child;
}
if(smallest == index) {
break;
}
swap_i32(&Node->array[index], &Node->array[smallest]);
index = smallest;
}
return res;
}
static int32_t min_heap_check_node(BinHeapHandle_t* const Node,
const int32_t value,
uint32_t my_index) {
int32_t index = -1;
if (my_index < Node->size) {
if (value == Node->array[my_index]) {
index = my_index;
} else {
if (Node->array[my_index] < value) {
uint32_t left = 2 * my_index + 1;
index = min_heap_check_node(Node, value, left);
if (-1 == index) {
uint32_t right = 2 * my_index + 2;
index = min_heap_check_node(Node, value, right);
}
} else {
index = -1;
}
}
}
return index;
}
bool min_heap_delete(BinHeapHandle_t* const Node, const int32_t value){
bool res = false;
int32_t del_index = min_heap_check_node(Node, value, 0);
if(0 <= del_index) {
swap_i32(&Node->array[del_index], &Node->array[Node->size-1]);
Node->size--;
res = min_heap_make_down(Node, del_index);
}
return res;
}В такой же хеш таблице надо для каждого элемента в куче хранить его позицию (при просеивании элементов не забывать обновлять позиции у обоих). Потом при удалении вы уже знаете, где элемент лежит - меняете его с последним в куче и оттуда удаляете. А то, что на его место поставили надо просеять или вниз или вверх.
Сделал функцию удаления из куч. Стало работать быстрее в два раза.
посмотрите такую структурку
struct Node {
using Ptr = std::shared_ptr<Node>;
Ptr left;
Ptr right;
std::vector<int> values; // Храним все значения, вставленные в этот узел
int size; // Общее число элементов в поддереве
Node() : size(0) {}
Node(int val) : values({val}), size(1) {}
};тут есть вектор, тут нету очереди, тут нету сортировки, за место неё амортизация векторная, автоудаление вообщем, тоесть я проверяю вектор как окно, добавляю еще раз и происходит амортизация, а так да, придется искать ноду и чистить, соотв нужна функция собрать дерево, вставить, получить 0-Ктый елемент, получить медиану и сделать выбор про такие деревья я прикрепил еще ниже файл с описанием
сортировка делается при вставке кстати самим деревом
Quickselect или pickbest
Вся суть моего текста в том, чтобы сделать быстрый медианный фильтр именно на чистом Си. Не на С++.
Чтобы можно было портировать алгоритм на микроконтроллеры.
понял, С++ как сейфти проверка абстракции соответственно по статье ускорительных структур выходит нужна нода и последовательность
typedef struct {
int *data;
size_t len;
size_t cap;
}vec;, последовательность это просто структура, ну амортизация да, эту баго-фичу(буду с дебагером еще смотреть) я вообще только вчера увидел впервые
тут по скорости я не смотрел, а так медианы проходит на литкоде, первые 2 кейса показывает причем последовательно как будто шагает вообщем
получается BVH для медиан, причем сам BVH имеет выборку по медиане(в описании его тоже затрагивают)
ну и на реддите видел обсуждение такой структуры
На мой взгляд сделать можно сильно проще.
1) Сделайте 1 сложносвязанный список размером с размер окна и связывающий каждый элемент в 2 списка. Далее эти элементы свяжите в 1 список отсортированный по значению величини в ноде и во 2 список по порядку добавления.
Далее при добавлении нового элемента в кучу сделайте следующее: возьмите последний элемент из списка по добавлению и удалите его(поменяв указатели которые формируют список по порядку и список по значению). Далее в этом элементе поменяйте значение на новое и вставьте этот элемент в начало списка по порядку и в список отсортированный по значению в нужное место.
Медианный фильтр готов.. Не нужно ни внешние библиотеки, ни ребалансировки ни хэш таблицы и потребление памяти фиксированное, какие бы значения туда ни попадали.
Для получения среднего значения возьмите размер окна поделите на 2 и возьмите этот элемент из списка отсортированного по величине. Если вам нужны значения для серидины верхней и нижней кучи из вашего алгоритма - просто возьмите элементы 1/4 и 3/4 размера окна.
настоящее решение никому не интересно на хабре :). Как это без
библиотеки; ребалансировки; хэш таблицы; просеивании элементов ; поОкать - О(амен) О(м); ... ?
тут сразу становится не о чем поговорить :) !
А потом пользователи жалуются, что все тормозит. А просто программисту было лень "Окать" и он впендюривал наивные очень медленные решения повсюду. О-большое - это база программирования. Это знать надо.
когда нам 25+ лет назад надо было HD видео играть на пентиумах нас про всякие О-разноразмерных никто не спрашивал, всех интересовали фреймы в секунду. А теперь все учатся правильно писать О-большое, про фреймы в секунду никто не вспоминает! По моему это просто такой вид моды, мода пройдет, я думаю. Хотя теоретическая математика тоже важна, конечно, но она достаточно ограничена.
Я не понял. Есть ли возможность нарисовать эту структуру данных?
Вот нарисовал такой сложносвязанный список из 5 элементов. Он отображает какая будет структура связей при получении данных 35, 8, 17, 500, 21.
Если обходить используя указатели Head1, Tail1 - то это будет список по порядку добавления. Если его обходить используя указатели Head2, Tail2 - то это будет список отсортированный по значениям (8, 17, 21, 35, 500).
вставьте этот элемент ... в список отсортированный по значению в нужное место
Вот тут проблема. А как найти это место? Бинарный поиск в списке не работает. Просто пройтись по списку - это линейная сложность O(размер окна). Когда как решение в статье рабоатет за O(log(размер окна)), что на порядки быстрее.
Все эти хитрые структуры данных исключительно чтобы быстрее работало.
Если вам неважна скорость, то зачем извращаться со списками - просто берете последние W элементов из цикличиского буфера и сортируете каждый раз при запросе медианы. Два массива и sort.
Бинарный поиск в списке не работает.
это прям не решаемая проблема сделать чтобы бинарный поиск работал на упорядоченном списке?
Вот тут явно видно нежелание задуматься о сложности алгоритма.
Бинарный поиск основан на том, что можно быстро взять элемент по его индексу, что в связных списках не работает.
Бинарный поиск смотрит на элемент в середине и решает в какую сторону дальше идти: влево или вправо. Но как посмотреть на средний элемент в списке? Это не массив, где можно по индексу в одну арифметическую операцию получить адрес элемента. Тут придется пройтись по всему списку до середины. И потом опять также в нужной половине. Потом опять в четвертине и т. д. Каждый раз надо проходится до середины.
В итоге такой бинарный поиск выполнит n/2 + n/4 + n/8 +... = n-1 операций, т.е. оказывается ничем не лучше простого наивного линейного поиска. Только сложнее код и всякие лишние операции: линейный поиск может остановится не дойдя до середины, если наткнется на нужное место, бинарный же - всегда выполнит эти самые n-1 операций.
быстро взять элемент по его индексу, что в связных списках не работает.
он там выразился не совсем корректно, а вы не стали вникать, потому что просто не верите в более простое решение (без всяких умных слов), мне кажется.
Сделайте 1 сложносвязанный список размером с размер окна
поскольку размер списка жестко задан - это массив, а не список.
Верить полезно - английские ученые доказали :) !
> поскольку размер списка жестко задан - это массив, а не список.
Ну подумайте чуть глубже и посмотрите на весь алгоритм. Это все еще список и элементы хоть и хранятся в масиве, они там не упорядочены по возрастанию. Третий по порядку элемент может быть хоть в начале, хоть в конце массива и не проходясь по ссылкам вы его никак не найдете.
Если же вы сделаете хранение элементов в массиве по возрастанию, то зачем там вообще сложно-связный список, если все указатели будут на следующий элемент в массиве? А главная проблема, вставка в такой массив все равно будет линейной, ибо надо будет почти все элементы сдвигать, чтобы новый вставить в середину.
Так что никак вы бинарный поиск со списками так просто не скрестите, вы или убиваете скорость бинарного поиска, или скорость изменения списка. В итоге получается более сложное и медленное решение чем с простым массивом.
Вообще, если в эту сторону думать, то в итоге вы придете все к тем же балансированным деревьям поиска или скип-листам, которых и пытались избежать.
Ну подумайте чуть глубже и посмотрите на весь алгоритм.
дело в том что я смотрю не на алгоритм, а на задачу и думаю как ее решить самым простым способом.
Сначала надо доказать что выбранный алгоритм является самым простым.
Тут всегда есть выбор между эффективностью и простотой: самый простой способ обычно самый медленный, а самый быстрый - сложнее. Иногда есть что-то среднее балансирующее между простотой и скоростью.
Так вот, предложенный @krotos139 алгоритм и медленный и сложный. Он все такой же линейный как наивный способ вставки в сортированный массив, но при этом усложнен двусвязными списками.
Сначала надо доказать что выбранный алгоритм является самым простым.
Самый простой еще медленее: Вы просто берете последние W элементов и сортируете их каждый раз. Куда уж проще? Хотя, возможно, кому-то более простым методом покажется метод за O(W^2) - берете каждый элемент из окна и считаете, сколько там меньших или равных ему, и берете минимальный с нужным количеством. Тут нет сложной концепции сортировки, хотя если использовать библиотечную функцию, этот метод будет содержать больше кода и переменных.
Но вообще, формально доказать, что какой-то метод самый простой очень сложно, ибо простота - вещь сложно формализуемая. И вообще, оценки снизу доказывать сильно сложнее оценок сверху.
сдвигать? всмысле memcpy есть же, выделенное окно или та структура где будут фильтры можно представлять в виде блока данных просто вставили участок байт же нет?
просто вы сейчас описали тривиальный момент вставка определенного количества байт в центр строки
потом если смотреть по вики что такое МФ это ну картинка самое простое, а картинка это строки хотим мы того или нет
тоесть семпл это елемент строки, а строка это последовательность семплов и такая строка может считаться в байтах
тоесть самое ближайшее это uint32 codepoints строки
19 UTF-32 code units: [ 0x20 0x20 0x2f 0x2f 0x70 0x72 0x69 0x6e 0x74 0x5f 0x73 0x74 0x72 0x28 0x26 0x73 0x29 0x3b 0xa ]
25 UTF-32 code units: [ 0x20 0x20 0x2f 0x2f 0x70 0x72 0x69 0x6e 0x74 0x66 0x28 0x22 0x25 0x7a 0x75 0x5c 0x6e 0x22 0x2c 0x6d 0x61 0x78 0x29 0x3b 0xa ]
19 UTF-32 code units: [ 0x20 0x20 0x53 0x74 0x72 0x69 0x6e 0x67 0x5f 0x66 0x72 0x65 0x65 0x28 0x26 0x73 0x29 0x3b 0xa ]
25 UTF-32 code units: [ 0x20 0x20 0x2f 0x2f 0x70 0x72 0x69 0x6e 0x74 0x66 0x28 0x22 0x25 0x7a 0x75 0x5c 0x6e 0x22 0x2c 0x6d 0x61 0x78 0x29 0x3b 0xa ]
12 UTF-32 code units: [ 0x20 0x20 0x72 0x65 0x74 0x75 0x72 0x6e 0x20 0x30 0x3b 0xa ]
2 UTF-32 code units: [ 0x7d 0xa ]тоесть не окно идёт по семплам а курсор и в месте курсора подставляется медиана тоесть в месте курсора фильтрация
тогда получается из потока семплы попадают в буффер, и там курсор
in [buffer[cursor]] out
если произошел out скинуть курсор в начало и получить новый блок данных из входа
сдвигать? всмысле memcpy есть же
И за какую сложность, по-вашему, работает memcpy?
Cтроки тут вообще нипричем. Дальше просто несвязный бред написан, как у вас обычно и просиходит.
просто выделить 3*1024, и через функцию в буфере адресно можно конструировать выводной поток дописывать в конец поблочно по 3*1024, помимо memcpy есть прямой доступ к елементам 3х3(например ширина курсора внутри буфера)
Ничего непонятно, но очень интересно (нет).
да, потомучто у дерева есть недостатки в буферной обработке(лишние итерации, которые можно опустить прямым доступом)
а деревом пользоваться, а обращаться к лепесткам как по массиву, зачем если есть итак массив
пришло 3 строки в буфер курсор 3х3 считаем пишем чем хуже
если нет строк последовательность можно поделить на 3 и использовать offset
или не делить и идти построчным курсором до конца последовательности(вобщем деление последовательности даст улучшение, это все как с текстом, мы можем иметь 1 большую строку на гигабайт, а можем делить на строки )
Остановитесь, глубоко вдохните и выдохните. Осознайте, что другие люди не имеют доступа к вашим мыслям, у нас не распределенный разум-рой и нет телепатии. Перечитайте статью и ветку комментариев, потом составьте на бумаге всю цепочку ассоциаций от этого общего контекста к вашим мыслям и укажите главные из них в комментарии. Тогда и только тогда будут шансы что вас поймут.
Каждый раз перед тем как запостить комментарий, убедитесь, что он опрерирует теми же коцепциями, что и тот, на который вы отвечаете. А если нет, то вы должны составить логическую цепочку от уже упомянутых концепций к вашим.
Вот memcpy вы даже к цитате привязали и на эту часть я ответить что-то разумное смог. Остальное как с неба свалилось: какие-то строки, курсоры, буфера.
я выдыхая осознал когда вы заминусили существование использования в таком роде структур memcpy впринципе всё понял
а что не так, человек пишет про последовательность байт, эту последовательность при получении надо поделить на 3 равных, знать эти адреса, указать ширину курсора(3х3) и вуаля есть все нужные адреса, если надо записать в центр 1/3 есть memcpy блочный
а что не так, человек пишет про последовательность байт, эту последовательность при получении надо поделить на 3 равных
Какой человек? Откуда взялось число 3?
ну семпл это же мерная величина измеряется в байтах
потомучто в 1 проход дороже чем по трём полосам на своих адресах
в 1 полосе 1 адрес и величина блока больше на 1/3, если поделить 1 большой на 3 равных по семплам выравнивая это будет логичнее, тогда надо позаботиться чтобы на входе было равное поступление семплов за такт или отрезок времени
Хорошо, семпл измеряется в байтах. Вообще все в компьютере в байтах представлено. Но при чем тут это, чем это помогает в поиске медианы?
Какой человек писал:
человек пишет про последовательность байт, эту последовательность при получении надо поделить на 3 равных
Откуда взялось 3, почему равные части?
Вы опять выдали какую-то свою мысль никак ее не привязав к упомянутому раньше и я опять не понял, что вы хотели сказать.
ну МФ в последовательности семплов так? последовательность семплов это и строка семплов, а значит если настроить равное поступление семплов например на 1/3 больше или просто чтобы равное поступало поделив например на 3, и распределив эти куски на свои адреса алгоритм попросторнее, пошустрее будет работать, это как со строками, вы же не работаете с 1 строкой на 3килобайта(аски например) я надеюсь, обычно нет и первая оптимизация в работе со строками, иметь на каждую строку свой адрес
а в сумме они могут достигнуть 3килобайта например, а курсор в этом контексте ходит по 1 символу и строке
ну МФ в последовательности семплов так?
Пока да.
а значит если настроить равное поступление семплов например на 1/3 больше или просто чтобы равное поступало поделив например на 3,
А тут я вас потерял. Что за "поступление" семплов? Поэтому неясно, как оно может быть равным и на 1/3 больше, ведь я не знаю, что за поступление.
всё зависит от того как вы читаете поток предположу что он состоит из семплов
в любом случае поступает адрес согласны и длинна?
вот я выше пишу что надо прочитать из 1 адреса в трёх адресное равномерное пространство, а писать как будто была бы последовательность этих трёх адресов
123456789
fn(+1) 123
456
789
2345678910поидее же 1 итерация 3 вычисления и запись уже по знакомому адресу
из вики пример 1
x = [2 50 6 3]
--
init
*x1 [2 2 50] y[0]
*x2 [2 50 6] y[1]
*x3 [50 6 3] y[2]
*x4 [6 3 3 ] y[3]
calculate
for int=0;i<1
fn(*x1) y[i]
fn(*x2) y[i+1]
fn(*x3) y[i+2]
fn(*x4) y[i+3]Все еще ничего не понятно. Вы так и не остановились и не выдали никаких связей по шагам. Вы продолжаете развивать свою гениальную мысль, но оно вообще далека от понимания.
в любом случае поступает адрес согласны и длинна?
Куда поступает? На вход программе решающей задачу? Поступает одномерный массив и число W - размер окна. Можно считать что массив это адрес да. Если вы это имелли ввиду адресом и длиной, то да. Если нет, то разъясните.
ну и получается ждём завершение всех потоков и читаем по 1024
в результате будет выход с медианами
прям как в курле, есть пример на просторах интернета
а вы хотите по очереди выполнять?
Я заканчиваю эту ветку. Не буду дальше разбираться - надоело. Вы каждый раз вместо того чтобы разъяснить вашу прошлую мысль и ответить на мои вопросы выдаете что-то новое и не понятное.
значит надо разобраться возможно дерево это проигрыш, есть источники как работать с последовательностями на С, почему 1 большой поток это тяжелее чем что-то поделённое и почему это легко запустить через пул потоков например
можно в разные адреса загнать, можно на пул потоков(по 4 потока) и есть TimSort там косвенно об этом же
извините я тоже перестану
Вот тут проблема. А как найти это место?
Обычно фильтры применяются к значениям которые плавно меняются. По этому мы можем взять последний добавленный элемент и сравнить новое значение с ним. Далее используя связи на следующий и предыдущий элемент последовательно сравнивая каждый элемент, перемещая указатель в нужном направлении, найти нужное место. В лучшем случае это будет О(1), в худшем случае это будет О(размера окна).
Если вы применяете фильтры, то значения уже зашумленные. Они могут чуть-чуть колебаться в окресности истинного гладкого значения, но при этом идти в полную перемешку, а значит новый элемент может попасть в любое место в отсортированном списке. Вот это самое "В лучшем случае это будет О(1)" - это на практике будет весьма редкая вещь.
Если последовательность монотонно растёт, то мы постоянно добавляем в левую кучу новые элементы (на вершину), а старые помечаем как выбывшие. Но они никогда не окажутся наверху кучи, и поэтому никогда не будут удалены. В результате у нас разрастается и куча, и мусорная корзина. И мы получаем и утечку, и логарифм от маляра Шлемюэля.
Или нет?
От логарифма на каждом шаге мы никак не избавимся, потому что heappush. Мы хотели бы избавиться от n или даже nlogn при удалении произвольного элемента из кучи.
Но давайте-ка сделаем совсем по-другому.
Пусть у нас есть упорядоченный контейнер с логарифмическим поиском-удалением-вставкой. То есть, любое ДДП (хоть АВЛ, хоть КЧД, неважно). И пусть у этого контейнера есть двунаправленные итераторы! Да-да, std::map.
И вот пусть мы знаем не только значение медианного элемента (или пары смежных), но и итератор на медианный элемент.
Теперь, добавляем новое значение в мап. Пусть мап сам занимается своей балансировкой, нам пофигу. Но мы ведь и понимаем, добавили в левое или правое крыло относительно значения медианы. Поэтому сдвигаем итератор медианы в нужную сторону, и это амортизированная O(1).
А потом удаляем старое значение из мапа. И мы также понимаем, из левого или правого крыла. И опять сдвигаем итератор.
Добавление в мап итак будет O(log n). Так что экономия на сдвигании итератора на общую сложность алгоритма не влияет. Тем более, что сдвигание итератора будет O(log n) в худшем случае: не хранят в деревьях указатели на следующий элемент обычно, ибо требования на константность в среднем. Это пройтись по всему дереву будет O(n) и поэтому каждая итерация O(1) в среднем. Но некоторые из итераций могут быть и o(log n) шагов. И можно так вставлять в дерево элементы что этот сдвиг итератора туда-сюда будет каждый раз будет o(log n) шагов.
Конечно, вы можете свое дерево написать с указателями вперед-назад, но все-равно остается добавление и общая сложность алгоритма остается O(n log n). И на поддержку этих указателей вы кучу памяти и вычислений потратите, так что возможно реализация с двумя простыми std::set для левой и правой доли окажется быстрее. set можно использовать вместо кучи, ибо там уже удаление есть встроенное.
там массивы должны быть
вы пишите число входных данных и размер окна, тогда в окне на каждое число создаётся адрес или поток, далее timsort и вставка в выходной, меньше действий чем с деревом
кароче задача МФ это комплексная адресуемая операция все адреса известны изначально, всё будет зависить от сортировки и размера окна
по всей видимости это второй способ
Скрытый текст
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define DATA_SIZE 1024
#define NUM_THREADS 4
#define WINDOW_SIZE 256
// Исходные данные
double data[DATA_SIZE*3];
// Обработанные данные
double result[DATA_SIZE*3];
// Структура для передачи данных в поток
typedef struct {
int start_idx;
int end_idx;
double *data;
double *result;
} thread_data_t;
// Функция для обработки части данных
void *process_chunk(void *arg) {
thread_data_t *td = (thread_data_t *)arg;
int start = td->start_idx;
int end = td->end_idx;
double *data = td->data;
double *result = td->result;
for (int i = start; i < end; i++) {
int window_start = (i - WINDOW_SIZE / 2) < start ? start : (i - WINDOW_SIZE / 2);
int window_end = (i + WINDOW_SIZE / 2) >= end ? end - 1 : (i + WINDOW_SIZE / 2);
// Пример: медиана в окне
int window_len = window_end - window_start + 1;
double window[WINDOW_SIZE];
//тут с окном
// Сортируем окно (простейшая сортировка)
//тут сортировка
// Берем медиану
double median;
if (window_len % 2 == 1) {
median = window[window_len / 2];
} else {
median = (window[window_len / 2 - 1] + window[window_len / 2]) / 2.0;
}
result[i] = median;
}
pthread_exit(NULL);
}
int main() {
// Инициализация данных (например, случайными)
for (int i = 0; i < DATA_SIZE*3; i+=4) {
data[i] = 2;
data[i+1] = 50;
data[i+2] = 6;
data[i+3] = 3;
}
pthread_t threads[NUM_THREADS*3];
thread_data_t thread_data[NUM_THREADS*3];
int chunk_size = (DATA_SIZE*3) / (NUM_THREADS*3);
// Создаем потоки
for (int i = 0; i < NUM_THREADS*3; i++) {
thread_data[i].start_idx = i * chunk_size;
if (i == (NUM_THREADS*3) - 1) {
thread_data[i].end_idx = DATA_SIZE*3; // последний поток идет до конца
} else {
thread_data[i].end_idx = (i + 1) * chunk_size;
}
thread_data[i].data = data;
thread_data[i].result = result;
pthread_create(&threads[i], NULL, process_chunk, &thread_data[i]);
}
// Ждем завершения потоков
for (int i = 0; i < NUM_THREADS*3; i++) {
pthread_join(threads[i], NULL);
}
// Теперь результат в массиве result
for (int i = 0; i < DATA_SIZE*3; i++) {
printf("%f\n", result[i]);
}
return 0;
}
Кажется, понял. Вы предлагаете каждое окно считать независимо и распараллелить вычисления. То, что это делается тривиально понятно примерно всем. Вам надо было не писать расплывчатые комментарии об адресации, а лишь сказать хоть один раз слова "параллельная обработка".
Этот способ в серъез никем не рассматривается, потому что для хоть сколько-нибудь больших окон O(w log w), даже деленное на количество потоков, оказывается сильно медленнее O(log w) при последовательной обработке окон и умном выборе структуры данных.
Плюс чаще задача с фильтрами на окнах выполняется онлайн - вам приходят числа по одному и надо сразу выдать сглаженное значение для последнего окна. Тут просто физически распараллелить нельзя.
тоесть вы хотите сказать поступает 1 число и ждёт ? метка начала конца, размер окна получается на момент сессии (на перфолентах тоже по 1 поступает наверно, но там есть метки и ширина)
сколько-нибудь больших окон это сколько 256 или сколько конкретно?
3 гига окно да? в очереди потоковых задач - это вроде 10к -задач по 12 потоков если окно 256, но тогда эти 3 гига(числовое обозначение разрядности не байты) сначала надо получить
если окно array[3гига] и если array[256] разные ситуации вроде
Ну вот приходят данные с датчика каждые 10мс. Вы будете ждать секунду прежде чем пакетно выдать данные за последнюю секунду? В системах реального времени надо сразу выдвать результат.
Вот если у вас 8 ядер в системе, то уже для окон размера около 8 параллельное решение будет хуже. В зависимости от реализации это может быть и 4 и 16 элементов, но порядок будет такой. Потому что решение в W раз медленее по сложности но выполняется в 8 потоков.
всё верно случай вообще интересный приходит сигнал так? допустим зашумленый, но он часть общего, смотрите пришла 1 - пошла лесенка вверх, пошла лесенка вниз, допустим у нас задача убрать лесенку или вниз или вверх, ладно буду разбираться )
Цель медианного фильтра - убрать выбросы, а не избавится от лесенок. Вот показывает у вас GPS координаты в москве, медленно двигающиеся на север. Потом одно значение приходит из америки, а следующие снова в москве на той же улице. Надо значение их америки проигнорировать и все еще показать движение на север в москве.
всё правильно дискретный сбор 1 окна или дискретное получение окна с размером?
тоесть что конкретно приходит входной массив с размером окна или окно и размер? или просто число приходит?
просто если зайти на литкод то там задача тривиальная, а вот конкретность может быть другой, и задачку-то понятно как решать на С посмотрев вики например,
псевдокод
окно размер
выделили новый размер
запустили цикл
вычислили сортировку
нашли медиану
записали результат
на С оно так же будет просто на С мы следим за выделением памяти самипросто может можно паралельно решать итерации 4 примерно, тоесть ходить по массиву если позволяет по 2-3-4 окна, за 1 итерацию цикла
тоесть можно подготовить такие условия что за 1 итерацию можно решить 4 окна не хешируя, само условие задачи и определение окна к этому подводит, даже пусть если я и ошибаюсь
тоесть если пришло 1 окно можно решить 1 окно, если пришло не 1 окно распределить итерации по 4 или до 4
в условии еще может быть тип сортировки под размер окон, например пришел массив и окно 1024 под неё хорошо допустим такая-то сортировка, и допустим если не будет выше 1024 то допустим ограничить при размере окна 1024 2мя итерациями за 1 итерацию цикла
мне почему-то так кажется, как железячно это вопрос тонкий наверно
выходная расчетная примерная по итерациям, допустим 30килобайт тут будет 15 итераций, а у вас сколько получается?
наподобии такого разве нельзя?
Скрытый текст
#include <iostream>
#include <vector>
#include <thread>
#include <numeric>
#include <algorithm>
std::vector<int> nums={1,3,-1,-3,5,3,6,7};
int k=3;
std::vector<int> nums1;
void worker(int start, int end,int j) {
int count=0;
std::vector<double> temp(nums.begin()+start,nums.begin()+end);
std::sort(temp.begin(), temp.end());
for (int i = start; i < end; ++i) {
// Работа в потоке
std::cout << "j "<<j<<" "<<nums[j+count] << " ";
count+=1;
}
std::cout << "\n";
// count=0;
}
int main() {
std::vector<std::thread> threads;
int num_threads = 6;
int chunk_size = 3;
int count=0;
for (int i = 0; i < num_threads; ++i) {
threads.emplace_back(worker, i * chunk_size, (i + 1) * chunk_size,i);
}
for (auto& t : threads) {
t.join(); // Дожидаемся завершения всех потоков
}
return 0;
}Вам надо написать класс/функцию, которой дается на вход одно число и она выдает медиану среди последних W переданных ей чисел.
а что делает автор если это начало? где там медиана? может что-то упущено в каком-то из описаний и у вас в коментариях?
тоесть 20 милисекунд по вашему коментарию прошло медианы нету (или она образовалась в размере окна которого нету получается), а вы пишите про 1 число только и нужно окно получается
да и по бенчмарку ничего не понятно вывод не читаемый
пример из вики не подходит получается и литкод тоже пообщавшись с вами я это понял
Если чисел не хватает, то можно выдавать или медиану из имеющегося меньшего количества, или вообще выдавать нефильтрованный вариант. Код автора использует первый вариант.
так же не хватает сравнений, с другими способами, наверно, если честно я даже не знаю как быть если окажется решение в лоб не хуже 2 куч при всех прочих, даже при ваших завышенных комментариях(GPS и прочее)
а если окно 10^9 такое может быть?
тут как я понимаю уже играет роль или память или скорость, ну тогда вопрос если окна размером 10^9 почему бы и не подождать? к раз наверное намёк, ну выполнится через 100мс или 1 секунду
а если окно 10^9 такое может быть?
Ваш способ будет в миллионы раз медленнее решения на двух кучах. При условии, конечно, что в компе хватит памяти это все засунуть.
Чем больше окно, тем хуже ваш метод по сравнению с кучами.
Еще раз, кучи выполняют LogW операций на каждый элемент массива, ваше решение - W log W, правда распараллеленные на P ядер.
Можно спорить, при каких кокретных значениях W ваше решение станет хуже. Будет ли это 4 или 16, или может быть даже все 20, если вы свое решение соптимизируете по максимуму. Вот тут без эксперимента и бенчмарков уже не сказать.
так надо чтобы приложение еще не висело в нагрузке постоянно то при работе в этом и прелесть мульти планировщика как я понимаю, например через epoll какой-нибудь может быть, это же дискретная обработка получается, у меня вот емакс на фрибсд не всегда висит на верху top если смотреть, но время постоянно отмеряется, и точно так же я настроил свой редактор текста(у меня редактор текста на кучах простых - не бинарных, я к тому, что если я уберу мульти проброс нагрузка будет существенна от введенного текста и рендеринга!, может это epoll+евенты, но радует, что настроить можно и снять нагрузку), у емакса например при активности только видно нагрузку текущую и не на 1 ядре(тоесть будет меняться ядро), емакс тоже на кучах ведь, java уж точно
кстати еще есть асинхронность в С aio.h может с ней еще можно считать медиану
тоесть читать пока пишешь наверно
кстати еще есть дерево с pickbest при insertion тогда на листьях будут только значения, а в корне индексы
ErinCatto_DynamicBVH_Full.pdf сдесь расписано
тогда получается не нужно 2 кучи нагрузка будет при вставке как я понимаю
получается это динамическое дерево с выбором лучшего при вставке с поддерживающим балансирующим механизмом и вообщем по её механике она ближе к окну, потомучто там есть настройка конкретно окна, соответственно можно как-то подумать как при вставке по упору в окно удалить первое, чтобы последнее было последним соскользить типо
Ну кстати да. Раз уж у нас добавление в кучу логарифмическое, то возьмём вместо двух куч два ДДП.
Единственная выгода двоичной кучи - в том, что она эффективно размещается на массиве, тогда как set требует динамическую память.
Ну ок, возьмём std::set с пользовательским аллокатором, разместим на массиве (правда, впятеро большего размера: в каждом узле, помимо значения, ещё три указателя и флажок балансировки).
Нет, бинарное дерево поиска не разместить вот также в массиве. Вернее, в массив-то элементы засунуть можно, но дети не будут иметь номера 2i и 2i+1. Ибо дерево поиска может быть не таким же ровным как куча. Где-то нет одного ребенка в середине - и вся нумерация сбилась. Даже без нарушения баланса.
Единственная выгода двоичной кучи - в том, что она эффективно размещается на массиве
Не только. Она еще эффективнее, в смысле там константа меньше. Обычно, чем хирее структура, тем меньше у нее ассимптотика, но тем больше константа. Эти всякие вращения для балансировки - гораздо больше действий, чем поменять отца с ребенком.
https://godbolt.org/z/7Mo53qnzn а так не подходит?
вообще надо наверное, дерево где индексы вначале в узлах, по индексам мы строим баланс дерево при вставке, и по индексам как по пути приходим в поиск в дереве (проход до ктого елемента наверное), потомучто альтернатива сортировке это quickselect+kth, но минус что дерево перестроить придётся(ребилд типо, но работает красиво)(поиск приравняется к ray-задачкам с деревьями)
1
2 3
4 5 6 7
а b c d e f 8 9
g 10 j k
h i
ну типо это с какого-то момента наверно не по cost дерево, я в деревьях не силён, но наверняка cost отработал бы и оно бы сбалансировалось бы наверное
тоесть взависимости от размера окна, имеем 2 поддерева медиан и они циркулируют заменяют друг друга может еще(ну это фантазия чисто)
вообще хорошо бы иметь универсальное динамическое дерево
Скрытый текст
+------------------------------------------------------------+
| Tree |
| |
| +----------------+ +----------------+ |
| | Build Module | | Search Module | |
| | (SAH, pickBest)| | (Range, Nearest)| |
| +----------------+ +----------------+ |
| |
| +------------------------------------------------------+ |
| | Nodes (hierarchy) | |
| | | |
| | +--------+ +--------+ +--------+ | |
| | | Node 1 | | Node 2 | | Node 3 | | |
| | | (AABB) | | (AABB) | | (AABB) | | |
| | +--------+ +--------+ +--------+ | |
| | / \ / \ / \ | |
| | / \ / \ / \ | |
| | Leaf / Internal Leaf / Internal Leaf / Internal | |
| | (Objects) (Objects) (Objects) | |
| +------------------------------------------------------+ |
| |
| +------------------------------------------------------+ |
| | Object Pool / Storage | |
| | (Objects with indices, positions, groups, etc.) | |
| +------------------------------------------------------+ |
| |
| +------------------------------------------------------+ |
| | Auxiliary Data | |
| | - Rotation nodes | |
| | - Group info | |
| | - Metadata for pickBest / SAH | |
| +------------------------------------------------------+ |
+------------------------------------------------------------+Можно. Я об этом выше писал:
в сбалансированных деревьях можно найти элемент по его номеру. Правда, для этого надо хранить в каждой вершине размер поддерева
так хитрость то в этом, но если так балансировать по комплекции памяти много выходит ради 15 елементов,
// 1
// 2 3
// 4 5 6 7
// 8 9 10 11 12 13 14 15
// a b c d e f g h i k l 0 0 0 0 0
//
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i k l 0 0 0 0 0
//
//
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15или по левелу идти там очередь вон статей полно на эту тему, стек или очередь, проблема в том что храним данные как есть, если бы это была векторная репрезентация было бы быстрее, векторная репрезентация это язык засечек типо(тоесть encode/decode засечек)
можно догодаться до такого, когда например надо рисовать столбики текста где каждая строка имеет в конце \n, тогда можно переходить на векторное преобразование по засечкам и это быстрее вроде работает(пример тоесть в выбранных зараннее столбиках текста от ls например нам не важны данные, а важны метаданные, тоесть начало и конец каждой строки как pos-число, а что там, это уже на плечах ls типо)
и вот квикселект делает эти засечки получается
Нет, ДДП можно разместить в массиве. Но это будет массив не только со значениями, но и со всей служебной информацией. В отличие от кучи, чья структура прибита гвоздями, и индексы дочерних и родительского элемента вычисляются.
Поскольку размер дерева фиксированный, то и память под узлы можно выделить один раз. И вместо указателей пользоваться индексами. И вообще, вместо строчного представления взять столбцовое: отдельно массив значений, отдельно массивы индексов, отдельно массив флажков балансировки.
Да, разменяли время на память. Но - разменяли ли? С одной стороны - куча и мусорная корзина (хеш-таблица, которая тоже хранит значения плюс свою служебную информацию), а с другой - просто дерево, которое сразу хранит служебную информацию, зато не дублирует значения.
Кстати, не set, а multiset... Или же map счётчиков.
Нет, ДДП можно разместить в массиве. Но это будет массив не только со значениями, но и со всей служебной информацией.
Это то, что я и написал:
Вернее, в массив-то элементы засунуть можно, но дети не будут иметь номера 2i и 2i+1.
Что касаемо остальных ваших аргументов, я их уже разобрал. Дело не только в памяти, но и в меньшем количестве операций, нужным куче для работы.
Не понял. Если кучи равного размера, но часть элементов в кучах на самом деле "отложенно удалены", то получается, алгоритм вовсе не медиану поддерживает? Потому что отложенно удаленных элементов в одной куче может быть больше, чем во второй.
Медианный фильтр на двух бинарных кучах