Easyelectronics.ru

Электроника для всех
Текущее время: 24 апр 2018, 02:19

Часовой пояс: UTC + 5 часов



    • JLCPCB - Платы прототипов всего за 2$ c бесплатной доставкой (при первом заказе)
    • 10 PCBs за $2 для 2 слоев, $15 для 4 слойной, $74 для 6 слойной платы.
    • Крупнейший китайский производитель прототипных плат. 290000+ клиентов & 8000+ заказов в день!
    • LCSC - Крупнейший китайский онлайн магазин радиодеталей.

Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 17:24 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
Доброго времени суток,

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 17:47 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 538
Откуда: GMT+6
CheMax писал(а):
2. производим сортировку;
По какому параметру?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 17:50 
Старожил

Зарегистрирован: 24 июн 2011, 14:05
Сообщения: 286
Откуда: Новочеркасск
После сортировки в вас грубо говоря "каша" от первоначального варианта записанного в массив, вариант только хранить индекс самой старой точки где-то или есть еще какие то доп. условия о которых не озвучено.
Kelvin вроде написано что по возрастанию.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 17:55 
Старожил
Аватара пользователя

Зарегистрирован: 11 авг 2016, 20:52
Сообщения: 538
Откуда: GMT+6
По возрастанию - это направление сортировки, а я спрашиваю, его сортировать надо по "старости" или по иному критерию?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 18:02 
Старожил

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 18:09 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
ELEKTROS писал(а):
После сортировки в вас грубо говоря "каша" от первоначального варианта записанного в массив, вариант только хранить индекс самой старой точки где-то или есть еще какие то доп. условия о которых не озвучено.
Kelvin вроде написано что по возрастанию.



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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 18:11 
Старожил

Зарегистрирован: 23 янв 2016, 15:37
Сообщения: 476
| 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 | <- упорядоченный массив


Последний раз редактировалось Reflector 20 сен 2017, 20:19, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 18:26 
Старожил
Аватара пользователя

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


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

для примера:

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 18:48 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 4200
Сортировать зачем? Медианный фильтр?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 19:32 
Заглядывает иногда

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

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

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


Последний раз редактировалось Арсений 20 сен 2017, 20:18, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 20 сен 2017, 19:58 
Старожил

Зарегистрирован: 10 июн 2011, 23:01
Сообщения: 2863
CheMax писал(а):
_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 равным размеру массива.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 11:48 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
u37 писал(а):
Сортировать зачем? Медианный фильтр?


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 11:56 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
_pv писал(а):
...


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 12:08 
Старожил

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 12:39 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
aamonster,
вот уж спасибо).

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

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

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

спасибо!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 14:37 
Старожил
Аватара пользователя

Зарегистрирован: 06 ноя 2013, 16:07
Сообщения: 524
Откуда: Германия
А тут сколько тактов?
Show код

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 14:47 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
dev писал(а):
А тут сколько тактов?
....


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

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


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 14:57 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 1474
CheMax писал(а):
добавлять новую точку вместо "самой старой". ?

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

Арсений писал(а):
... при пересортировке нужно ....

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 18:30 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
BusMaster,

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 21 сен 2017, 21:56 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2409
Откуда: Санкт-Петербург
CheMax, навскидку на 7 элементах массив порвёт список, так что есть шанс сделать быстрее 292 тактов. Особенно - если развернуть цикл.
Хотя если 292-299 приемлемо - лучше оставить как есть.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 22 сен 2017, 10:16 
Старожил
Аватара пользователя

Зарегистрирован: 06 ноя 2013, 16:07
Сообщения: 524
Откуда: Германия
Тут еще тонкий момент есть - иногда надо максимизировать среднюю скорость, а иногда - худшую.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 22 сен 2017, 12:20 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
вот только 7 элементов это только для примера, скорее для оценки даже. Существует вероятность, что окно может быть увеличено, опять же 9, 11, 13 ... кто его знает, как оно себя поведет. Тут внешних факторов хватает, поэтому и ищется наиболее быстрый алгоритм.

что касается средней скорости\худшей скорости, пока не знаю. за время тестирования лучший результат 291 такт, худший 298 такт. что одно, что другое устраивает полностью (гонял алгоритм около часа на случайных значениях от RNG модуля. естественно время генерации не участвовало в тесте). Скорость оценивал через DWT модуль.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 22 сен 2017, 13:08 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2409
Откуда: Санкт-Петербург
CheMax, попробуйте не только на случайных числах, но и на монотонно возрастающих/убывающих (один из крайних случаев, на которых некоторые сортировки лажают). Но вроде особых проблем быть не должно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 22 сен 2017, 13:17 
Старожил
Аватара пользователя

Зарегистрирован: 01 авг 2016, 10:47
Сообщения: 209
Откуда: Таганрог
aamonster, так же проходил эту проверку на счетчике. результат тот же)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Сортировка и скользящее окно
СообщениеДобавлено: 26 сен 2017, 11:03 
Старожил

Зарегистрирован: 17 дек 2014, 04:38
Сообщения: 394
Посмотрите, может подойдет
Код:
#include <stdio.h>
#define MASLEN   10

typedef struct myset {
   struct myset *prev;
   int i;
   struct myset *next;
} TypeSet;

TypeSet mass[MASLEN];
int inx,count;

void init() {
   inx = 0; count = 0;
   for (int i = 0;i<MASLEN;i++) {
      mass[i].i = 0;
      mass[i].prev = NULL;
      mass[i].next = NULL;
   }
}
TypeSet *getEl(int el) {
   return(&mass[el]);
}
void cmpEl(TypeSet *el1, TypeSet *el2) {
   TypeSet *tel;

   if (el1->i > el2->i) {
      if (!el1->prev) {
         el1->prev = el2;
      } else {
      tel = el1->prev;
      if (tel->i < el2->i) el1->prev = el2;
      }
   } else {
      if (!el1->next) {
         el1->next = el2;
      } else {
      tel = el1->next;
      if (tel->i >= el2->i) el1->next = el2;
      }
   }
}
void addEl(int el) {
   TypeSet *ts;
   int tc,ti;

   mass[inx].i = el;
   tc = count;ti = inx;
   while(tc--) {
      ti--;
      if (ti < 0) ti += MASLEN;
      ts = getEl(ti);
      cmpEl(&mass[inx],ts);
   }
   if (mass[inx].prev) {ts = mass[inx].prev; ts->next = &mass[inx];}
   if (mass[inx].next) {ts = mass[inx].next; ts->prev = &mass[inx];}
   inx = (inx<(MASLEN-1))?inx+1:0;
   if (count < MASLEN) count++;
}
TypeSet *findFirst() {
   for (int i = 0; i<MASLEN; i++) {
      if (!mass[i].prev) return(&mass[i]);
   }
   return(NULL);
}
int main() {
TypeSet *ts;

   addEl(5);
   addEl(2);
   addEl(15);
   addEl(3);
   addEl(12);
   addEl(8);
   addEl(9);
   addEl(3);
   ts = findFirst();
   do {
      printf("%d\n",ts->i);
      ts = ts->next;
   }while(ts);

   return(0);
}


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB