Суть: получаю с сервера сущности, представляющие собой временные интервалы с датой начала и конца. Интервалы могут пересекаться, включаться и не быть таковыми, то есть не пересекаться, а находится на расстоянии, при этом дата конца первого меньше даты начала второго. Ну думаю понятно. Мне необходимо слить вместе пересекающиеся и включающие интервалы, чтобы у меня получились только не пересекающиеся. Сложность в том, что их очень много поэтому я ищу мат аппарат, который мог бы это оптимизировать. Нужен именно какой-то известный алгоритм что ли.
Заранее благодарю за любые подсказки.
новые сообщения
ответы на мои сообщения
избранное
скрытые темы
случайный топик
ёбнуть всё в новых вкладках
Форум → Программирование → Общие вопросы программирования → Ищу быстрый алгоритм
Ищу быстрый алгоритм
-
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
-
Сообщения:
5147
Репутация:
N
Группа:
в ухо
Янв. 14, 2016, 2:34 п.п., спустя 20 минут 47 секунд
не знаю спец. алгоритмов, а помочь ускорить поиск могу [ попытаться ].
во первых, большинство людей не знают как эффективно сравнивать два интервала. см.
во вторых, можно написать такой джойн с той же таблицей, чтобы наложение было видно.а что с этим дальше делать, это уже контекст депендант, как говорится.
Пересечение временны́х диапазонов — R2-D2 buzz
artoodetoo.ru
Detect overlapping date ranges from the same table
I have a table with the following data PKey Start End Type ==== ===== === ==== 01 01/01/2010 14/01/2010 S 02 15
stackoverflow.com
ιιlllιlllι унц-унц -
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
Янв. 14, 2016, 4:25 п.п., спустя 1 час 51 минуту
@artoodetoo, спасибо большое. Я профтычил написать что нужен программный способ и это не касается SQL
-
Сообщения:
5147
Репутация:
N
Группа:
в ухо
Янв. 14, 2016, 5:23 п.п., спустя 58 минут 20 секунд
А больше деталей можешь выдать? Если эти получаемые интервалы идут строго по нарастающей (риалтайм какой-то), то достаточно получая смотреть крайнюю запись и либо апдейтить её, либо инсертить новую.
Если время дискретно, скажем, по 15 мин, то тоже может иметь значение..ιιlllιlllι унц-унц -
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
Янв. 14, 2016, 5:35 п.п., спустя 11 минут 18 секунд
@artoodetoo, они идут в произвольном порядке из разных источников и я их сам мержу и сортирую, в итоге есть события в которых во время которых в текущий набор вмерживаются загруженные
-
Сообщения:
3244
Репутация:
N
Группа:
Джедаи
Янв. 15, 2016, 2:56 д.п., спустя 9 часов 21 минуту 4 секунды
Мат аппарат:
1. Дано: множество A уже отфильтрованных (не пересекающихся и не дублирующихся) интервалов
2. На вход поступает один интервал D c границами Dmin, Dmax
3. Если множество А пустое - пушим D в A, гото 3, иначе идём дальше
4. В множестве A ищем интервалы I, каждый из которых удовлетворяет условию (Imin between Dmin and Dmax) OR (Imax between Dmin and Dmax), границы совпадения нестрогие, т.е. >=, <=
5. Ищем минимальную и максимальную границы для I объединённого с D, т.е. Nmin = min(Imin, Dmin), Nmax = max(Imax, Dmax)
6. Удаляем множество I
7. Записываем новый интервал N
8. Гото 2Спустя 164 сек.- [...] гото 2 [...]
Спустя 12 сек.да блять
Спустя 11 сек.в п.3 гото 2
Спустя 63 сек.В множестве A ищем интервалы I - значит I - тоже множество
Спустя 208 сек.Ну и в целом такое сложение обладает свойством коммутативности, то есть, можно разбить исходное множество интервалов на подмножества, по каждому подмножеству пройтись алгоритмом, потом складывать подмножества друг с другом.
Спустя 251 сек.ещё нужно определиться с временным шагом. если у нас шаг 1 секунда, то п.4 должен быть таким:
(Imin between Dmin and Dmax+1sec) OR (Imax between Dmin-1sec and Dmax)
чтобы объединять диапазоны 00:00:00..01:06:45 и 01:06:46..02:02:02
не всё полезно, что в swap полезло -
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
-
Сообщения:
3244
Репутация:
N
Группа:
Джедаи
Янв. 15, 2016, 5:11 п.п., спустя 21 минуту 7 секунд
рассуждения по поводу дальнейшей оптимизации:
- первым делом нужно будет отбросить интервалы, целиком лежащие внутри других интервалов. можно взять самые большие интервалы и просеять через них все остальные. с оставшимися работать дальше
- быстрее всего обрабатываются данные, целиком влезающие в кэш процессора
- возьмём граничный случай, когда данных настолько много, что они не вмещаются в оперативную память
алгоритм тогда будет таким:
1 определеляем количество ядер процессора (m) и размер кэша L3
2 по количеству ядер создаём количество потоков P[P1..Pm]
3 для каждого потока берём из исходного множества B ну например по 5 интервалов, назовём их K1..K5
4 откусываем от множества B некое подмножество Z интервалов так, чтобы они вмещались в L3 или 0.9 L3, ну примерно
5 скармливаем потокам P множество Z на предмет следующей проверки, на примере одного потока
-- for I in Z
--- for k in K
---- если I целиком входит в k - то I просто удаляем. если объединяется - то расширяем k и удаляем I, если не входит ни в один из k - то добавляем I к K
6 гото 4
7 после некоторого количества итераций 4-6 (например, после 1000) берём множества с потоков 2..m и скармливаем их в поток 1, затем проверяем K на взаимопересечение и объединяем при необходимостито есть получаем что-то вроде reduce. прогоняем все интервалы за один проход и на выходе получаем целевое отфильтрованное множество. если в какой-то момент после шага 7 размер множества K (в байтах) будет больше L3 - то можно взять половину K (состоящую из меньших интервалов) и положить её в какой-нибудь промежуточный массив. цель первой фильтрации - убрать мелкие интервалы.
Спустя 152 сек.второй алгоритм разумеется будет на порядки быстрее первого, особенно если не прибегать ни к каким SQL
Спустя 38 сек.но это для задач, где интервалов прям реально дохуя и минуты стоят дорого
не всё полезно, что в swap полезло -
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
Янв. 15, 2016, 5:31 п.п., спустя 20 минут 13 секунд
@master, ок спасибо, насчет железа я не рассматриваю оптимизацию, думаю можно держать отсортированные интервалы, и перебирать отсортированный пакет пришеджих, бинарным поиском найти место куда попадает первый пришедший и соотвественно вмержить, вставить или силить, и так пока не кончится пакет.
-
Сообщения:
3131
Репутация:
N
Группа:
в ухо
Янв. 15, 2016, 5:31 п.п., спустя 12 секунд
На чём писать то надо? На сях?
Один процесс и все интервалы в памяти лежат?
Или их тоже где-то сохранять надо, а потом извлекать?
-
Сообщения:
5210
Репутация:
N
Группа:
Джедаи
Янв. 15, 2016, 5:41 п.п., спустя 9 минут 52 секунды
На чём писать то надо? На сях?
Один процесс и все интервалы в памяти лежат?
Или их тоже где-то сохранять надо, а потом извлекать?
@vasa_c, можно на сях, но я буду писать на Obj-c, там можно на С писать. Можно распараллелить, но пока условия проще, так что один поток, и всё в памяти.
Пожалуйста, авторизуйтесь, чтобы написать комментарий!