В этом тексте вы узнаете зачем программистам микроконтроллеров нужна стабильная сортировка.
В программировании микроконтроллеров периодически приходится решать задачу о выявлении пересечения интервалов. Чаще всего это нужно при разработке загрузчиков и NVRAM, чтобы во время исполнения прошивки определять, что диапазоны памяти конфигов в самом деле пересекаются или не пересекаются.
Например Вы пишете загрузчик. Поступает команда прописать память от и до. Надо убедиться, что диапазон памяти самого загрузчика не пересекается с той памятью, которую надо изменить.
Второй пример. Вы хотите прописать массив в Flash память. Надо прежде всего проверить принадлежит ли вообще массив области Flash памяти. Если да, то начать писать. Если нет, то выдать ошибку.
Третий пример. Стандарт разработки ПО ISO-26262 требует перед применением конфига проверять его на валидность в run-time.
На первый взгляд простая задачка, однако, как оказалось, реализовать такое в коде - это вовсе нетривиальная задачка. Но обо всём по порядку...
Постановка задачи
Даны два непрерывных интервала:
номер интервала |
Начало |
Конец |
Имя интервала |
1 |
x1_start |
x1_end |
A |
2 |
x2_start |
x2_end |
B |
Определить:
1--пересекаются ли эти два интервала?
2--поглощает ли один интервал другой?
4--стыкуются ли эти два интервала
5--прочее
Тут же добавлю модульные тесты для процедуры проверки факта пересечения интервалов
# |
A |
B |
Пересекаются? |
комментарий |
1 |
[1 7] |
[5 9] |
1 |
нахлёст |
2 |
[1 9] |
[6 8] |
1 |
В внутри А |
3 |
[0 1] |
[1 2] |
0 |
соприкасаются |
4 |
[0 1] |
[2 3] |
0 |
|
5 |
[0 1] |
[1 1] |
1 |
точечный интервал с краю |
6 |
[7 7] |
[0 9] |
1 |
точечный интервал внутри |
7 |
[0 5] |
[5 9] |
0 |
соприкасаются |
В качестве X может быть всё, что только угодно: адреса физической памяти, время (time-stamp) отправки и прибытия автобусов, напряжение, диапазон радио частот. Словом всё, что обычно распределяется в виде диапазона величин.
Терминология
Непрерывные интервалы пересекаются, если существуют точки, которые присутствует в обоих интервалах.
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Название алгоритма |
Название алгоритма |
AVERAGE Performance |
insertion sort |
Сортировка вставками |
¼ n 2 |
bubble sort |
Сортировка пузырьком |
½ n 2 |
mergesort |
Сортировка слиянием |
n log2 n |
множество типа continuum - множество, где между двумя числами из множества всегда можно выбрать число, которое по середине.
Решение
Вы конечно можете применить аппарат линейной алгебры, представить интервалы в виде векторов, потом двигать вертикальный вектор Vy=(0; 1) и на каждом числе искать пересечение векторов. Однако это безумно много вычислений. Так не правильно.
Есть решение проще. Надо взять интервалы и представить их в другой форме записи.
Фаза 1: Превратить интервалы в массив точек
Мы представим векторы в виде последовательности точек. Образно выражаясь, расщепим интервалы на атомарные точки. Возьмём два интервала и составим из них массив точек. При этом каждая точка, как структура данных, будет обладать следующими тремя свойствами.
№ |
Название переменной |
возможные значения |
1 |
Координата Х |
целое число (-N, -1, 0, 1, +N) |
2 |
Тип скобки |
начало или конец интервала: [ или ] |
3 |
Номер самого интервала |
натуральное число (1 2 3 4 5) |
Получится массив структур из 4х точек.
Фаза 2: Сортировка
Выберем массив точек и выполним последовательно три стабильные сортировки. Порядок сортировок имеет тут ключевое значение.
# |
критерий сортировки |
компаратор |
1 |
по скобкам |
[ < ] |
2 |
по номеру интервала |
1<2 |
3 |
по координате X |
1<2 |
Тут нужна именно стабильная сортировка, чтобы очередная сортировка (по X) не испортила порядок с одинаковыми значениями x для предыдущей сортировки по типу скобки.
Фаза 3 Поиск пересечения
Вот у нас кристаллизовался трижды отсортированный массив. Главный порядок - это последняя сортировка по X.
Теперь надо завести переменную cross. Читаем точки массива с лева-направо -->. Если встретили открывающую скобку, то увеличиваем cross на +1 . Если встретили закрывающуюся скобку, то вычитаем -1 из cross. Таким образом, если во время обхода массива переменная cross принимает 2, то это значит, что тут интервалы начали пересекаться.
Просто и не затейлево.
Практическая часть
Итак, танцуем от печки... Точку представим в виде структуры данных IntervalPoints_t.
typedef enum {
INT_POINT_START = 1,
INT_POINT_END = 2,
INT_POINT_UNDEF = 0,
} IntervalPoint_t;
typedef struct {
uint32_t val;
uint32_t num;
IntervalPoint_t type;
} IntervalPoints_t;
typedef struct {
uint32_t start;
uint32_t end;
} IntervalE_t;
typedef struct {
uint32_t start;
uint32_t size;
} IntervalS_t;
Перед вами набор основных функций для обработки интервалов
Скрытый текст
#include "interval.h"
#include <stdlib.h>
#include <string.h>
#include "data_utils.h"
#include "log.h"
bool is_interval_e(const IntervalE_t* const Interval) {
bool res = false;
if(Interval->start < Interval->end) {
res = true;
}
return res;
}
bool IntervalConvert_e_s(const IntervalE_t* const in,
IntervalS_t* const out) {
bool res = false;
res = is_interval_e(in);
if(res) {
out->start = in->start;
out->size = in->end - in->start;
}
return res;
}
bool IntervalConvert_2_1(const IntervalS_t* const in,
IntervalE_t* const out) {
bool res = false;
if(in) {
if(out) {
out->start = in->start;
out->end = in->start + in->size;
}
}
return res;
}
static int comp_points(const void* elem1,
const void* elem2) {
if((((IntervalPoints_t*)elem2)->val) <
(((IntervalPoints_t*)elem1)->val))
return 1;
if((((IntervalPoints_t*)elem1)->val) <
(((IntervalPoints_t*)elem2)->val))
return -1;
return 0;
}
static int comp_num(const void* elem1,
const void* elem2) {
int ret = 0;
if((((IntervalPoints_t*)elem2)->num) <
(((IntervalPoints_t*)elem1)->num) )
ret = 1;
if((((IntervalPoints_t*)elem1)->num) <
(((IntervalPoints_t*)elem2)->num) )
ret = -1;
return ret;
}
static int comp_bracket(const void* elem1,
const void* elem2) {
int ret = 0;
if((((IntervalPoints_t*)elem2)->type) <
(((IntervalPoints_t*)elem1)->type) )
ret = 1;
if((((IntervalPoints_t*)elem1)->type) <
(((IntervalPoints_t*)elem2)->type) )
ret = -1;
return ret;
}
bool interval_intersect(const IntervalE_t* const A,
const IntervalE_t* const B) {
bool res = false;
IntervalPoints_t Point[4] = {0};
Point[0].val = A->start;
Point[0].type = INT_POINT_START;
Point[0].num = 1;
Point[1].val = A->end;
Point[1].type = INT_POINT_END;
Point[1].num = 1;
Point[2].val = B->start;
Point[2].type = INT_POINT_START;
Point[2].num = 2;
Point[3].val = B->end;
Point[3].type = INT_POINT_END;
Point[3].num = 2;
mergeSort(Point, ARRAY_SIZE(Point),
sizeof(IntervalPoints_t), comp_bracket);
mergeSort(Point, ARRAY_SIZE(Point),
sizeof(IntervalPoints_t), comp_num);
mergeSort(Point, ARRAY_SIZE(Point),
sizeof(IntervalPoints_t), comp_points);
uint32_t i = 0;
int32_t cnt = 0;
for(i = 0; i < ARRAY_SIZE(Point); i++) {
switch(Point[i].type) {
case INT_POINT_START:
cnt++;
break;
case INT_POINT_END:
cnt--;
break;
default:
break;
}
if(1 < cnt) {
res = true;
break;
}
}
return res;
}
А функция interval_intersect_continuum ищет ненулевые пересечения. В случае их нахождения возвращает true.
bool interval_intersect_continuum(const IntervalE_t* const A,
const IntervalE_t* const B) {
bool res = false;
bool spot_start = false;
bool spot_end = false;
IntervalE_t commom_e = {
.start = 0,
.end = 0,
};
IntervalPoints_t Point[4] = {0};
Point[0].val = A->start;
Point[0].type = INT_POINT_START;
Point[0].num = 1;
Point[1].val = A->end;
Point[1].type = INT_POINT_END;
Point[1].num = 1;
Point[2].val = B->start;
Point[2].type = INT_POINT_START;
Point[2].num = 2;
Point[3].val = B->end;
Point[3].type = INT_POINT_END;
Point[3].num = 2;
mergeSort(Point, ARRAY_SIZE(Point), sizeof(IntervalPoints_t), comp_bracket);
mergeSort(Point, ARRAY_SIZE(Point), sizeof(IntervalPoints_t), comp_num);
mergeSort(Point, ARRAY_SIZE(Point), sizeof(IntervalPoints_t), comp_points);
int32_t i = 0;
int32_t line_cnt = 0;
for(i = 0; i < ARRAY_SIZE(Point); i++) {
switch(Point[i].type) {
case INT_POINT_START:
line_cnt++;
break;
case INT_POINT_END:
line_cnt--;
break;
default:
break;
}
if(2 == line_cnt) {
if(false == spot_start) {
commom_e.start = Point[i].val;
spot_start = true;
}
}
if(line_cnt < 2) {
if(spot_start) {
if(false == spot_end) {
spot_end = true;
commom_e.end = Point[i].val;
}
}
}
}
IntervalS_t commom_s = {0};
res = IntervalConvert_e_s(&commom_e, &commom_s);
if(commom_s.size) {
res = true;
} else {
res = false;
}
return res;
}Функция interval_is_dock проверяет, что интервалы стыкуются другу к другу без промежутка.
bool interval_is_dock(const IntervalE_t* const pA, const IntervalE_t* const pB) {
bool dock = false;
if(pA->end == pB->start) {
dock = true;
}
if(pB->end == pA->start) {
dock = true;
}
return dock;
}
И проверка, что один интервал поглощает другой интервал
static bool interval_is_a_in_b(const IntervalE_t* const pA,
const IntervalE_t* const pB) {
bool res = false;
if(pB->start <= pA->start) {
if(pA->end <= pB->end) {
res = true;
}
}
return res;
}
bool interval_is_merge(IntervalE_t* const pA,
IntervalE_t* const pB) {
bool res = false;
res = interval_is_a_in_b(pA, pB);
if(false == res) {
res = interval_is_a_in_b(pB, pA);
}
return res;
}Вот и весь джентельменский набор.
Арифметику над интервалами лучше выделить в отдельный программный компонент и отдельную папку в репозитории с именем interval. Это пригодится Вам много где. Например для определения пересечения временных интервалов или при пуске NVRAM.
Что можно улучшить
Формально можно построить целую алгебру над интервалами. Определить сумму интервалов, разность интервалов, умножение интервала на число, логические операции "и", "или", "исключающее или", "нет" между интервалами и прочее. Определить строгое [] и нестрогое () вхождения границ интервалов (как в школе). Корректно обрабатывать интервалы-лучи и прочее. Однако самая употребительная задача - это всё же проверять интервалы на пересечения и на поглощение. Остальное - чисто из академического интереса.
Приложения интервальной арифметики
1--Поиск пересечения временных интервалов в расписании транспорта.
2--проверка диапазонов памяти в прошивках. Проверка конфигов для NVRAM на валидность при старте прошивки.
3--построение диаграмм Ганта в программах планировщиках задач.
4--Реализация функции memmove()
Итог
Удалось научиться просто и легко проверять факт наличия пересечения/поглощения абстрактных интервалов. Это открывает дорогу для разработки с NVRAM внутри микроконтроллерных прошивок и многого другого.
Ссылки
№ |
Название |
URL |
1 |
Задача о Выборе Билетов |
|
2 |
NVRAM для микроконтроллеров |
|
3 |
ISO 26262-6 разбор документа (или как писать безопасный софт) |
Комментарии (32)
Kelbon
16.06.2025 18:39Задача поставлена неправильно. В той постановке что в статье, хватит простой проверки находится ли точка внутри интервала, дальше если одна точка находится в интервале - пересекаются, если обе - один содержит другой
А тут решается другая задача, когда уже есть очень много интервалов и нужно сделать поиск лучше чем за O(N) перебора всех интервалов
Я не олимпиадник, но если задача в том чтобы проверять пересекаются ли интервалы в памяти, то рассуждал бы так:
если хотя бы одно пересечение есть, то это уже ошибка, такого быть не должно. Мы не должны создавать программу, которая работает в памяти там где другая программа уже заняла. Значит мы можем исходить из того, что никакие уже добавленные интервалы никогда не пересекаютсяЗначит оптимизация с объединением интервалов например нам ничего не даст
Так что решается так:
закинуть все точки начал и концов интервалов в сортированный массив
при поиске пересечений искать любые точки между началом и концом проверяемого интервала. Если найдено - пересечение есть
Всё
Sdima1357
16.06.2025 18:39Сортировать надо структуры типа {позиция, признак начало_конец, номер интервала} , только по позиции и только один раз. Это тоже задача что и определение самопересечения 3д меша , на каком нибудь луче по знакам нормалей
aabzel Автор
16.06.2025 18:39Пробовал сортировать один раз (по X).
Получилось так, что не все модульные тесты проходят из той таблицы, что в тексте.Не надо забывать, что есть ещё и точечные интервалы.
Sdima1357
16.06.2025 18:39точечные интервалы - без проблем. интервалы у Вас целочисленные.От каждого начала вычитаю 0.25 , к каждому концу прибавляю 0.25 , отсортировал. Признак начала +1 конца -1. бегу по порядку . и складываю признак в сумму. 0 - я вне интервала, 1 внутри. больше 1 те 2,3 - я зашел в несколько интервалов сразу. Если домножить на 4 все на четыре вместо 0.25 будет 1.
Sdima1357
16.06.2025 18:39#include <stdio.h> #include <stdlib.h> // Define SIZE for interval array and size calculations. #define SIZE 8 // Entry structure definition struct entry { int position; int start_stop; int index; }; // Input intervals array struct input { int start; int length; char id; } intervals[SIZE] = { {0, 10, 'A'}, {10, 10 , 'B'}, {20, 10, 'C'}, {30, 10, 'D'}, {5, 10, 'W'}, {20, 1, 'X'}, {29, 1, 'Y'}, {20, 10, 'Z'} }; // Compare function for qsort int compare_entries(const void *a, const void *b) { struct entry *entryA = (struct entry *) a; struct entry *entryB = (struct entry *) b; return entryA->position - entryB->position; } // Main function int main() { // Allocate memory for entries array struct entry *entries = (struct entry*) malloc(sizeof(struct entry) * SIZE * 2); if (!entries) { fprintf(stderr, "Memory allocation failed\n"); return 1; } /* Fill the entries array with appropriate values */ for (int i = 0; i < SIZE; i++) { // Start position entries[i * 2].position = intervals[i].start * 4 - 1; entries[i * 2].index = i; entries[i * 2].start_stop = 1; // End position entries[i * 2 + 1].position = (intervals[i].start + intervals[i].length-1) * 4 + 1; entries[i * 2 + 1].index = i; // Correct here to assign the index for end position entries[i * 2 + 1].start_stop = -1; } /* Sort the array using qsort */ qsort(entries, SIZE * 2, sizeof(struct entry), compare_entries); // Print sorted list of entries for verification printf("Sorted Entries:\n"); int summ = 0; for (int i = 0; i < SIZE * 2; i++) { summ+=entries[i].start_stop; if(summ>=2) { printf("intersect on %c position %d\n",intervals[entries[i].index].id,(entries[i].position+1)/4); } } // Free allocated memory free(entries); return 0; }
aabzel Автор
16.06.2025 18:39Это тоже задача что и определение самопересечения 3д меша , на каком нибудь луче по знакам нормалей
Это еще что за задача такая?
Есть ли возможность написать, пожалуйста, постановку задачи?
playermet
16.06.2025 18:39Вроде все проще должно быть.
1) Представляем каждый интервал началом, длиной, и именем в том виде в каком он удобен (структурой и указателями или еще как-то).
2) Сортируем один массив один раз по координате начала точки.
3) Один раз линейно проходим массив слева направо, и ищем пересечения справа для каждого элемента, пока они есть.
Рабочий псевдокод на Lua:
local intervals = { { start = 0, length = 10, name = "A" }; { start = 10, length = 10, name = "B" }; { start = 20, length = 10, name = "C" }; { start = 30, length = 10, name = "D" }; { start = 5, length = 10, name = "W" }; -- Пересекает A и B { start = 20, length = 1, name = "X" }; -- Точка в начале C { start = 29, length = 1, name = "Y" }; -- Точка в конце C { start = 30, length = 10, name = "Z" }; -- Совпадает с D } table.sort(intervals, function (a, b) return a.start < b.start end ) for i = 1, #intervals - 1 do local curr_end = intervals[i].start + intervals[i].length - 1 local j = i + 1 while j <= #intervals and intervals[j].start <= curr_end do print(('Intersect between %s and %s at [%s, %s]'): format(intervals[i].name, intervals[j].name, math.max(intervals[i].start, intervals[j].start), math.min(curr_end, intervals[j].start + intervals[j].length - 1))) j = j + 1 end end --[[ Вывод: Intersect between A and W at [5, 9] Intersect between W and B at [10, 14] Intersect between C and X at [20, 20] Intersect between C and Y at [29, 29] Intersect between D and Z at [30, 39] ]]Да, в худшем случае это квадратичный алгоритм, но лучше и не будет, потому что задача требует найти все пересечения, а в худшем случае все интервалы пересекаются со всеми. На реальных данных такого скорее всего не возникнет, и сложность будет ближе к линейной.
Вместо print рабочая функция может складировать пересечения в массив, выводить в лог, устанавливать флаг, или что там требуется в реальной задаче. Заодно можно переупорядочивать вывод имен интервалов для удобства чтения и т.д.
playermet
16.06.2025 18:39Вот еще минимальные изменения для переупорядочивания имен. Имхо читать вывод так значительно легче. А еще лучше будет сложить в массив и отсортировать его по левому имени интервала.
local function sort_names(a, b, less) return a < b == less and a or b end ... print(('Intersect between %s and %s at [%s, %s]'): format( sort_names(intervals[i].name, intervals[j].name, true), sort_names(intervals[i].name, intervals[j].name, false), math.max(intervals[i].start, intervals[j].start), math.min(curr_end, intervals[j].start + intervals[j].length - 1))) --[[ Вывод: Intersect between A and W at [5, 9] Intersect between B and W at [10, 14] Intersect between C and X at [20, 20] Intersect between C and Y at [29, 29] Intersect between D and Z at [30, 39] ]]С точечными интервалами тоже работает:
local intervals = { { start = 0, length = 1, name = "A" }; { start = 1, length = 1, name = "B" }; { start = 2, length = 1, name = "C" }; { start = 3, length = 1, name = "D" }; { start = 1, length = 2, name = "X" }; -- Пересекает B и C { start = 1, length = 1, name = "Y" }; -- Точка в B } --[[ Вывод: Intersect between X and Y at [1, 1] Intersect between B and X at [1, 1] Intersect between C and X at [2, 2] Intersect between B and Y at [1, 1] ]]
domix32
16.06.2025 18:39Точечный интервал по идее должен иметь длину 0.
playermet
16.06.2025 18:39Это ведь прямая целых чисел. Меньше чем одну ячейку памяти из текста задачи занять нельзя.
Но если добавить обнаружение не только пересечений, но и соприкасаний, то будет и с нулями в плавающей запятой работать. Только нужно будет учесть потенциальные погрешности согласно конкретной задаче.
Akina
16.06.2025 18:39Вот в упор не понимаю, за каким рожном тут именно устойчивая сортировка. Не нужна она, от слова "совсем". Всё, что необходимо - на фазе 3 проверять сумму с накоплением, которая cross, только в момент изменения значения.
miksoft
Видимо, я не понял проблему...
Мы пересечение вычисляем по-простому:
x1_start <= x2_end and x2_start <= x1_end
(при условии, что концы включаются в интервал)
randomsimplenumber
Я тоже не понял проблему. У каждой области памяти есть начало и размер. При сборке прошивки достаточно контролировать размер каждого раздела. И ничто ни с чем не пересечется.
aabzel Автор
Стандарт разработки ПО ISO-26262 требует перед применением конфига проверять его на валидность в run-time.
randomsimplenumber
Ну, надо значит надо
И если тест не прошел - то что, падать?
aabzel Автор
выдать красный текст в UART-CLI
randomsimplenumber
А потом падать, или лететь дальше, но с красным текстом?
aabzel Автор
Обычно неправильные конфиги выявляются в debug сборке. В release такое не попадает.
randomsimplenumber
А почему нельзя выполнить проверку на этапе сборки? Конфиг это же что-то вроде makefile? make test.
aabzel Автор
Потому что половина конфигов передаются си кодом, как константные массивы структур.
randomsimplenumber
Компилятор С умеет делать так чтобы структуры в памяти не пересекались.
Интересные у вас там конкурсы;)
aabzel Автор
Не адреса структур, а их значения не должны пересекаться.
randomsimplenumber
Значения эти куда-то указывают же? Компилятор умеет в указатели. Я даже не представляю, зачем нужно сначала сломать то что компилятор умеет от рождения, а потом подпирать это тестами.
Jijiki
при некоторых операциях перераспределения памяти есть момент когда мы сравниваем пересечение dst, src, это отличие копи от мув вроде если я не ошибаюсь
кароче при мув надо чтобы не было пересечения наверно
представим две строки, представим что они не по 1, а по 10 предположим, представим что нужен мув, и тогда поидее надо соблюсти пересечение(пример плохой я возможно ошибся я до конца пока сам не понимаю как мув работает)
aabzel Автор
Покажите полную функцию проверки пересечения интервалов.
randomsimplenumber
Сортируем все точки по возрастанию. Берём первые 2 точки. Если они принадлежат разным интервалам - упсь, пересекаются. Иначе - повторяем со следующей парой точек.
domix32
Тут стоит уточнять по возрастанию чего. У вас как минимум есть две точки интервала и их дифф то бишь размер, всех можно упорядочивать по возрастанию.
randomsimplenumber
Да ;) По возрастанию адреса в памяти.
По легенде, всё происходит при старте микроконтроллера, и достаточно одного упавшего теста, чтобы признать прошивку негодной. N log (N) на сортировку.
Хотя, кмк, включать в дебажный билд какие то алгоритмы, которых нет в релизном -;это какой-то кринж. Надо значит надо.
apevzner
Тут, наверное, речь об том, что интервалов много. Нет, не много, а вот прям МНОГО.
И надо как-то быстренько определить, не пересекается ли следующий интервал с уже имеющимися, попадает ли точка в какой-то из интервалов и т.п.
Тут, конечно, можно поизобретать что-нибудь, типа обобщенного бинарного поиска и т.п.