Сглаживание пересекающихся промежутков времени - PullRequest
Новая
       10

Сглаживание пересекающихся промежутков времени

15 голосов
/ 08 июня 2009

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

Чтобы прояснить ситуацию, взгляните на пример данных за 03.06.2009:

Следующие промежутки времени перекрываются или непрерывны и должны объединиться в один промежуток времени

  • 05: 54: 48 - 10: 00: 13
  • 09: 26: 45 - 09: 59: 40

Результирующий временной интервал будет с 05:54:48 до 10:00:13. Поскольку между 10:00:13 и 10:12:50 существует разрыв, у нас также есть следующие временные интервалы:

  • 10: 12: 50 - 10: 27: 25
  • 10: 13: 12 - 11: 14: 56
  • 10: 27: 25 - 10: 27: 31
  • 10: 27: 39 - 13: 53: 38
  • 11: 14: 56 - 11: 15: 03
  • 11: 15: 30 - 14: 02: 14
  • 13: 53: 38 - 13: 53: 43
  • 14: 02: 14 - 14: 02: 31

, что приводит к одному объединенному промежутку времени с 10:12:50 до 14:02:31, поскольку они перекрываются или соседствуют.

Ниже вы найдете пример данных и сведенные данные, как мне было бы нужно. Колонка продолжительности просто информативна.

Любое решение - будь то SQL или нет - приветствуется.

РЕДАКТИРОВАТЬ : Поскольку существует множество разных и интересных решений, я уточняю свой первоначальный вопрос, добавляя ограничения, чтобы увидеть, как "лучшее" (если оно есть) решение всплывет:

  • Я получаю данные через ODBC из другой системы. Для меня нет способа изменить макет таблицы или добавить индексы
  • Данные индексируются только по столбцу даты (временной части нет)
  • На каждый день около 2,5 тыс. Строк
  • Примерная схема использования данных примерно следующая:
    • Большую часть времени (скажем, 90%) пользователь будет запрашивать только один или два дня (строки от 2,5 до 5 тысяч)
    • Иногда (9%) диапазон может составлять до месяца (~ 75 тыс. Строк)
    • Редко (1%) диапазон будет до года (~ 900 тыс. Строк)
  • Запрос должен быть быстрым для типичного случая, а не "вечным" для редкого случая.
  • Запрос данных за год занимает около 5 минут (простой выбор без объединений)

В рамках этих ограничений, что было бы лучшим решением? Боюсь, что большинство решений будут ужасно медленными, так как они объединяются по комбинации даты и времени, что в моем случае не является индексным полем.

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

Пример данных: 

Date       | Start    | Stop
-----------+----------+---------
02.06.2009 | 05:55:28 | 09:58:27
02.06.2009 | 10:15:19 | 13:58:24
02.06.2009 | 13:58:24 | 13:58:43
03.06.2009 | 05:54:48 | 10:00:13
03.06.2009 | 09:26:45 | 09:59:40
03.06.2009 | 10:12:50 | 10:27:25
03.06.2009 | 10:13:12 | 11:14:56
03.06.2009 | 10:27:25 | 10:27:31
03.06.2009 | 10:27:39 | 13:53:38
03.06.2009 | 11:14:56 | 11:15:03
03.06.2009 | 11:15:30 | 14:02:14
03.06.2009 | 13:53:38 | 13:53:43
03.06.2009 | 14:02:14 | 14:02:31
04.06.2009 | 05:48:27 | 09:58:59
04.06.2009 | 06:00:00 | 09:59:07
04.06.2009 | 10:15:52 | 13:54:52
04.06.2009 | 10:16:01 | 13:24:20
04.06.2009 | 13:24:20 | 13:24:24
04.06.2009 | 13:24:32 | 14:00:39
04.06.2009 | 13:54:52 | 13:54:58
04.06.2009 | 14:00:39 | 14:00:49
05.06.2009 | 05:53:58 | 09:59:12
05.06.2009 | 10:16:05 | 13:59:08
05.06.2009 | 13:59:08 | 13:59:16
06.06.2009 | 06:04:00 | 10:00:00
06.06.2009 | 10:16:54 | 10:18:40
06.06.2009 | 10:18:40 | 10:18:45
06.06.2009 | 10:23:00 | 13:57:00
06.06.2009 | 10:23:48 | 13:57:54
06.06.2009 | 13:57:21 | 13:57:38
06.06.2009 | 13:57:54 | 13:57:58
07.06.2009 | 21:59:30 | 01:58:49
07.06.2009 | 22:12:16 | 01:58:39
07.06.2009 | 22:12:25 | 01:58:28
08.06.2009 | 02:10:33 | 05:56:11
08.06.2009 | 02:10:43 | 05:56:23
08.06.2009 | 02:10:49 | 05:55:59
08.06.2009 | 05:55:59 | 05:56:01
08.06.2009 | 05:56:11 | 05:56:14
08.06.2009 | 05:56:23 | 05:56:27

