День добрый,
Есть задача вести несколько различных графиков работ (график работы предприятия, график работы по должности, график работы отдела, график работы оборудования и т.д.). Пока есть идея описывать данные графики работ от общего к частностям, то есть задавать правила, а потом указывать для них исключения. Например указать что график работы компании с 9:00 до 18:00 с понедельника по пятницу, а потом указать праздничные и сокращенные дни. На самом деле все несколько сложнее, нет привязки к дням, а есть просто указание промежутков времени.
Исходя из данных требований был разработан прототип работы с графиками, но немного смущает скорость работы. Подсчет количества рабочего времени на год занимает 3 секунды (идет процесс преобразования правил в рабочие промежутки времени). Возможно алгоритм не оптимален и может быть оптимизирован, но вопрос не в этом
Есть ли какие нибудь алгоритмы или общие подходы к работе с календарями/графиками работы? Также есть потребность в пересечении, вычитании и пересечении графиков работы. Как правильно с этим работать и что можно почитать? Куда копать?
Заранее спасибо за разумные ответы
I>Также есть потребность в пересечении, вычитании и пересечении графиков работы.
Имелось ввиду: пересечение, вычитание и объединение графиков работы
Здравствуйте, intr13, Вы писали:
I>>Также есть потребность в пересечении, вычитании и пересечении графиков работы.
I>Имелось ввиду: пересечение, вычитание и объединение графиков работы
3 секунды много или мало — зависит от количества работ. Если там 100500 млрд. работ то достаточно быстро ) если 10 работ то медленно )
Возможно тип данных поможет сменить если это еще не сделано, все сводится к пересечению отрезков.
Например если взять дискретность 1 секунда то получаем в год 31536000 сек , обычного Int32 хватит на 132 года, но лучше сразу Int64 ).
Возможно имеет смысл секунды не считать, только минуты или по 5 минут. Врятли кто-то планирвать будет дело на 2 минуты или планировать встречу на 12.32
поэтому дискретность бери из практики.
Потом нужно будет сделать проецирование этой цифры в привычный формат, с учетом 29 февраля и учет перевода времени + возможны какие-то специфики для экзотических культур.
Все расчеты по пересечению работ будут сводится к расчету пересечения отрезков, что должно быть достаточно быстро
то есть на входе у тебя список отрезков — после обработки снова список отрезков который может быть больше или равен по кол-ву исходному.
например 2 варианта
без пересечения
|----------| работа1
|------------| работа 2
на выходе :
|----------| работа1
|------------| работа 2
с пересечением
|----------| работа1
|------------| работа 2
на выходе :
|--- | работа1
|-----| работа 1+работа2
|------| работа 2
P>3 секунды много или мало — зависит от количества работ. Если там 100500 млрд. работ то достаточно быстро ) если 10 работ то медленно )
Отрезков относительно немного порядка 1000. Сейчас основное время ест преобразование из правил в отрезки.
P>Возможно тип данных поможет сменить если это еще не сделано, все сводится к пересечению отрезков.
P>Например если взять дискретность 1 секунда то получаем в год 31536000 сек , обычного Int32 хватит на 132 года, но лучше сразу Int64 ).
P>Возможно имеет смысл секунды не считать, только минуты или по 5 минут. Врятли кто-то планирвать будет дело на 2 минуты или планировать встречу на 12.32
P>поэтому дискретность бери из практики.
P>Потом нужно будет сделать проецирование этой цифры в привычный формат, с учетом 29 февраля и учет перевода времени + возможны какие-то специфики для экзотических культур.
Дискретность отрезка равна секунде при задании правил, при преобразовании правил в отрезки дискретность получается в миллисекундах (стандартный тип данных — дата со временем). Возможно действительно стоит задуматься об использовании точки начала отсчета, смещения относительно нее и заданным типом дискретности.
P>Все расчеты по пересечению работ будут сводится к расчету пересечения отрезков, что должно быть достаточно быстро
А есть ли какие нибудь базовые алгоритмы или подходы к пересечению отрезков? Что нибудь есть почитать?
P>то есть на входе у тебя список отрезков — после обработки снова список отрезков который может быть больше или равен по кол-ву исходному.
Это в принципе понятно, у меня даже есть операция слияния следующих друг за другом отрезков. Я ее натравливаю на результат в конце работы основного алгоритма.
Здравствуйте, intr13, Вы писали:
P>>3 секунды много или мало — зависит от количества работ. Если там 100500 млрд. работ то достаточно быстро ) если 10 работ то медленно )
I>Отрезков относительно немного порядка 1000. Сейчас основное время ест преобразование из правил в отрезки.
Ну 1000 отрезков и 3 секунды это медленно.
I>Дискретность отрезка равна секунде при задании правил, при преобразовании правил в отрезки дискретность получается в миллисекундах (стандартный тип данных — дата со временем). Возможно действительно стоит задуматься об использовании точки начала отсчета, смещения относительно нее и заданным типом дискретности.
ну тут смотри , т.к. насколько я знаю формат datetime в части реализации это float формат ( зависит от библиотеки ) , поэтому лучше переходить к формату integer, при этом брать большую дискретность, 5 минут мне кажется самая минимальная должна быть. Ну или минута — версия для президента Медведева ( говорят у них там все по минутам расписано ), но не по миллисекундам это точно )
Ну и алгоритмы пересечения отрезков посмотри со сложностью n * log (n)
http://wiki.bks-tv.ru/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2
там
Пересечение отрезков (алгоритм Бентли — Оттманна) — поиск всех точек пересечения отрезков на плоскости O((n + k)logn), k — количество точек пересечения.
Алгоритм Чазелла — Эдельсбруннера — пересечение отрезков за O(k + nlogn).
http://rain.ifmo.ru/cat/view.php/vis/geometry/segment-intersection-2008/algorithm
I>Это в принципе понятно, у меня даже есть операция слияния следующих друг за другом отрезков. Я ее натравливаю на результат в конце работы основного алгоритма.
Вот кстати готовая opensource библиотека
http://alglib.sources.ru/
попробуй ее алгоритм использовать
