Форум программистов, компьютерный форум, киберфорум
Микроконтроллеры
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.61/33: Рейтинг темы: голосов - 33, средняя оценка - 4.61
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173

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

19.09.2017, 16:37. Показов 7129. Ответов 36
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток,

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

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

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

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

сложность заключается именно в поиске самой старой точки. Размер массива небольшой, например 7 элементов. Кто-нибудь реализовывал подобное или встречал подобный алгоритм?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
19.09.2017, 16:37
Ответы с готовыми решениями:

Скользящее окно в Vivado HLS
Всем привет. Работаю на win7_64bit, Vivado HLS 2016.2. Написал простейшее скользящее окно, по ресурсам все должно занимать 10BRAM, а...

Скользящее окно Mathcad
Коллеги, добрый день! срочно требуется Ваша помощь: считаем среднеквад отклонение. сейчас оно посчитано для одного конкретного...

Создать скользящее окно для вектора значений
Имеется вектор случайных значений распределенных по нормальному закону, нужно создать скользящее окно размером в 60 значений, и для каждого...

36
0 / 0 / 0
Регистрация: 26.01.2009
Сообщений: 3
21.09.2017, 09:29
Студворк — интернет-сервис помощи студентам
Тут еще тонкий момент есть - иногда надо максимизировать среднюю скорость, а иногда - худшую.
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
21.09.2017, 11:33
вот только 7 элементов это только для примера, скорее для оценки даже. Существует вероятность, что окно может быть увеличено, опять же 9, 11, 13 ... кто его знает, как оно себя поведет. Тут внешних факторов хватает, поэтому и ищется наиболее быстрый алгоритм.

что касается средней скорости\худшей скорости, пока не знаю. за время тестирования лучший результат 291 такт, худший 298 такт. что одно, что другое устраивает полностью (гонял алгоритм около часа на случайных значениях от RNG модуля. естественно время генерации не участвовало в тесте). Скорость оценивал через DWT модуль.
0
0 / 0 / 0
Регистрация: 06.12.2016
Сообщений: 1,864
21.09.2017, 12:21
ShiMox, попробуйте не только на случайных числах, но и на монотонно возрастающих/убывающих (один из крайних случаев, на которых некоторые сортировки лажают). Но вроде особых проблем быть не должно.
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
21.09.2017, 12:30
oomomstir, так же проходил эту проверку на счетчике. результат тот же)
0
1 / 1 / 0
Регистрация: 08.05.2015
Сообщений: 225
25.09.2017, 10:16
Посмотрите, может подойдет
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdyo.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 *fymdFirst() {
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 = fymdFirst();
do {
prymtf("%d\n",ts->i);
ts = ts->next;
}while(ts);
 
return(0);
}
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
25.09.2017, 12:05
voyd1509, что-то мне подсказывает, что данный алгоритм больше для ПК, нежели для МК.

понимаю, что можно адаптировать, но все же ...
0
1 / 1 / 0
Регистрация: 08.05.2015
Сообщений: 225
25.09.2017, 12:10
На МК он подойдет, но напильником допиливать придется :)
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
25.09.2017, 13:19
ну так и ПК с помощью напильника можно до состояния МК сточить)))

попробую, но немного позже
0
0 / 0 / 0
Регистрация: 06.12.2016
Сообщений: 3,113
25.09.2017, 13:34
Мне медиана не понравилась - теряется усреднение по отсчетам. Я сделал усреднение С удалением N экстремумов. Т.е. N-проходовый алгоритм, на каждом проходе считается среднее и ищется мин и макс. На следующем проходе самое большое число (модуль дельты от среднего) удаляется из списка (точнее игнорируется в расчёте). Настройками легко адаптировать алгоритм на импульсные помехи. При этом мало портится усреднение.
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
25.09.2017, 14:38
так у медианы и не стоит задача усреднения как-бы. её задача отсеять выпадающие точки, а средним пусть уже другие занимаются, да пусть хоть то же скользящее среднее.
0
0 / 0 / 0
Регистрация: 06.12.2016
Сообщений: 3,113
25.09.2017, 14:58
Усреднение снижает шум и повышает точность. Медиана - нет. Она только убирает "не типичные" значения. Чем больше размер окна, тем существеннее разница между алгоритмами. IMHO.
Впрочем, это ваше дело. ))
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
25.09.2017, 15:06
так у меня и стоит задача убрать нетипичные, выпадающие, значения. ибо при 64 битах на входе, можно поиметь ой какую разницу между соседними точками)))