Сведенный результат: 

Date       | Start    | Stop     | Duration
-----------+----------+----------+---------
02.06.2009 | 05:55:28 | 09:58:27 | 04:02:59
02.06.2009 | 10:15:19 | 13:58:43 | 03:43:24
03.06.2009 | 05:54:48 | 10:00:13 | 04:05:25
03.06.2009 | 10:12:50 | 14:02:31 | 03:49:41
04.06.2009 | 05:48:27 | 09:59:07 | 04:10:40
04.06.2009 | 10:15:52 | 14:00:49 | 03:44:58
05.06.2009 | 05:53:58 | 09:59:12 | 04:05:14
05.06.2009 | 10:16:05 | 13:59:16 | 03:43:11
06.06.2009 | 06:04:00 | 10:00:00 | 03:56:00
06.06.2009 | 10:16:54 | 10:18:45 | 00:01:51
06.06.2009 | 10:23:00 | 13:57:58 | 03:34:58
07.06.2009 | 21:59:30 | 01:58:49 | 03:59:19
08.06.2009 | 02:10:33 | 05:56:27 | 03:45:54

Ответы [ 7 ]

7 голосов
/ 08 июня 2009

Вот решение только для SQL. Я использовал DATETIME для столбцов. Хранение времени отдельно, по моему мнению, является ошибкой, так как у вас будут проблемы, когда время пройдет после полуночи. Вы можете настроить это, чтобы справиться с этой ситуацией, хотя, если вам нужно. Решение также предполагает, что время начала и окончания НЕ НЕДЕЙСТВИТЕЛЬНО. Опять же, вы можете настроить при необходимости, если это не так.

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

Результаты соответствуют вашим ожидаемым результатам, за исключением одного случая, когда проверка вручную выглядит так, как будто вы допустили ошибку в ожидаемом результате. 6-го числа должен быть промежуток, который заканчивается в 2009-06-06 10: 18: 45.000. 

SELECT
     ST.start_time,
     ET.end_time
FROM
(
     SELECT
          T1.start_time
     FROM
          dbo.Test_Time_Spans T1
     LEFT OUTER JOIN dbo.Test_Time_Spans T2 ON
          T2.start_time < T1.start_time AND
          T2.end_time >= T1.start_time
     WHERE
          T2.start_time IS NULL
) AS ST
INNER JOIN
(
     SELECT
          T3.end_time
     FROM
          dbo.Test_Time_Spans T3
     LEFT OUTER JOIN dbo.Test_Time_Spans T4 ON
          T4.end_time > T3.end_time AND
          T4.start_time <= T3.end_time
     WHERE
          T4.start_time IS NULL
) AS ET ON
     ET.end_time > ST.start_time
