Сортировка и скользящее окно

Доброго времени суток,

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

Т.е. хотелка выглядит так:

определяем размер массива методом пол-палец-потолок, например равный 7.

1. добавляем новую точку в массив (если массив заполнен - пишем точку вместо самой старой);
2. производим сортировку;
3. вернуться на пункт 1;

сложность заключается именно в поиске самой старой точки. Размер массива небольшой, например 7 элементов. Кто-нибудь реализовывал подобное или встречал подобный алгоритм?

0

Сообщение от ShiMox 2. производим сортировку;

По какому параметру?

0

После сортировки в вас грубо говоря "каша" от первоначального варианта записанного в массив, вариант только хранить индекс самой старой точки где-то или есть еще какие то доп. условия о которых не озвучено.
Kitvym вроде написано что по возрастанию.

0

По возрастанию - это направление сортировки, а я спрашиваю, его сортировать надо по "старости" или по иному критерию?

0

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

0

Сообщение от ITIKTROS После сортировки в вас грубо говоря "каша" от первоначального варианта записанного в массив, вариант только хранить индекс самой старой точки где-то или есть еще какие то доп. условия о которых не озвучено. Kitvym вроде написано что по возрастанию.

доп. условий в отличии от банка нет)

индекс по сортированному массиву? а как её тогда искать? получается помнить надо значение, искать его, определять индекс?

0

| 11 | 42 | 10 | 59 | 15 | <- исходный массив
| p2 | p0 | p4 | p1 | p3 | <- упорядоченный массив

Удаляем 11, т.е. первый элемент из первого массива и указатель p0 на него, из второго.
Добавляем 25 в конец первого массива и указатель p5 на него в соответствующую позицию второго.

| X | 42 | 10 | 59 | 15 | 25 | <- исходный массив (т.к. у нас круговой буфер, то все элементы остались на своих местах)
| p2 | p4 | p5 | p1 | p3 | <- упорядоченный массив

0

Сообщение от _pv массив отсортирован по возрастанию, а второй массив с индексами первого - по старости (тупо кольцевой буфер куда добавляется индекс очередного элемента) можно наоборот, данные хранить в тупо кольцевом буфере, а в отсортированном виде хранить индексы.

не совсем понял,
можно наглядный пример?

для примера:

| 11 | 42 | 10 | 59 | 15 | <- исходный массив
| 01 | 02 | 03 | 04 | 05 | <- индексы исходного массива

| 10 | 11 | 15 | 42 | 59 | <- упорядоченный массив
| 03 | 01 | 05 | 02 | 04 | <- индексы исходного массива

теперь, как мне добавить новую точку? в исходном массиве понятно что надо перетереть точку с индексом 1. а в сортированном?

0

Сортировать зачем? Медианный фильтр?

0

А если так:
array[] - наш массив.
Перед сортировкой копируем массив в array_copy[]. Запоминаем порядковый номер самого старого элемента в переменную pos. Сортируем массив array[].

Пришла пора заменить самый старый элемент - находим самый старый элемент (array_copy[pos]). Ищем элемент со значением array_copy[pos] в массиве array[] бинарным древом. Если размер массива небольшой и заранее известный - ищем при помощи жестко прописанного древа if/else. Заменяем значения в элементе соответствующем элементе array[] и в array_copy[pos]. Инкрементируем pos.

Потом еще и место, куда при пересортировке нужно вставить новый элемент можно найти тем же бинарным древом.

0

Сообщение от ShiMox Сообщение от _pv массив отсортирован по возрастанию, а второй массив с индексами первого - по старости (тупо кольцевой буфер куда добавляется индекс очередного элемента) можно наоборот, данные хранить в тупо кольцевом буфере, а в отсортированном виде хранить индексы.

не совсем понял,
можно наглядный пример?

| 11 | 42 | 10 | 59 | 15 | <- исходный массив

| 10 | 11 | 15 | 42 | 59 | <- упорядоченный массив
| 02 | 04 | 01 | 05 | 03 | <- индексы по времени добавления (первый - 11==[2], второй 42==[4],...)

при добавлении очередного элемента пусть будет 45, сначала удаляется элемент с индексом 02 (11) -первый по списку, а все индексы что выше уменьшаются на 1, раз элемент удалили

| 10 | 15 | 42 | 59 | <- упорядоченный массив
| 03 | 01 | 04 | 02 | <- индексы массива отсортированные по времени добавления

