Гость
Форумы / Oracle [игнор отключен] [закрыт для гостей] / распределение периодов по непересекающимся группам / 4 сообщений из 4, страница 1 из 1
29.12.2020, 15:13
    #40032288
ln123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение периодов по непересекающимся группам
Есть таблица содержащая определенные периоды времени, нужно разбить эти периоды на группы таким образом что бы каждая группа содержала только не пересекающиеся периоды.
Количество групп должно быть минимальными.
model и match_recognize использовать нельзя т.к. решение должно работать и на Oracle и на Postgres

У меня получилось приблизительно такое решение:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
with t as
 (select 1 id, sysdate ds, sysdate + 10 de
    from dual
  union all
  select 2 id, sysdate + 5, sysdate + 15
    from dual
  union all
  select 3 id, sysdate + 11, sysdate + 16
    from dual
  union all
  select 4 id, sysdate + 12, sysdate + 17
    from dual
  union all
  select 5 id, sysdate + 12, sysdate + 17
    from dual
  union all
  select 6 id, sysdate + 18, sysdate + 19
    from dual
  --union all
  --select 7 id, sysdate + 18, sysdate + 19 from dual
  ),
t1 as
 (select t.*,
         lag(t.ds) over(order by ds) ds_prev,
         row_number() over(order by ds, de, id) r
    from t),
t2(id, ds, de, ds_prev, r, idroot, rroot) as
 (select id, ds, de, ds_prev, r, t1.id, t1.r
    from t1
  union all
  select t1.id, t1.ds, t1.de, t1.ds_prev, t1.r, t2.idroot, t2.rroot
    from t2
    join t1
      on t1.ds > t2.de
     and t1.ds_prev <= t2.de)
select t2.*, dense_rank() over(order by t2.idroot) gr
  from t2
 where not exists (select 1
          from t2 tt
         where t2.id = tt.id
           and tt.rroot < t2.rroot)



результат вроде похож на правду (поле gr содержит искомый номер группы для периода), но у решения есть ряд недостатков:
1. Оно не правильно будет работать для совпадающих по дате начала периодов (пример закомментированный период с id = 7) в принципе этот недостаток я могу обойти доработав данное решение
2. Боюсь что быстродействие у данного решения будет не очень хорошим, особенно учитывая что у меня будет порядка несколько сотен тысяч периодов и результат нужно получать достаточно быстро.

Введение дополнительного условия на начало ветвления (стоить дерево нужно только для периодов имеющих пересечения) конечно поможет, но возможно есть лучшие варианты или подходы?
...
Рейтинг: 0 / 0
29.12.2020, 15:24
    #40032304
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение периодов по непересекающимся группам
ln123,

для отладки легче воспринимаются диапазоны в числах

я б делал примерно так
1) обьеденил пересекающиеся
2)к-во групп будет равно максимальному к-ву диапазончиков в обьеденившем
3) переномеровал диапазночики в рамках обьедененных (порядковый номер ето искомая группа)

все

.....
stax
...
Рейтинг: 0 / 0
29.12.2020, 15:37
    #40032321
ln123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение периодов по непересекающимся группам
Stax,

Либо я вас не до конца понял либо так работать не будет.
Рассмотрим пример (для удобства числовой):

0-5, 4-7, 6-8

объединяем, получаем один период 0-8 в котором 3 периода т.е. при вашем подходе мы получаем 3 группы однако, их на самом деле 2: Первая 0-5 и 6-8 и вторая 4-7
...
Рейтинг: 0 / 0
29.12.2020, 15:44
    #40032323
Stax
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
распределение периодов по непересекающимся группам
ln123
Stax,

Либо я вас не до конца понял либо так работать не будет.


Вы правильно поняли, я был неправ

.....
stax
...
Рейтинг: 0 / 0
Форумы / Oracle [игнор отключен] [закрыт для гостей] / распределение периодов по непересекающимся группам / 4 сообщений из 4, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]