Обсуждение двух задач на пересечение отрезков

15.03.19

Разработка - Математика и алгоритмы

Ищем общее в частностях, или задача о пересечении отрезков.

Чем хороша математика? Возможно, тем, что  с помощью универсального языка формулирует методы и решения, которые впоследствии можно применять к самым разным явлениям окружающего мира. Задача разработчика состоит в том, чтобы за различными формами разглядеть общее содержание и эффективно использовать разработанный для этого содержания математический аппарат. Проиллюстрируем данный тезис с помощью статей, которые были в разное время размещены на  портале infostart.

Начнем с "ФИФО для любопытных". В данной публикации обсуждается, как одним запросом получить все движения расходных документов за период. Есть таблица приходных накладных, которые формируют партии товаров, и таблица расходных накладных, в которых эти товары списываются. Необходимо для каждого документа списания указать документы партии и количество товара, которое списывается с каждой партии. Теперь обратимся к "Распределение в запросе" или "избавляемся от перебора". Автор приводит найденное им решение для следующей задачи. Есть складские ячейки с известной емкостью  (A, B, C, D) и сам товар (X, Y, Z), который необходимо «как-то» разложить по этим ячейкам, но так, чтоб в ячейку не положили больше товара, чем может быть в ней места. 

При всей ,на первый взгляд,непохожести обсуждаемых в данных статьях темах речь идет об одной и той же математической задаче. Есть два множества отрезков. Отрезки заданы координатами начала и конца, причем координаты правой точки больше координаты левой. Каждому отрезку сопоставлен уникальный индекс,например ссылка на документ.  Надо определить какие отрезки пересекаются и вычислить длину этого пересечения. Покажем как формируются эти отрезки.  Рассмотрим задачу "Ячейки и Товары".

Таблица с ячейками переходит в таблицу с отрезками, где начало и конец определяются с помощью запроса с нарастающими итогами. Аналогично строим таблицу для товаров.

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

Найдем критерий, по которому мы можем собрать пересекающиеся отрезки. Эта задача решена  древними греками, а может и еще раньше.  Приведем одно из возможных рассуждений. Даны два отрезка А(начало,конец) и Б(начало,конец). Начало и конец это координаты отрезка. Проще всего сформулировать правило , при котором отрезки НЕ пересекаются. Оно такое (А.конец < Б.начало ИЛИ A.начало>Б.конец). Применим к данному выражению отрицание, тогда оно трансформируется в условие (А.конец>= Б.начало И A.начало<=Б.конец). После этого становится понятно, как выбрать все пары пересекающихся отрезков.

Текст="ВЫБРАТЬ
      |	А.индекс КАК Аи,
      |	Б.индекс КАК Би
      |ИЗ
      |	А КАК А
      |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Б КАК Б
      |		ПО А.конец >= Б.начало
      |		И А.начало <= Б.конец";

Теперь осталось добавить длину пересечения. А она равна Мин(А.конец,Б.конец)-Макс(А.начало,Б.начало), что на языке запросов выглядит как:

Текст="ВЫБРАТЬ
      |	А.индекс КАК Аи,
      |	Б.индекс КАК Би,
      |	ВЫБОР
      |		КОГДА А.конец < Б.конец
      |			ТОГДА А.конец
      |		ИНАЧЕ Б.конец
      |	КОНЕЦ - ВЫБОР
      |		КОГДА А.начало > Б.начало
      |			ТОГДА А.начало
      |		ИНАЧЕ Б.начало
      |	КОНЕЦ КАК Пересечение
      |ИЗ
      |	А КАК А
      |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Б КАК Б
      |		ПО А.конец >= Б.начало
      |		И А.начало <= Б.конец";

Применим предложенный алгоритм к нашим данным.

Функция ДобавитьОтрезок(длина,куда)
	запись        =куда.Добавить()  ;
	запись.индекс =куда.Количество();
	если запись.индекс=1 тогда
		запись.начало =0           ;
	иначе
		запись.начало =куда[запись.индекс-2].конец;
	конецесли;
	запись.конец  =запись.начало+длина;
	
	возврат запись;
