В этом тексте вы узнаете зачем программистам микроконтроллеров нужна стабильная сортировка.
В программировании микроконтроллеров периодически приходится решать задачу о выявлении пересечения интервалов. Чаще всего это нужно при разработке загрузчиков и 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 разбор документа (или как писать безопасный софт) |
Комментарии (49)
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, только в момент изменения значения.
wataru
16.06.2025 18:39Вам тут не нужна устойчивая сортировка. Вам нужна любая сортировка, выполняемая один раз, но по сложному ключу. Вместо того, чтобы отсортировать по координате, потом сортировать по типу скобочки не портя порядок, можно сразу отсортировать по обоим ключам. Просто функция проверки должна в правильном порядке сравнивать все поля ключей:
bool less(Event a, Event b) { if (a.time < b.time) return true; if (a.time > b.time) return false; if (a.type < b.type) return true; if (a.tupe > b.type) return false; return a.id < b.id; }Можно это вставить в свою сортировку, а можно функцию сравнения передать тому же qsort (правда, в C надо будет изменить ее возвращать не true/false, а отрицательное/нулевое/положительное число).
А так, еще стоит указать, что ваш метод поиска пересечений в литературе известен как метод заметающей прямой. Но это не самый простой метод в реализации. Он чуть мощнее других и позволяет, например, найти точку покрытую наибольшим количеством отрезков. Или можно разрешать вложенность отрезков но не пересечение.
Более простой метод: все отрезки отсортировать по началу, потом пройтись по массиву один раз и проверять каждые 2 соседних отрезка на пересечение через min/max начал и концов:
bool Intersects(Segment a, Segment b) { return min(a.right, b.right) >= max(a.left, b.left); }Это работает, потому что самый левый отрезок, если и пересекается с каким-то орезком, то пересекается и со всеми, левее него. А значит точно есть пересечение и со вторым отрезком в отсортированном массиве. Если же первый отрезок не пересекается со вторым, то не пересекается и с любым следующим, ведь они еще правее второго. Дальше можно первый отрезок исключить из рассмотрения и применить ту же логику опять.
aabzel Автор
16.06.2025 18:39Вам тут не нужна устойчивая сортировка. Вам нужна любая сортировка, выполняемая один раз, но по сложному ключу. Вместо того, чтобы отсортировать по координате, потом сортировать по типу скобочки не портя порядок, можно сразу отсортировать по обоим ключам. Просто функция проверки должна в правильном порядке сравнивать все поля ключей:
Гениально! Спасибо. Я сам бы до такого никогда не додумался.
wataru
16.06.2025 18:39Забавно, мне наоборот идея использовать стабильные сортировки вот так вот в голову плохо помещается. Идея о том, как radix sort писать нерекурсивно за счет стабильных сортировок (что практически та же идея, что у вас) в свое время сломала мне мозг.
aabzel Автор
16.06.2025 18:39Я просто сначала на бумажке эту задачу решал. Таблицы чертил. И зацепился за идею многоступенчатой сортировки.
dmagin
16.06.2025 18:39Если все-таки "прицепить" линейную алгебру, то:
Интервал на одномерной шкале - аналог аффинного вектора, - разность точек шкалы. Примерно так:
, где
- границы. Вообще, - это представление границ интервала, а не самого интервала, но тут это неважно.Плюсом получаем возможность представления множества интервалов, например:
.Представлять такие интервалы можно табличкой с колонками точек (границ) и их амплитуд (+1, - 1).
Сложение смежных интервалов - обычная свертка таблицы по границам (и сложение их амплитуд):
-
Операция пересечения сводится к алгебре - умножению амплитуд границ:
Тонкость в том, что базовые интервалы
тут упорядочены. Подразумевается, что
. -
Полученный интервал пересечения, выраженный в базовых интервалах
, можно привести к "граничному представлению", раскрыв интервалы и просуммировав коэффициенты (амплитуды) границ. Пункты 5, 6 можно свести в одну операцию, - коэффициенты будут выражены как накопительные суммы (опять же - используется направленность шкалы, то есть упорядоченность границ).Скорее всего формулы и примеры заслуживают отдельной статьи, раз вопросы по интервалам периодически всплывают.
wataru
16.06.2025 18:39Тонкость в том, что базовые интервалы
тут упорядочены. Вы фактически описали ровно то, что автор и сделал. Только у него не +1 и -1, а скобочки [ и ]. Но идея та же самая: сортируем все эти "события" на оси, потом проходимся и считаем сколько сейчас открыто интервалов.
dmagin
16.06.2025 18:39Вы фактически описали ровно то, что автор и сделал.
Не, насколько я смог понять, это автор реализовал частный случай общего подхода ).
Тут прикольно, что фактически используется скалярное произведение аффинных векторов. Но с учетом упорядоченности. Хотя казалось бы, - где интервалы, и где скалярное произведение.
Короче, на алгебру надежнее опираться. И это мы еще двумерных интервалов не касались ).
dmagin
16.06.2025 18:39"Скобочки", пожалуй, тоже заслуживают замечания. Дело в том, что обычно интервалы задаются не границами как таковыми, а границами других интервалов. Например, "2-е число месяца" - это не граница, а интервал. Как и "2-я ячейка памяти". Для числа 2 его левая граница обозначается как [2, а правая - как 2]. При работе с интервалами все границы надо приводить к одному типу - все либо левые, либо правые. Поскольку сложно указать системе, что 2] == [3. Поэтому интервал "со 2-го по 5-е" - это интервал [2, 5], но в канонической форме его следует задавать как [2, 6[ или [2, [6. Тогда границы будут сокращаться при сложении: [2, 5] + [6, 10] == [2, 6[ + [6, 11[ == [2 - 6[ + [6 - 11[ == [2, 11[ == [2, 10].
Таким образом не тип скобки определяет амплитуду границы (+1 или -1), а положение границы относительно запятой.
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
Ну, shall be это не требование а пожелание. И я не увидел, почему это должно проверяться в runtime.
aabzel Автор
А где же этой проверке ещё происходить если не в run-time?
randomsimplenumber
Там где конфиги генерируются там и проверять.
aabzel Автор
Не генерируются они. Их руками человек прописывает.
А человеку свойственно делать опечатки.
randomsimplenumber
Ну так тем более. Это либо на эта этапе git hook, либо на этапе сборки. Тащить какие то непроверенные конфиги в прошивку и проверять в полете, смело конечно.
aabzel Автор
MCU нынче мощные. Не перетрудятся единовременной проверкой конфига.
wataru
Нет, в технических текстах обычно используют язык из RFC 2119:
Так что это требование. Вот "Should" было бы пожеланием.
aabzel Автор
Покажите полную функцию проверки пересечения интервалов.
randomsimplenumber
Сортируем все точки по возрастанию. Берём первые 2 точки. Если они принадлежат разным интервалам - упсь, пересекаются. Иначе - повторяем со следующей парой точек.
domix32
Тут стоит уточнять по возрастанию чего. У вас как минимум есть две точки интервала и их дифф то бишь размер, всех можно упорядочивать по возрастанию.
randomsimplenumber
Да ;) По возрастанию адреса в памяти.
По легенде, всё происходит при старте микроконтроллера, и достаточно одного упавшего теста, чтобы признать прошивку негодной. N log (N) на сортировку.
Хотя, кмк, включать в дебажный билд какие то алгоритмы, которых нет в релизном -;это какой-то кринж. Надо значит надо.
apevzner
Тут, наверное, речь об том, что интервалов много. Нет, не много, а вот прям МНОГО.
И надо как-то быстренько определить, не пересекается ли следующий интервал с уже имеющимися, попадает ли точка в какой-то из интервалов и т.п.
Тут, конечно, можно поизобретать что-нибудь, типа обобщенного бинарного поиска и т.п.
miksoft
А можно конкретнее? Миллиард?
У нас вполне себе миллиарды обрабатываются. Правда, у нас не микроконтроллеры, а бизнес-данные.