LEFT OUTER JOIN
(
     SELECT
          T5.end_time
     FROM
          dbo.Test_Time_Spans T5
     LEFT OUTER JOIN dbo.Test_Time_Spans T6 ON
          T6.end_time > T5.end_time AND
          T6.start_time <= T5.end_time
     WHERE
          T6.start_time IS NULL
) AS ET2 ON
     ET2.end_time > ST.start_time AND
     ET2.end_time < ET.end_time
WHERE
     ET2.end_time IS NULL
4 голосов
/ 09 июня 2009

В MySQL: 

SELECT  grouper, MIN(start) AS group_start, MAX(end) AS group_end
FROM    (
        SELECT  start,
                end,
                @r := @r + (@edate < start) AS grouper,
                @edate := GREATEST(end, CAST(@edate AS DATETIME))
        FROM    (
                SELECT  @r := 0,
                        @edate := CAST('0000-01-01' AS DATETIME)
                ) vars,
                (
                SELECT  rn_date + INTERVAL TIME_TO_SEC(rn_start) SECOND AS start,
                        rn_date + INTERVAL TIME_TO_SEC(rn_end) SECOND + INTERVAL (rn_start > rn_end) DAY AS end
                FROM    t_ranges
                ) q
        ORDER BY
                start
        ) q
GROUP BY
        grouper
ORDER BY
        group_start

То же решение для SQL Server описано в следующей статье в моем блоге:

Вот функция для этого: 

DROP FUNCTION fn_spans
GO
CREATE FUNCTION fn_spans(@p_from DATETIME, @p_till DATETIME)
RETURNS @t TABLE
        (
        q_start DATETIME NOT NULL,
        q_end DATETIME NOT NULL
        )
AS
BEGIN
        DECLARE @qs DATETIME
        DECLARE @qe DATETIME
        DECLARE @ms DATETIME
        DECLARE @me DATETIME
        DECLARE cr_span CURSOR FAST_FORWARD
        FOR
        SELECT  s_date + s_start AS q_start,
                s_date + s_stop + CASE WHEN s_start < s_stop THEN 0 ELSE 1 END AS q_end
        FROM    t_span
        WHERE   s_date BETWEEN @p_from - 1 AND @p_till
                AND s_date + s_start >= @p_from
                AND s_date + s_stop <= @p_till
        ORDER BY
                q_start
        OPEN    cr_span
        FETCH   NEXT
        FROM    cr_span
        INTO    @qs, @qe
        SET @ms = @qs
        SET @me = @qe
        WHILE @@FETCH_STATUS = 0
        BEGIN
                FETCH   NEXT
                FROM    cr_span
                INTO    @qs, @qe
                IF @qs > @me
                BEGIN
                        INSERT
                        INTO    @t
                        VALUES (@ms, @me)
                        SET @ms = @qs
                END
                SET @me = CASE WHEN @qe > @me THEN @qe ELSE @me END
        END
        IF @ms IS NOT NULL 
        BEGIN
                INSERT
                INTO    @t
                VALUES  (@ms, @me)
        END
        CLOSE   cr_span
        RETURN
END

Поскольку в SQL Server отсутствует простой способ ссылки на ранее выбранные строки в наборе результатов, это один из редких случаев, когда курсоры в SQL Server работают быстрее, чем решения на основе набора.

Проверено на 1,440,000 строках, работает в течение 24 секунд для полного набора и почти мгновенно для диапазона дня или двух.

Обратите внимание на дополнительное условие в запросе SELECT: 

s_date BETWEEN @p_from - 1 AND @p_till

Это кажется избыточным, но на самом деле это грубый фильтр, который позволяет использовать ваш индекс на s_date.

3 голосов
/ 08 июня 2009

Аналогичный вопрос по SO здесь:

Минимальный срок действия и срок действия для смежных дат

FWIW Я проголосовал за рекомендацию Джо Селко «SQL для умников», третье издание, повтор: третье издание (2005 г.), в котором обсуждаются различные подходы, набор базовых и процедурных.