КонецФункции

Функция Пересечение() export
	

	start=ТекущаяУниверсальнаяДатаВМиллисекундах();
	
	типЧ=новый ОписаниеТипов("Число");
	
	тзА = new ТаблицаЗначений;
	тзА.Колонки.Добавить("индекс",типЧ);
	тзА.Колонки.Добавить("начало",типЧ);
	тзА.Колонки.Добавить("конец",типЧ);
	
	ДобавитьОтрезок(10,тзА);
	ДобавитьОтрезок(3 ,тзА);
	ДобавитьОтрезок(3 ,тзА);
	ДобавитьОтрезок(13,тзА);
	
	
	тзБ = тзА.СкопироватьКолонки();
	ДобавитьОтрезок(12,тзБ);
	ДобавитьОтрезок(8 ,тзБ);
	ДобавитьОтрезок(6 ,тзБ);
	
	
	
	
	Текст="ВЫБРАТЬ
	      |	тз.индекс КАК индекс,
	      |	тз.начало КАК начало,
	      |	тз.конец КАК конец
	      |ПОМЕСТИТЬ А
	      |ИЗ
	      |	&тзА КАК тз
	      |;
	      |
	      |////////////////////////////////////////////////////////////////////////////////
		  |ВЫБРАТЬ
	      |	тз.индекс КАК индекс,
	      |	тз.начало КАК начало,
	      |	тз.конец КАК конец
	      |ПОМЕСТИТЬ Б
	      |ИЗ
	      |	&тзБ КАК тз
	      |;
	      |
	      |////////////////////////////////////////////////////////////////////////////////
	      |ВЫБРАТЬ
	      |	А.индекс КАК Аи,
	      |	Б.индекс КАК Би,
	      |	ВЫБОР
	      |		КОГДА А.конец < Б.конец
	      |			ТОГДА А.конец
	      |		ИНАЧЕ Б.конец
	      |	КОНЕЦ - ВЫБОР
	      |		КОГДА А.начало > Б.начало
	      |			ТОГДА А.начало
	      |		ИНАЧЕ Б.начало
	      |	КОНЕЦ КАК Пересечение
	      |ИЗ
	      |	А КАК А
	      |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Б КАК Б
	      |		ПО А.конец >= Б.начало
	      |			И А.начало <= Б.конец";
	
	
	
	
   запрос=новый запрос(Текст);
   запрос.Параметры.Вставить("тзА",тзА);
   запрос.Параметры.Вставить("тзБ",тзБ);
    ответ=запрос.Выполнить().Выгрузить();
   end=ТекущаяУниверсальнаяДатаВМиллисекундах();
   message("выполнение запроса "+(end-start));
   возврат  ответ;
КонецФункции	

Функция ДобавитьОтрезок добавляет отрезок в массив, функция Пересечение возвращает пересечение отрезков из приведенного выше примера.

Именно этот алгоритм и реализован в приведенных выше публикациях. Можно ли предложить более эффективное решение. Да, можно, и вот почему. Приведенный запрос будет правильно работать для любых наборов отрезков, в том числе и пересекающихся внутри одного множества. В тоже время, по условиям задачи отрезки расположены непрерывно на числовой прямой,не пересекаются и конец предыдущего совпадает с началом следующего (спасибо нарастающим итогам).

В этом случае мы можем заменить представление отрезка его длиной и порядком следования(индексом)  А[индекс](длина). Индекс - это номер отрезка в таблице, длина - колонка из  таблицы, в которой хранятся рассматриваемые отрезки. Рассмотрим два левых отрезка  А и Б. Они пересекаются и длина пересечения равна длине минимального из них. Уберем этот отрезок из множества, в которое он входит, а второй укоротим на длину пересечения. Повторим нашу процедуру. Остановимся, когда обработаем все отрезки в первом или втором множестве. Именно такой алгоритм предложил Сергей в публикации "Минимализмы" раздел  7. Связывание таблиц значений по ФИФО.  Кстати, частным случаем данного алгоритма является списание по партии внутри одного расходного документа, что вполне естественно. Предложенный алгоритм показывает значительный выигрыш в быстродействии по сравнению с запросом, поскольку учитывает особенность расположения  отрезков в исходных множествах.