а затем надо 45 поставить на нужное место, в конец добавить его индекс, а все индексы что >= увеличить на один раз элемент вставили

| 10 | 15 | 42 | 45 | 59 | <- упорядоченный массив
| 03 | 01 | 05 | 02 | 04 | <- индексы исходного массива отсортированные по времени добавления

следущий кандидат по списку на удаление - 42 под индексом [3]

но вместо того чтобы бегать два раза по массиву с индексами и инкрементировать/декрементировать их при вставке/удалении можно наверное просто сделать массив из структур

struct{
int value;
int ttl;
}

сортировать его по value, а при удалении элемента тупо проходить по всему массиву, уменьшать ttl на 1 и удалять элемент c ttl = 0.
а при добавлении добавлять его всегда с ttl равным размеру массива.

0

Сообщение от u37 Сортировать зачем? Медианный фильтр?

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

0

Сообщение от _pv ...

Это надо обдумать и попробовать, спасибо

0

Так и ищите быструю реализацию медианного фильтра, а не сортировки.
Это разные задачи: сортировка массива требует O(n*log(n)) операций, а поиск медианы - всего O(n).

Ну и плюс для столь короткого окна быстрая реализация вообще будет специфической. Опять же ищите готовую.

Ну а "на тяп-ляп" - для окна длиной 7 нетрудно поддерживать отсортированный массив. За один проход по массиву из него удаляется одно число и добавляется одно (кусок между этими двумя числами сдвигается на 1 позицию)

0

oomomstir,
вот уж спасибо).

своеобразное проявление закона Мерфи: если есть два пути, обязательно будет выбран долгий.

поиск по быстрым алгоритмам медианного фильтра вывел на описание алгоритма, описанного Филом Экстромом.
взяв от сюда: http://chipenable.ru/index.php/item/203 ... filtr.html код, получил следующий результат:
мк: L471
Fclk = 12,288 МГц
формат данных на входе uint64_t
окно для примера взял 7
количество тактов 292 - 299(!)

против 1200-1250 тактов при стандартной реализации.

спасибо!

0

А тут сколько тактов?
кодну и uint64_t жирноват для этой задачи, на первый взгляд.

ПыСы: не тестировал

0

Сообщение от div А тут сколько тактов? ....

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

Сообщение от div ну и uint64_t жирноват для этой задачи, на первый взгляд. ПыСы: не тестировал

данные идут в таком формате, если уж совсем интересно то это метка времени.

0

Сообщение от ShiMox добавлять новую точку вместо "самой старой". ?

Вопрос: что есть "старая точка", "новая точка"? По времени, то есть по наименьшему (наибольшему) индексу, при условии что пишется в массив от 0 до икс-икс? В этому случае "самой старой" будет индекс 0.
Индексы оставляйте теми же самыми, элементы никуда не сдвигайте, пишите по кольцу. Упорядочивайте только указатели на элементы. Вы должны иметь массив указателей на элементы массива, и работайте только с указателями. Причем, на время этой работы запрещайте запись в массив (можно заполнять приемный буфер, если прием остановить нельзя).
Не делайте так, как советуют писюковые погромисты, то есть не надо никуда дергать элементы массива, оставьте всё на своих местах, иначе потом вы хрен найдете изначальный порядок записи элементов и не сможете добавить новый в правильное место. Используйте кольцевой буфер, а сортируйте только массив указателей на каждый элемент.

Сообщение от Ирсений ... при пересортировке нужно ....

Арсюша, слухай, не суйся сюда со своим свопом HDD, а. Иди задай вопрос "А што такое кольцевой буфер - это сахар или соль?" Епт...

0

BusMostir,

спасибо за совет, буду посмотреть.

тот вариант что я нашел в сети использует связанные списки для сортировки и выдачи медианы. работает по добавлению нового элемента, и быстро (выше писал что немного меньше 300 тактов CPU). Пока что буду пытаться понять ту реализацию, ибо давно смотрел в сторону списков, но не знал для чего их применить можно. Опыта и знаний Си маловато все же, или скорее понимания что в какой ситуации применить.

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

0

ShiMox, навскидку на 7 элементах массив порвёт список, так что есть шанс сделать быстрее 292 тактов. Особенно - если развернуть цикл.
Хотя если 292-299 приемлемо - лучше оставить как есть.

0