ФорумПрограммированиеОбщие вопросы программирования → Ищу быстрый алгоритм

Ищу быстрый алгоритм

  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 14 января 2016 г. 3:13

    Суть: получаю с сервера сущности, представляющие собой временные интервалы с датой начала и конца. Интервалы могут пересекаться, включаться и не быть таковыми, то есть не пересекаться, а находится на расстоянии, при этом дата конца первого меньше даты начала второго. Ну думаю понятно. Мне необходимо слить вместе пересекающиеся и включающие интервалы, чтобы у меня получились только не пересекающиеся. Сложность в том, что их очень много поэтому я ищу мат аппарат, который мог бы это оптимизировать. Нужен именно какой-то известный алгоритм что ли.
    Заранее благодарю за любые подсказки.

  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 14 января 2016 г. 3:34, спустя 20 минут 47 секунд

    не знаю спец. алгоритмов, а помочь ускорить поиск могу [ попытаться ].
    во первых, большинство людей не знают как эффективно сравнивать два интервала. см. Пересечение временны́х диапазонов — R2-D2 buzz [artoodetoo.ru]
    во вторых, можно написать такой джойн с той же таблицей, чтобы наложение было видно. Detect overlapping date ranges from the same table [stackoverflow.com]

    а что с этим дальше делать, это уже контекст депендант, как говорится.

    ιιlllιlllι унц-унц
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 14 января 2016 г. 5:25, спустя 1 час 51 минуту

    @artoodetoo, спасибо большое. Я профтычил написать что нужен программный способ и это не касается SQL

  • artoodetoo

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 14 января 2016 г. 6:23, спустя 58 минут 20 секунд

    А больше деталей можешь выдать? Если эти получаемые интервалы идут строго по нарастающей (риалтайм какой-то), то достаточно получая смотреть крайнюю запись и либо апдейтить её, либо инсертить новую.
    Если время дискретно, скажем, по 15 мин, то тоже может иметь значение..

    ιιlllιlllι унц-унц
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 14 января 2016 г. 6:35, спустя 11 минут 18 секунд

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

  • master

    Сообщения: 3244 Репутация: N Группа: Джедаи

    Spritz 14 января 2016 г. 15: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 сек.

    1. [...] гото 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 полезло
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 15 января 2016 г. 5:49, спустя 13 часов 53 минуты 42 секунды

    @master, ок, бинарный поиск в тему

  • master

    Сообщения: 3244 Репутация: N Группа: Джедаи

    Spritz 15 января 2016 г. 6: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 полезло
  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 15 января 2016 г. 6:31, спустя 20 минут 13 секунд

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

  • vasa_c

    Сообщения: 3131 Репутация: N Группа: в ухо

    Spritz 15 января 2016 г. 6:31, спустя 12 секунд

    На чём писать то надо? На сях?

    Один процесс и все интервалы в памяти лежат?

    Или их тоже где-то сохранять надо, а потом извлекать?

  • kostyl

    Сообщения: 5210 Репутация: N Группа: Джедаи

    Spritz 15 января 2016 г. 6:41, спустя 9 минут 52 секунды

    На чём писать то надо? На сях?

    Один процесс и все интервалы в памяти лежат?

    Или их тоже где-то сохранять надо, а потом извлекать?

    @vasa_c, можно на сях, но я буду писать на Obj-c, там можно на С писать. Можно распараллелить, но пока условия проще, так что один поток, и всё в памяти.

Пожалуйста, авторизуйтесь, чтобы написать комментарий!