Надеюсь, что  данная  статья будет полезна при поиске общих математических подходов для непохожих, в первом приближении, процессов.

Пересечение отрезков нарастающие итоги

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7458    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8835    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7801    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. acanta 15.03.19 09:08 Сейчас в теме
Очень полезная информация.Спасибо.
2. script 128 15.03.19 13:55 Сейчас в теме
Вот шайтан. Пожалуйста добавьте в эту статью примеров с цифрами. Очень хочу в этом разобраться но никак не "въеду".
5. scientes 288 16.03.19 15:36 Сейчас в теме
В первоначальном варианте статьи была ошибка в запросе - сравнение индексов. Оно требуется, если ищутся пересекающиеся отрезки внутри одного множества. Когда работаем с двумя множествами, надо соединить "каждый с каждым" и это сравнение будет ошибкой.
3. bulpi 215 15.03.19 17:31 Сейчас в теме
"Предложенный алгоритм показывает значительный выигрыш в быстродействии по сравнению с запросом"
Ну, я думаю, и этот алгоритм можно запросом оформить, но нужно ли ? ildarovichildarovich бы точно смог :)
4. scientes 288 15.03.19 17:54 Сейчас в теме
(3)Думаю, что запросом это не сделать. Иначе бы ildarovich это сделал, а он предложил решение через программный код.
8. ildarovich 7850 18.03.19 17:20 Сейчас в теме
(3) (4) Слежу за этой темой. Сейчас есть вот такие мысли. Привожу их больше для желания собрать свой "state of art" по этой теме.
Запросом у меня есть: в Минимализмах 3 задача 52. Как раз из комментариев к статье https://forum.infostart.ru/forum9/topic164079/ , которая здесь упомянута. Просто более аккуратное, на мой взгляд решение, но не более быстрое.

Теперь, если нужно более быстрое решение для пересечения отрезков параллельных прямых при проецировании на одну прямую.
Здесь два пути:
исторически первый - дискретизация интервалов путем деления на наименьший интервал, чтобы затем определить общие куски группировкой. Это решает проблему квадратичной зависимости роста времени выполнения запроса от числа отрезков. Этот путь я планировал для быстрого ФИФО запросом.
Второй путь был найден позднее в статье Простой способ индексирования интервалов. На нем тоже можно основать быстрый запрос линейный по скорости. И он "красивее".

В общем алгоритме быстрого ФИФО запросом есть еще задача нахождения нарастающего итога.
Пока я искал (и нашел) способ "Баттерфляй" без предварительной нумерации, в запросах нумерация строк появилась (!!!). Это требует пересмотра многих ранее написанных запросов, которые с нумерацией решаются линейно по скорости.
Еще в несколько раз ускорить метод Баттерфляй позволяет экономия на записи во временные таблицы. Вывел формулу определения эффективных делителей в Баттерфляй, зависящую от соотношения затрат на запись и чтение.

Но все это осталось в черновиках, потому что явного большого интереса к выполнению таких вычислений именно в запросе я не увидел. К тому же нужно посмотреть как будет на этих задачах работать новая разработка 1С "Ускоритель аналитических запросов".
9. scientes 288 18.03.19 17:44 Сейчас в теме
(8)
в запросах нумерация строк появилась (!!!)

На какой версии платформы ?
10. ildarovich 7850 18.03.19 20:36 Сейчас в теме
(9) 8.3.13, функция называется АВТОНОМЕРЗАПИСИ()
buriZa; a45; PLAstic; gaglo; +4 Ответить
6. HAMMER_59 244 18.03.19 07:35 Сейчас в теме
Прочитал бегло статью - ничего не понял, но тема заманчивая. Почитал статьи по ссылкам.
Первая статья сводится к мысли: "вот если бы не было регистров накопления, тогда я бы выкрутился вот так".
Вторая статья, выдвигает тезис: "перебор всегда хуже чем запрос", довольно странное утверждение, т.к. запрос будет преобразован в план выполнения запроса, а там уже тот самый перебор, который хуже чем запрос. Понятно, что в одном случае выборки выполняются интерпритатором 1С, в другом случае скомпилированный код, но неужто прямо такие гигантские потери? В обсуждении статьи все прекрасно разобрано, в т.ч. про утверждения о великолепии использования хитровывернутых запросов.
Это же язык запросов, нам не надо задумываться как будут получены данные, нам главное написать запрос, север SQL сам разберется как лучше. Лично убеждался, даже на относительно простых запросах может и не разобраться, причем самое приятное, что в одном случае результат запроса будет формироваться мгновенно, а в другом случае тот же самый запрос будет выполняться несколько минут.
7. graphbuh 254 18.03.19 16:25 Сейчас в теме
Можно использовать критерий квадратного трехчлена - если х лежит в интервале х2, х3, то (х-х2)(х-х3)<0
11. monkbest 115 19.03.19 09:23 Сейчас в теме
Вроде понятно, но перечитал еще раз и стало непонятно:)

Откуда у нас координаты каждого отрезка, чтобы писать такие условия? У нас есть только индекс отрезка (дата документа) и длина отрезка (количество товара). Ни начала ни конца у нас нет

Для того, чтобы понять координаты начала и конца отрезков текущих остатков нам надо узнать длины предыдущих, которые мы списали 10 лет назад, т.е. вытянуть в запрос всю историю данного товара от начала ведения базы по приходам и расходам, а это уже такое себе решение.

Или я что-то не уловил? Ткните в меня своей мыслью еще раз, очень интересно.
12. scientes 288 19.03.19 16:01 Сейчас в теме
(11) Добавил в статью пример для задачи Ячейки и Товары. Для списания по партиям аналогично. Получаем остатки по партиям на начальную дату, добавляем в список приходы. Это первое множество. Второе множество получаем из расходных накладных.
13. monkbest 115 20.03.19 09:12 Сейчас в теме
(12) ну т.е. получаем срез на какую-то дату обычным способом из регистра накопления, а от него уже отрезками. Понял
14. PLAstic 295 04.04.19 17:58 Сейчас в теме
Хотел бы отметить, что получать последовательности отрезков можно и запросом.
ВЫБРАТЬ
	Задания.Ключ КАК Ключ,
	Задания.РасходГСМ КАК РасходГСМ
ПОМЕСТИТЬ ВТРасход
ИЗ
	Документ.ВыполнениеРабот.Задания КАК Задания
ГДЕ
	Задания.Ссылка = &Ссылка
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	ВТРасход.Ключ КАК Ключ,
	СУММА(ЕСТЬNULL(ВТРасход2.РасходГСМ, 0)) КАК НачОстаток,
	СУММА(ЕСТЬNULL(ВТРасход2.РасходГСМ, 0) + ВТРасход.РасходГСМ) КАК КонОстаток
ПОМЕСТИТЬ ВТИндексыРасхода
ИЗ
	ВТРасход КАК ВТРасход
		ЛЕВОЕ СОЕДИНЕНИЕ ВТРасход КАК ВТРасход2
		ПО (ВТРасход2.Ключ < ВТРасход.Ключ)

СГРУППИРОВАТЬ ПО
	ВТРасход.Ключ
Показать


И да, АВТОНОМЕРЗАПИСИ() позволяет весь пример сделать запросом без кода.
15. PLAstic 295 04.04.19 18:48 Сейчас в теме
(14) Текст запроса неправильный, КонОстаток считает неправильно.
16. user1226970 31.03.20 14:15 Сейчас в теме
А как это будет выглядеть ,если отрезки это даты?
Оставьте свое сообщение