Алгоритм оптимального интервала работы - PullRequest
Новая
       7

Алгоритм оптимального интервала работы

0 голосов
/ 24 сентября 2018

Допустим, у вас есть разные задания, которые вам нужно регулярно выполнять (например, вы хотите выполнять вызовы API для разных конечных точек).Допустим, вам нужно достичь двух разных конечных точек и вы хотите, чтобы ваши звонки были как можно дальше друг от друга.

Пример: у вас есть два задания, одно запускается раз в минуту, другое запускаетсядважды в минуту.

Решение: запустить задание A с интервалом 60 секунд, подождать 15 секунд, запустить задание B с интервалом 30 секунд.Таким образом, задания будут выполняться в считанные секунды: 0 (задание A), 15 (задание B), 45 (задание B), 60 (задание A), 75 (задание B), 105 (задание B), 120 (задание A)... сделать максимальный интервал между вызовами API 15 секунд при сохранении необходимой нам частоты вызовов.

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

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

Спасибо

1 Ответ

0 голосов
/ 24 сентября 2018

Вот мое решение, если мы допустим, чтобы интервалы были немного неравными.

Предположим, что наши вызовы A[0], A[1], ..., A[n] с частотами f[0],f[1], ..., f[n], где все частоты находятся в одной единице.Например, 60 / час, 120 / час и т. Д.

Общая частота, с которой происходят события, будет f = f[0] + f[1] + ... + f[n], что означает, что некоторые события будут планироваться каждые hour/f с интервалом времени.Вопрос в том, что произойдет, когда.

Способ представить это - представить, что у нас есть ряд ведер, наполненных водой.Каждый раз, когда мы будем сбрасывать единицу воды из самого полного ведра перед нами.

Поскольку в самом начале нам все равно, с чего начать, давайте инициализируем вектор чисел, просто назначая случайные числаих, full[0], full[1], ..., full[n].И теперь наш алгоритм выглядит так: псевдокод: 

Every hour/f time apart:
    for each i in 0..n:
        fill[i] += f[i]/f
    i_choice = (select i from 0..n with the largest f[i])
    fill[i_choice] -= 1
    Do event A[i_choice]

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

...