2 голосов
/ 08 июня 2009

Предполагая, что вы:

  • имеет какой-то простой пользовательский объект Date, в котором хранятся дата / время начала и дата / время окончания
  • возвращает строки в отсортированном порядке (по дате / времени начала) в виде списка, L , из этих дат
  • хочу создать сводный список дат, F

Выполните следующие действия: 

first = first row in L
flat_date.start = first.start, flat_date.end = first.end
For each row in L:
    if row.start < flat_date.end and row.end > flat_date.end: // adding on to a timespan
        flat_date.end = row.end
    else: // ending a timespan and starting a new one
        add flat_date to F
        flat_date.start = row.start, flat_date.end = row.end
add flat_date to F // adding the last timespan to the flattened list
1 голос
/ 08 июня 2009

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

создать тестовые данные: 

create table t1 (d1 datetime, d2 datetime)

insert t1 (d1,d2)
    select           '2009-06-03 10:00:00', '2009-06-03 14:00:00'
    union all select '2009-06-03 13:55:00', '2009-06-03 18:00:00'
    union all select '2009-06-03 17:55:00', '2009-06-03 23:00:00'
    union all select '2009-06-03 22:55:00', '2009-06-04 03:00:00'

    union all select '2009-06-04 03:05:00', '2009-06-04 07:00:00'

    union all select '2009-06-04 07:05:00', '2009-06-04 10:00:00'
    union all select '2009-06-04 09:55:00', '2009-06-04 14:00:00'

рекурсивный CTE: 

;with dateRanges (ancestorD1, parentD1, d2, iter) as
(
--anchor is first level of collapse
    select
        d1 as ancestorD1,
        d1 as parentD1,
        d2,
        cast(0 as int) as iter
    from t1

--recurse as long as there is another range to fold in
    union all select
        tLeft.ancestorD1,
        tRight.d1 as parentD1,
        tRight.d2,
        iter + 1  as iter
    from dateRanges as tLeft join t1 as tRight
        --join condition is that the t1 row can be consumed by the recursive row
        on tLeft.d2 between tRight.d1 and tRight.d2
            --exclude identical rows
            and not (tLeft.parentD1 = tRight.d1 and tLeft.d2 = tRight.d2)
)
select
    ranges1.*
from dateRanges as ranges1
where not exists (
    select 1
    from dateRanges as ranges2
    where ranges1.ancestorD1 between ranges2.ancestorD1 and ranges2.d2
        and ranges1.d2 between ranges2.ancestorD1 and ranges2.d2
        and ranges2.iter > ranges1.iter
)

Дает вывод: 

ancestorD1              parentD1                d2                      iter
----------------------- ----------------------- ----------------------- -----------
2009-06-04 03:05:00.000 2009-06-04 03:05:00.000 2009-06-04 07:00:00.000 0
2009-06-04 07:05:00.000 2009-06-04 09:55:00.000 2009-06-04 14:00:00.000 1
2009-06-03 10:00:00.000 2009-06-03 22:55:00.000 2009-06-04 03:00:00.000 3
0 голосов
/ 11 октября 2015

Расширяя ответ на MahlerFive, я написал быстрое расширение для DateTools. Пока он прошел все мои испытания. 

extension DTTimePeriodCollection {

    func flatten() {

        self.sortByStartAscending()

        guard let periods = self.periods() else { return }
        if periods.count < 1 { return }

        var flattenedPeriods = [DTTimePeriod]()
        let flatdate = DTTimePeriod()

        for period in periods {

            guard let periodStart = period.StartDate, let periodEnd = period.EndDate else { continue }

            if !flatdate.hasStartDate() { flatdate.StartDate = periodStart }
            if !flatdate.hasEndDate() { flatdate.EndDate = periodEnd }

            if periodStart.isEarlierThanOrEqualTo(flatdate.EndDate) && periodEnd.isGreaterThanOrEqualTo(flatdate.EndDate) {

                flatdate.EndDate = periodEnd

            } else {

                flattenedPeriods.append(flatdate.copy())
                flatdate.StartDate = periodStart
                flatdate.EndDate = periodEnd
            }
        }

        flattenedPeriods.append(flatdate.copy())

        // delete all periods
        for var i = 0 ; i < periods.count ; i++ { self.removeTimePeriodAtIndex(0) }

        // add flattened periods to self
        for flat in flattenedPeriods { self.addTimePeriod(flat) }
    }
0 голосов
/ 09 июня 2009

Чтобы помочь ответить на вопрос, вот пример данных, приведенных в вопросе в табличной переменной, такой как Hainstech: 

declare @T1 table (d1 datetime, d2 datetime)

insert @T1 (d1,d2)
select           '02 June 2009 05:55:28','02 June 2009 09:58:27'
union all select '02 June 2009 10:15:19','02 June 2009 13:58:24'
union all select '02 June 2009 13:58:24','02 June 2009 13:58:43'
union all select '03 June 2009 05:54:48','03 June 2009 10:00:13'
union all select '03 June 2009 09:26:45','03 June 2009 09:59:40'
union all select '03 June 2009 10:12:50','03 June 2009 10:27:25'
union all select '03 June 2009 10:13:12','03 June 2009 11:14:56'
union all select '03 June 2009 10:27:25','03 June 2009 10:27:31'
union all select '03 June 2009 10:27:39','03 June 2009 13:53:38'
union all select '03 June 2009 11:14:56','03 June 2009 11:15:03'
union all select '03 June 2009 11:15:30','03 June 2009 14:02:14'
union all select '03 June 2009 13:53:38','03 June 2009 13:53:43'
union all select '03 June 2009 14:02:14','03 June 2009 14:02:31'
union all select '04 June 2009 05:48:27','04 June 2009 09:58:59'
union all select '04 June 2009 06:00:00','04 June 2009 09:59:07'
union all select '04 June 2009 10:15:52','04 June 2009 13:54:52'
union all select '04 June 2009 10:16:01','04 June 2009 13:24:20'
union all select '04 June 2009 13:24:20','04 June 2009 13:24:24'
union all select '04 June 2009 13:24:32','04 June 2009 14:00:39'
union all select '04 June 2009 13:54:52','04 June 2009 13:54:58'
union all select '04 June 2009 14:00:39','04 June 2009 14:00:49'
union all select '05 June 2009 05:53:58','05 June 2009 09:59:12'
union all select '05 June 2009 10:16:05','05 June 2009 13:59:08'
union all select '05 June 2009 13:59:08','05 June 2009 13:59:16'
union all select '06 June 2009 06:04:00','06 June 2009 10:00:00'
union all select '06 June 2009 10:16:54','06 June 2009 10:18:40'
union all select '06 June 2009 10:18:40','06 June 2009 10:18:45'
union all select '06 June 2009 10:23:00','06 June 2009 13:57:00'
union all select '06 June 2009 10:23:48','06 June 2009 13:57:54'
union all select '06 June 2009 13:57:21','06 June 2009 13:57:38'
union all select '06 June 2009 13:57:54','06 June 2009 13:57:58'
union all select '07 June 2009 21:59:30','07 June 2009 01:58:49'
union all select '07 June 2009 22:12:16','07 June 2009 01:58:39'
union all select '07 June 2009 22:12:25','07 June 2009 01:58:28'
union all select '08 June 2009 02:10:33','08 June 2009 05:56:11'
union all select '08 June 2009 02:10:43','08 June 2009 05:56:23'
union all select '08 June 2009 02:10:49','08 June 2009 05:55:59'
union all select '08 June 2009 05:55:59','08 June 2009 05:56:01'
union all select '08 June 2009 05:56:11','08 June 2009 05:56:14'
union all select '08 June 2009 05:56:23','08 June 2009 05:56:27'
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...