Комментарии 62
Видимо, я не понял проблему...
Мы пересечение вычисляем по-простому:
x1_start <= x2_end and x2_start <= x1_end
(при условии, что концы включаются в интервал)
Я тоже не понял проблему. У каждой области памяти есть начало и размер. При сборке прошивки достаточно контролировать размер каждого раздела. И ничто ни с чем не пересечется.
При сборке прошивки достаточно контролировать размер каждого раздела. И ничто ни с чем не пересечется.
Стандарт разработки ПО ISO-26262 требует перед применением конфига проверять его на валидность в run-time.
Ну, надо значит надо
И если тест не прошел - то что, падать?
И если тест не прошел - то что, падать?
выдать красный текст в UART-CLI
А потом падать, или лететь дальше, но с красным текстом?
Обычно неправильные конфиги выявляются в debug сборке. В release такое не попадает.
при некоторых операциях перераспределения памяти есть момент когда мы сравниваем пересечение dst, src, это отличие копи от мув вроде если я не ошибаюсь
кароче при мув надо чтобы не было пересечения наверно
представим две строки, представим что они не по 1, а по 10 предположим, представим что нужен мув, и тогда поидее надо соблюсти пересечение(пример плохой я возможно ошибся я до конца пока сам не понимаю как мув работает)
Ну, shall be это не требование а пожелание. И я не увидел, почему это должно проверяться в runtime.
И я не увидел, почему это должно проверяться в runtime.
А где же этой проверке ещё происходить если не в run-time?
Ну, shall be это не требование а пожелание
Нет, в технических текстах обычно используют язык из RFC 2119:
MUST This word, or the terms "REQUIRED" or "SHALL", mean that the definition is an absolute requirement of the specification.
Так что это требование. Вот "Should" было бы пожеланием.
Покажите полную функцию проверки пересечения интервалов.
Сортируем все точки по возрастанию. Берём первые 2 точки. Если они принадлежат разным интервалам - упсь, пересекаются. Иначе - повторяем со следующей парой точек.
Тут стоит уточнять по возрастанию чего. У вас как минимум есть две точки интервала и их дифф то бишь размер, всех можно упорядочивать по возрастанию.
Да ;) По возрастанию адреса в памяти.
По легенде, всё происходит при старте микроконтроллера, и достаточно одного упавшего теста, чтобы признать прошивку негодной. N log (N) на сортировку.
Хотя, кмк, включать в дебажный билд какие то алгоритмы, которых нет в релизном -;это какой-то кринж. Надо значит надо.
Тут, наверное, речь об том, что интервалов много. Нет, не много, а вот прям МНОГО.
И надо как-то быстренько определить, не пересекается ли следующий интервал с уже имеющимися, попадает ли точка в какой-то из интервалов и т.п.
Тут, конечно, можно поизобретать что-нибудь, типа обобщенного бинарного поиска и т.п.
"Образно выражаясь ращипим интервалы на атомарные точки."
Расщепим?
Задача поставлена неправильно. В той постановке что в статье, хватит простой проверки находится ли точка внутри интервала, дальше если одна точка находится в интервале - пересекаются, если обе - один содержит другой
А тут решается другая задача, когда уже есть очень много интервалов и нужно сделать поиск лучше чем за O(N) перебора всех интервалов
Я не олимпиадник, но если задача в том чтобы проверять пересекаются ли интервалы в памяти, то рассуждал бы так:
если хотя бы одно пересечение есть, то это уже ошибка, такого быть не должно. Мы не должны создавать программу, которая работает в памяти там где другая программа уже заняла. Значит мы можем исходить из того, что никакие уже добавленные интервалы никогда не пересекаются
Значит оптимизация с объединением интервалов например нам ничего не даст
Так что решается так:
закинуть все точки начал и концов интервалов в сортированный массив
при поиске пересечений искать любые точки между началом и концом проверяемого интервала. Если найдено - пересечение есть
Всё
Сортировать надо структуры типа {позиция, признак начало_конец, номер интервала} , только по позиции и только один раз. Это тоже задача что и определение самопересечения 3д меша , на каком нибудь луче по знакам нормалей
Пробовал сортировать один раз (по X).
Получилось так, что не все модульные тесты проходят из той таблицы, что в тексте.
Не надо забывать, что есть ещё и точечные интервалы.
Ну значит что то не то либо с реализацией либо с тестами.
точечные интервалы - без проблем. интервалы у Вас целочисленные.От каждого начала вычитаю 0.25 , к каждому концу прибавляю 0.25 , отсортировал. Признак начала +1 конца -1. бегу по порядку . и складываю признак в сумму. 0 - я вне интервала, 1 внутри. больше 1 те 2,3 - я зашел в несколько интервалов сразу. Если домножить на 4 все на четыре вместо 0.25 будет 1.
#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;
}Это тоже задача что и определение самопересечения 3д меша , на каком нибудь луче по знакам нормалей
Это еще что за задача такая?
Есть ли возможность написать, пожалуйста, постановку задачи?
Вроде все проще должно быть.
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 рабочая функция может складировать пересечения в массив, выводить в лог, устанавливать флаг, или что там требуется в реальной задаче. Заодно можно переупорядочивать вывод имен интервалов для удобства чтения и т.д.
Вот еще минимальные изменения для переупорядочивания имен. Имхо читать вывод так значительно легче. А еще лучше будет сложить в массив и отсортировать его по левому имени интервала.
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]
]]
Вот в упор не понимаю, за каким рожном тут именно устойчивая сортировка. Не нужна она, от слова "совсем". Всё, что необходимо - на фазе 3 проверять сумму с накоплением, которая cross, только в момент изменения значения.
Вам тут не нужна устойчивая сортировка. Вам нужна любая сортировка, выполняемая один раз, но по сложному ключу. Вместо того, чтобы отсортировать по координате, потом сортировать по типу скобочки не портя порядок, можно сразу отсортировать по обоим ключам. Просто функция проверки должна в правильном порядке сравнивать все поля ключей:
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);
}Это работает, потому что самый левый отрезок, если и пересекается с каким-то орезком, то пересекается и со всеми, левее него. А значит точно есть пересечение и со вторым отрезком в отсортированном массиве. Если же первый отрезок не пересекается со вторым, то не пересекается и с любым следующим, ведь они еще правее второго. Дальше можно первый отрезок исключить из рассмотрения и применить ту же логику опять.
Вам тут не нужна устойчивая сортировка. Вам нужна любая сортировка, выполняемая один раз, но по сложному ключу. Вместо того, чтобы отсортировать по координате, потом сортировать по типу скобочки не портя порядок, можно сразу отсортировать по обоим ключам. Просто функция проверки должна в правильном порядке сравнивать все поля ключей:
Гениально! Спасибо. Я сам бы до такого никогда не додумался.
Если все-таки "прицепить" линейную алгебру, то:
Интервал на одномерной шкале - аналог аффинного вектора, - разность точек шкалы. Примерно так:
, где
- границы. Вообще, - это представление границ интервала, а не самого интервала, но тут это неважно.Плюсом получаем возможность представления множества интервалов, например:
.Представлять такие интервалы можно табличкой с колонками точек (границ) и их амплитуд (+1, - 1).
Сложение смежных интервалов - обычная свертка таблицы по границам (и сложение их амплитуд):
Операция пересечения сводится к алгебре - умножению амплитуд границ:
Тонкость в том, что базовые интервалы
тут упорядочены. Подразумевается, что
.Полученный интервал пересечения, выраженный в базовых интервалах
, можно привести к "граничному представлению", раскрыв интервалы и просуммировав коэффициенты (амплитуды) границ. Пункты 5, 6 можно свести в одну операцию, - коэффициенты будут выражены как накопительные суммы (опять же - используется направленность шкалы, то есть упорядоченность границ).Скорее всего формулы и примеры заслуживают отдельной статьи, раз вопросы по интервалам периодически всплывают.
Тонкость в том, что базовые интервалы
Вы фактически описали ровно то, что автор и сделал. Только у него не +1 и -1, а скобочки [ и ]. Но идея та же самая: сортируем все эти "события" на оси, потом проходимся и считаем сколько сейчас открыто интервалов.
Вы фактически описали ровно то, что автор и сделал.
Не, насколько я смог понять, это автор реализовал частный случай общего подхода ).
Тут прикольно, что фактически используется скалярное произведение аффинных векторов. Но с учетом упорядоченности. Хотя казалось бы, - где интервалы, и где скалярное произведение.
Короче, на алгебру надежнее опираться. И это мы еще двумерных интервалов не касались ).
Короче, на алгебру надежнее опираться. И это мы еще двумерных интервалов не касались ).
Вы тут сову на глобус натягиваете. Ваша формализация очень неформальна и непонятно, как с ней работать. Вот вы написали, что множество из отрезков [a..b] [c..d] описываеся как a-b+c-d. Это число? Не может быть, ведь тогда это тупо суммарная длина отрезков, этого совсем не достаточно чтобы работать с отрезками. Что это за объекты, как работает с ними операция сложения/вычитания. У вас там где-то векторы должны быть. Скольки мерные? Как отрезок [a b] отличается от [a+1 b+1]?
Тут прикольно, что фактически используется скалярное произведение аффинных векторов
Скалярное произведение обычно дает число. Как оно тут используется я так и не понял. Пока вы это не формализуете, ваш "более общий метод" существует только у вас в воображении.
О, как набросились). Конечно, я тут по верхушкам общего формализма только прошелся, - это ж коммент, а не учебник. Но насчет "скалярного произведения" вы правы, - опечатался по привычке, - конечно, речь была про "внутреннее произведение" векторов.
Ну и кратко по вашим вопросам.
Если a и b - это точки, то как их разность может быть числом? Это просто разность элементов - аффинный вектор. Я вообще считал, что это не требует пояснения.
Возможно, вас запутало то, что интервалы тут определены на числовой шкале. Ну дак шкала может быть любой, лишь бы на ней упорядоченность можно было ввести. Можно алфавит взять - там буквы упорядочены. Вот вам интервал в форме вектора от буквы 'а' до 'д': [a - [д. Это граничное (векторное) представление.
Как с векторами работает операция сложения/вычитания? А в чем проблема? Все стандартно. Про мерность векторов тоже не понял, - тут пространство одномерно, соответственно и векторы/интервалы тоже одномерные. Но могут состоять из нескольких элементов (точек) - это для вас проблема?
Скалярное произведение интервалов действительно существует, если метрику (длины интервалов) ввести. И дает число - размер (длину) области пересечения. Кроме того, - работает не только в одномерных (линейных шкалах), но и на графах-деревьях. Но тут я уже не буду в подробности вдаваться - и так перебор.
Сделал вывод, что статья про алгебру интервалов была бы на хабре полезной.
Сколько пафоса)
просто разность элементов - аффинный вектор. Я вообще считал, что это не требует пояснения.
Требует пояснения, потому что упоминать самые простые одномерные вектора в контексте этой задачи - это вообще не к месту.
Если это просыте вектора, то отрезки [1,2] и [10000,10001] - это один и тот же вектор. Они не различимы. Бесполезная нотация.
Как с векторами работает операция сложения/вычитания?
Это тоже тут вообще бесполезно, ибо {[1,2] [3,5] [4,6] [9,10]} и {[1,2] [3,5] [6,8] [9,10]} дадут один и тот же результат по вашим формулам, но в первом случае средние отрезки пересекаются, а во втором - нет. Опять же, это тупо суммарная длина всех отрезков. Ну, допустим, положительный вектор с такой длиной. Бесполезная вещь вообще.
Скалярное произведение интервалов действительно существует,
Если у вас отрезки - это одномерные вектора, то скалярное произведение дает тупо произведение их длин. Бесполезная фигня.
И дает число - размер (длину) области пересечен
Это если у вас отрезки представлены, например, в виде функций-индикаторов, которые дайют 1 на отрезке и 0 вне его. Тогда да, скалярное произведение - интеграл от произведения функций - даст ровно длину пересечения. И тут даже есть линейное пространство функций. Вы, похоже, где-то краем глаза это увидели, запомнили только что там скалярное произведение, додумали до векторов, и пошли показывать, какие вы умные, даже не понимая о чем пишите.
Сделал вывод, что статья про алгебру интервалов была бы на хабре полезной.
Только если там уровень формализма будет чуточку (на пару порядков) серъезнее, чем в ваших комментариях.
Ужас какой, куда я вляпался. Вы при таких набросах реально на диалог рассчитываете? Всего вам доброго! )
Если это просыте вектора…
разность элементов - аффинный вектор
Вы здесь путаете аффинные векторы со свободными векторами. Это всё так сильно разные штуки.
Вы здесь путаете аффинные векторы
Я не знаю никаких аффинных векторов. Знаю аффинные пространства. Вообще поиск в гугле "аффинный вектор" никаких определений не возвращает. Могли бы вы привести определение для непосвещенных?
Лично мне понятие аффинного вектора тоже незнакомо. Я лишь обращал внимание, что Вы его путаете с другими векторами.
Судя по всему, понятие аффиного вектора родственно понятию связанного вектора - просто упорядоченная пара точек аффинного пространства.
Плюс, похоже товарищ @dmagin знает какую-то алгебру поверх этих векторов. Пока что выглядит как во многом формальные комбинации векторов.
Лично мне понятие аффинного вектора тоже незнакомо
Ну вот и вам тоже. Но у @dmaginэто "Я вообще считал, что это не требует пояснения". Нам с вами, наверно, должно быть стыдно.
И вообще, вот вы тут тоже не правы. Вы не знаете что это такое, интернет не знает что это такое, автор комментария это не пояснил, но вы меня упрекаете, что я тут, оказывается, что-то с чем-то спутал. Согласитесь, что вам тоже идея товарища dmagin вообще не понятна.
Судя по всему, понятие аффиного вектора родственно понятию связанного вектора
Это ниоткуда не следует. Разность двух точек в афинном пространстве, о которой говорил мой оппонент - это свободный вектор. Я это так и воспринял и не стал даже придираться к несуществующим определениям. Тем более автор утверждает, что это должно быть всем понятно, так что "афинный вектор" - явно не какая-то редкая заумная вещь, а лишь некорректное и небрежное называние чего-то совсем простого.
Использование связанных векторов, действительно, сразу бы решило кучу проблем, о которых я говорил, вроде того, что отрезки [1,2] и [101,102] обозначаются одним и тем же свободным вектором, что в контексте задачи о пересечении отрезков делает их применение бесполезным (ведь пересечение определяется всязимным положением отрезков, так что забывать о их положении нельзя). Но там бы возникли другие проблемы, например в нотации объединения отрезков. Вот что такое сумма двух произвольных связанных векторов вообще?
Но, поскольку мой оппонент явно не хочет разъяснять свои идеи, мы так и не узнаем, что именно там имелось ввиду.
"Скобочки", пожалуй, тоже заслуживают замечания. Дело в том, что обычно интервалы задаются не границами как таковыми, а границами других интервалов. Например, "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), а положение границы относительно запятой.
При работе с интервалами все границы надо приводить к одному типу - все либо левые, либо правые
Не обязательно. Надо лишь знать, что граница начало или конец и включается ли она в интервал или нет. Обычно все интервалы одного типа (замкнутые или открытые).
Надо лишь знать, что граница начало или конец и включается ли она в интервал или нет.
Нет, это не так. Граница - это точка. У нее нулевая длина. Она не дает вклада в интервал. Поэтому нет смысла задавать вопрос о принадлежности точечной границы интервалу. Вы так же как и многие путаете здесь граничные интервалы и границы. 2 - это интервал, а [2 или 2] - точки. Примеры границ-точек на временной шкале: "КонецДня(), КонецНедели(), НачалоМесяца(). Нет смысла задавать вопрос, принадлежит ли текущему месяцу его конец ).
Граница - это точка. У нее нулевая длина.
Зависит от задачи. Где-то отрезки нулевой длины имеют смысл. Ваш же пример со временем. Запланировать 2 встречи подряд часто нормально. И если вы хотите в календарь вставить новую встречу, то можно рассмотреть множество возможных начал, которое окажется дополнением объединения открытых запрещенных интервалов. И там может получиться интервал нулевой длины - и можно взять точку из него, что равносильно вставке новой встречи между двумя существующими.
Ни разу не олимпиадный программист, но по идее, для решения таких задач давно придуманы специальные структуры данных, типа дерева интервалов . Это если вам таких проверок много надо делать. Если же проверка одна, то какая-то переусложненная реализация вышла, в духе "Hello world в кровавом ентерпрайзе".
Задача о пересечении интервалов (или зачем программисту MК стабильная сортировка)