по поводу шума, знаем, боремся всеми доступными средствами
0
0 / 0 / 0
Регистрация: 06.12.2016
Сообщений: 382
25.09.2017, 15:16
64 бита? То есть?? Как это?
32 бита - это 192 дБ диапазона. В таком диапазоне не работает ни один физический преобразователь. А при 64 битах - младшие 40 бит - шумы. Иль у вас космические технологии в разработке?

С шумами фильтр Калмана работает хорошо.
0
0 / 0 / 0
Регистрация: 06.12.2016
Сообщений: 1,864
25.09.2017, 15:25
u37, N-проходовый?! 8-O
Поддержание отсортированного массива/списка требует одного прохода на новую точку. А на отсортированном массиве ваш метод делается за один проход (идти с двух концов массива). А для больших N вроде можно ещё оптимизировать.

BusMostir, Калман хорош (при заявленных для него условиях идеален :-)), но на одиночные выбросы, насколько я помню, не рассчитан. Да и предпосылок использовать тут именно его не видно (нет модели, по которой его строить).
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
25.09.2017, 17:22
что вас так пугает 64 бита? я ж вроде писал выше, что это метки времени. Думаю можно угадать, что формат за формат.

Медианный нужен, ибо поставщику этих меток говорим "Не верю!"

по поводу шумов и фильтрации с использованием Калмана:
можно ж поступить проще использовав такую формулу: y = y(n-1)*0.7 + y(n)*0.3; (!!! Коэффициенты взяты по технологии "пол-палец-потолок".!!!)

и шумы можно снизить, и усреднить так можно, и задержку в реакции на скачкообразное изменение.
0
0 / 0 / 0
Регистрация: 06.12.2016
Сообщений: 737
25.09.2017, 18:21
Цитата Сообщение от ShiMox
так у меня и стоит задача убрать нетипичные, выпадающие, значения. ибо при 64 битах на входе, можно поиметь ой какую разницу между соседними точками)))
У меня была такая проблема. При оцифровке, бывало, что точка (одна!) выпадала на хрензна какую величину, так что кривила усреднение.

Я боролся так. Каждую точку снимал трижды, потом сравнивал эти три величины между собой, самую отличающуюся выкидывал, а между двумя оставшимися брал среднее. И это считалась за снятое значение точки.
А потом уже в массив, и всё что там дальше надо...

Таким образом, выпадающие значения шли в мусор сразу, прежде всякой обработки.
0
0 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 173
26.09.2017, 11:30
запрос точки слишком много времени занимает, реальность времени теряется. поэтому и не могу запрашивать более одной точки за раз.

Про данный метод в первую очередь подумали, но увы
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
26.09.2017, 11:30
Помогаю со студенческими работами здесь

Скользящее среднее
Есть ДФ data, в нем стобец 'TotalCost'. Необходимо посчитать скользящее среднее за 7 дней по столбцу TotalCost. Я делаю так: #data =...

Скользящее среднее. Разновидности
Есть массив семплов звука. Применяю простую скользящую среднюю: #define SAMPLE_RATE (44100) #define FRAMES_PER_BUFFER (2048) #define...

Синтетическое скользящее среднее
Доброго времени суток. Прошу Вашей помощи в написании корректного алгоритма для данного вида средних. Есть алгоритм построения (он...

Среднее скользящее значение
Здравствуйте, не могу сообразить, как посчитать скользящее значение цены через запрос Допустим есть таблица: Есть средняя цена за...

Скользящее ДПФ (Герцель...)
Необходимо выделять первую гармонику из сигнала в реальном времени Пытаюсь реализовать скользащий алгоритм Герцеля. Немного не понятна...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru