Приветствую.
В табличке накопились временные отрезки и сейчас хочется посчитать количество дней, которые покрывались хотя бы одним отрезком (начало или конец отрезка — включительно).
Погуглил — находится алгоритм "сканирующей прямой". Например, тут: Длина объединения отрезков
1. Получается, нужно делать выборку всех данных? Так данных может быть много, то, думаю, будет проще не делать предварительную сортировку, а тупо идти по дням, выбирая самые длинные отрезки.
2. Может есть лучше алгоритм?
Здравствуйте, Real 3L0, Вы писали:
R3>Приветствую. R3>В табличке накопились временные отрезки и сейчас хочется посчитать количество дней, которые покрывались хотя бы одним отрезком (начало или конец отрезка — включительно). R3>Погуглил — находится алгоритм "сканирующей прямой". Например, тут: Длина объединения отрезков R3>1. Получается, нужно делать выборку всех данных? Так данных может быть много, то, думаю, будет проще не делать предварительную сортировку, а тупо идти по дням, выбирая самые длинные отрезки. R3>2. Может есть лучше алгоритм?
Тут сложно что-то подсказать, не видя как у вас организованы данные
Здравствуйте, Real 3L0, Вы писали:
R3>Здравствуйте, BlackEric, Вы писали:
BE>>Тут сложно что-то подсказать, не видя как у вас организованы данные
R3>SQLite. Одна таблица. Два поля в формате DATETIME.
Насколько я понимаю, если отрезки перекрываются, без сортировки нормально работать не будет.
Здравствуйте, BlackEric, Вы писали:
BE>Насколько я понимаю, если отрезки перекрываются, без сортировки нормально работать не будет.
Если количество записей большое, то может быть попадос по памяти.
Если уж всё равно идти перебором по всем записям то, по-моему, проще без сортировки, а тупо поиском:
1. берём самый первый отрезок (и самый длинный)
2. считаем его дни
3. берём отрезок, в который попадает конец предыдущего отрезка
3.1. если такого нет, то берём следующий ближайший отрезок (и самый длинный)
4. считаем его дни
5. go to 3.
Тут не нужно на клиента выгружать все отрезки, но нужно больше обращаться в БД.
Здравствуйте, Olaf, Вы писали:
O>А в чем заключается задача? Не уверен, что правильно понял. O>Существует набор отрезков времени t1 и t2. Необходимо найти непрерывную последовательность таких отрезков?
посчитать количество дней, которые покрывались хотя бы одним отрезком
Здравствуйте, Real 3L0, Вы писали:
R3>Если уж всё равно идти перебором по всем записям то, по-моему, проще без сортировки, а тупо поиском: R3>1. берём самый первый отрезок (и самый длинный)
А чтоб отрезок был и первый и самый длинный, что обеспечит?
Здравствуйте, Real 3L0, Вы писали:
R3>Приветствую. R3>В табличке накопились временные отрезки и сейчас хочется посчитать количество дней, которые покрывались хотя бы одним отрезком (начало или конец отрезка — включительно). R3>Погуглил — находится алгоритм "сканирующей прямой". Например, тут: Длина объединения отрезков R3>1. Получается, нужно делать выборку всех данных? Так данных может быть много, то, думаю, будет проще не делать предварительную сортировку, а тупо идти по дням, выбирая самые длинные отрезки. R3>2. Может есть лучше алгоритм?
я бы пробовал 2 варианта:
первый — с индексированными столбцами
Создаём временную таблицу с календарём
DAY_ID DAY_start DAY_end
01/01/2020 — 01/01/2020 00:00:00 — 01/01/2020 23:59:59
...
31/12/2023 — 31/12/2023 00:00:00 — 31/12/2023 23:59:59
Выбирем день если начало или конец дня между началом и концом отрезков.
На год 366 записей. Соответственно 366+366 индексированных поисков на год.
На выходе — дни по которым были записи.
Второй
Группировка по начальному дню и максимальному для начала дню окончания.
Для записей типа
01/01/2020 07:11:22 — 23/02/2020 14:36:27
01/01/2020 12:36:45 — 08/03/2020 14:36:27
вводим функции начала и конца дня
для начала обрезаем время а концу устанавливаем окончание дня
группируем по началу дня начала и максимальному окончанию дня окончания
На выходе группировки получим для каждого дня начала
01/01/2020 00:00:00 — 08/03/2020 23:59:59
для года на выходе не более 365 записей.
В конце уже можно по первому варианту по календарю пройтись.
если точность нужна на доли секунды, то рассмотреть вариант с полуоткрытыми интервалами [начало; конец).
DAY_ID DAY_start DAY_end
01/01/2020 — 01/01/2020 00:00:00 — 02/01/2020 00:00:00
Здравствуйте, Real 3L0, Вы писали:
R3>посчитать количество дней, которые покрывались хотя бы одним отрезком
Мы можем посчитать количество дней на одном отрезке t2 — t1 в днях.
Не могу понять, как связаны остальные отрезки друг с другом в рамках этой задачи, т.е. что нужно сделать дальше, зная разницу в днях на каждом отрезке.
Здравствуйте, Real 3L0, Вы писали:
R3>Здравствуйте, paucity, Вы писали:
P>>Я конечно давно не брал в руки шашек, но разве Order — не сортировка, которой ты хочешь избежать?
R3>Я хотел избежать выгрузки всех данных на клиента. А это — просто получение одной записи.
Так и алгоритм "сканирующей прямой" тоже на клиент вернёт тебе только одно число, а сортировка и обработка будет на стороне sql сервера делаться. Непонятно, что ещё на клиента ты хочешь получать.
Пример для таблицы Intervals(A, B) с полуоткрытыми целочисленными интервалами:
WITH
Bounds(Point, Diff) AS (
SELECT A AS Point, 1 as Diff from Intervals
UNION ALL
SELECT B AS Point, -1 as Diff from Intervals
),
Balance(IntervalBalance, IntervalLength) AS (
SELECT
SUM(Diff) OVER w0 AS IntervalBalance,
Point - lag(Point) OVER w0 as IntervalLength
FROM Bounds
WINDOW w0 AS (ORDER BY Point ASC, Diff DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW EXCLUDE CURRENT ROW)
)
SELECT SUM(IntervalLength) As LengthOfUnion FROM Balance WHERE IntervalBalance > 0;
(в зависимости от объёма и движка, на практике можно ещё PARTITION BY в окно, очевидно, добавить, чтобы обрабатывать непересекающиеся части таблицы параллельно, но идея и так должна быть понятна)
Здравствуйте, tsitan, Вы писали:
T>первый — с индексированными столбцами T>Создаём временную таблицу с календарём
Да, думал про создание дополнительной таблицы с днями. Вариант всем хорош, кроме того, что нужно её поддерживать в актуальном состоянии.
T>Второй T>Группировка по начальному дню и максимальному для начала дню окончания. T>для года на выходе не более 365 записей.
Здравствуйте, watchmaker, Вы писали:
W>Так и алгоритм "сканирующей прямой" тоже на клиент вернёт тебе только одно число, а сортировка и обработка будет на стороне sql сервера делаться.
Нет. Там в алгоритме нужно идти по прямой времени и делать n++, если отрезок начался, и n--, если отрезок кончился.
Соответственно, если в дне n>0, то этот день считаем.
Здравствуйте, Real 3L0, Вы писали: R3>Нет. Там в алгоритме нужно идти по прямой времени и делать n++, если отрезок начался, и n--, если отрезок кончился. R3>Соответственно, если в дне n>0, то этот день считаем.
Решение от watchmaker делает именно это. Только на стороне сервера, а не на стороне клиента.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, watchmaker, Вы писали:
W>Пример для таблицы Intervals(A, B) с полуоткрытыми целочисленными интервалами: W>
WITH
W> Bounds(Point, Diff) AS (
W> SELECT A AS Point, 1 as Diff from Intervals
W> UNION ALL
W> SELECT B AS Point, -1 as Diff from Intervals
W> ),
W> Balance(IntervalBalance, IntervalLength) AS (
W> SELECT
W> SUM(Diff) OVER w0 AS IntervalBalance,
W> Point - lag(Point) OVER w0 as IntervalLength
W> FROM Bounds
W> WINDOW w0 AS (ORDER BY Point ASC, Diff DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW EXCLUDE CURRENT ROW)
W> )
W>SELECT SUM(IntervalLength) As LengthOfUnion FROM Balance WHERE IntervalBalance > 0;
W>
Спасибо, начинает доходить идея.
Правда, я с оконными функциями не дружу.
В таком виде запрос возвращает 0, хотя данные точно есть.
A и B — имеют тип datetime (sqlite).
Нужно учитывать, что если:
* A и B находятся в одном и том же дне, то этот день тоже считаем;
* A и B находятся в разных днях, то эти дни считаем включительно.
