Алгоритм для вычисления следующего набора в последовательности

Question

Я ищу алгоритм для вычисления следующего набора операций в последовательности. Вот простое определение последовательности.

1. Задание 1А будет выполняться каждые 500 часов
2. Задание 2А будет выполняться каждые 1000 часов
3. Задание 3А будет выполняться каждые 1500 часов

Итак, при t = 500, сделайте 1А. При t = 1000 делайте 1A и 2A, при t = 1500 делайте 1A и 3A, но не 2A, поскольку 1500 не кратно 1000. Вы понимаете, как это сделать.

Было бы довольно легко, если бы у меня было время, но у меня нет. У меня есть история заданий (например, в прошлый раз было выполнено [1A + 2A]).

Знание последнего времени (например, [1A + 2A]) недостаточно для принятия решения:

• [1A + 2A] может быть при t = 1000: далее [1A + 3A] при t = 1500
• [1A + 2A] может быть при t = 5000: далее [1A] при t = 5500

Есть ли алгоритм для этого? Это похоже на знакомую проблему (какое-то сито?), Но я не могу найти решение.

Кроме того, он должен «масштабироваться», так как на самом деле у меня более 3 задач.

Answer 1

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

Answer 2

Последовательность должна повториться. Для данного примера последовательность будет 1А, 1А + 2А, 1А + 3А, 1А + 2А, 1А, 1А + 2А + 3А. В этой ситуации вы могли видеть, как далеко назад находятся последние 1A + 2A + 3A, и использовать это расстояние в качестве индекса в массиве. В общем случае для цикла длины N вы всегда можете сделать это, протестировав последние N событий со всеми поворотами цикла, но я подозреваю, что обычно будет доступно какое-то сокращение, например, сколько событий назад произошло последнее событие «сделать все», или как давно произошло последнее событие «сделать все».

Answer 3

Билл Ящерица прав. Вот как определить интервалы задачи из истории (в Python):

history = [list of tuples like (timestamp, (A, B, ...)), ordered by timestamp]
lastTaskTime = {}
taskIntervals = {}

for timestamp, tasks in history:
    for task in tasks:
        if task not in lastTaskTime:
            lastTaskTime[task] = timestamp
        else:
            lastTimestamp = lastTaskTime[task]
            interval = abs(timestamp - lastTimestamp)
            if task not in taskIntervals or interval < taskIntervals[task]:
                taskIntervals[task] = interval  # Found a shorter interval

            # Always remember the last timestamp
            lastTaskTime[task] = timestamp

# taskIntervals contains the shortest time intervals of each tasks executed at least twice in the past
# lastTaskTime contains the last time each task was executed

Чтобы получить набор заданий, которые будут выполнены следующим:

nextTime = None
nextTasks = []

for task in lastTaskTime:
    lastTime = lastTaskTime[task]
    interval = taskIntervals[task]

    if not nextTime or lastTime + interval < nextTime:
        nextTime = lastTime + interval
        nextTasks = [task]
    elif lastTime + interval == nextTime:
        nextTasks.append(task)

# nextTime contains the time when the next set of tasks will be executed
# nextTasks contains the set of tasks to be executed

Answer 4

Изменить:

Ах, ты должен пойти другим путем. В этом случае, как кто-то упомянул, вы можете рассчитать эффективный @TimeLastJob, используя наименьшее общее кратное из трех

- Примечание: используются некоторые SQL-расширения SQL Server 2005,
- но все еще может служить в качестве спецификации алгоритма psuedocode
ОБЪЯВИТЬ @constEvaluationPeriodLength int
ОБЪЯВИТЬ @ constCycleTimeJob1A int
ОБЪЯВИТЬ @ constCycleTimeJob2A int
ОБЪЯВИТЬ @ constCycleTimeJob3A int

SET @constEvaluationPeriodLength = 500
SET @ constCycleTimeJob1A = 500
SET @ constCycleTimeJob2A = 1000
SET @ constCycleTimeJob3A = 1500

ОБЪЯВИТЬ @ Indicator1ARunAtLastCyclePoint int
ОБЪЯВИТЬ @ Indicator2ARunAtLastCyclePoint int
ОБЪЯВИТЬ @ Indicator3ARunAtLastCyclePoint int

SET @ Indicator1ARunAtLastCyclePoint = 1
SET @ Indicator2ARunAtLastCyclePoint = 0
SET @ Indicator3ARunAtLastCyclePoint = 1

ОБЪЯВИТЬ @tblPrimeFactors TABLE (
TaskId int
CycleTimePrimeFactor int
)

- захват основных факторов для каждого TaskId
IF (@ Indicator1ARunAtLastCyclePoint = 1)
НАЧАТЬ
INSERT @tblPrimeFactors
ВЫБРАТЬ
TaskId = 1
, PrimeFactor
FROM dbo.tvfGetPrimeFactors (@ constCycleTimeJob1A) - табличная функция оставлена ​​для читателя
КОНЕЦ
IF (@ Indicator2ARunAtLastCyclePoint = 1)
НАЧАТЬ
INSERT @tblPrimeFactors
ВЫБРАТЬ
TaskId = 2
, PrimeFactor
FROM dbo.tvfGetPrimeFactors (@ constCycleTimeJob2A) - табличная функция оставлена ​​для читателя
КОНЕЦ
IF (@ Indicator3ARunAtLastCyclePoint = 1)
НАЧАТЬ
INSERT @tblPrimeFactors
ВЫБРАТЬ
TaskId = 3
, PrimeFactor
FROM dbo.tvfGetPrimeFactors (@ constCycleTimeJob3A) - табличная функция оставлена ​​для читателя
КОНЕЦ


- рассчитать LCM, который может служить эффективным временем
- использует возможности динамической таблицы SQL Server
- (Внутренние операторы select с круглыми скобками и псевдонимами t0 и t1 ниже)
ОБЪЯВИТЬ @LCM int

ВЫБРАТЬ
- Веселитесь с логами / полномочиями для выполнения функции агрегирования продукта
@LCM = Power (сумма (log10 (мощность (PrimeFactor, Frequency))), 10)
ОТ
(
ВЫБРАТЬ
PrimeFactor
, частота = макс (частота)
ОТ
(
ВЫБРАТЬ
PrimeFactor
, частота = количество (*)
FROM @tblPrimeFactors
GROUP BY
TaskId
, PrimeFactor
) t0
) t1

ОБЪЯВИТЬ @TimeLastJob int
ОБЪЯВИТЬ @TimeNextJob int
SET @TimeLastJob = @LCM
SET @TimeNextJob = @TimeLastJob + @constEvaluationPeriodLength

ВЫБРАТЬ
Indicator1A = 1 - SIGN (@TimeNextJob% @ constCycleTimeJob1A)
, Indicator2A = 1 - SIGN (@TimeNextJob% @ constCycleTimeJob2A)
, Indicator3A = 1 - SIGN (@TimeNextJob% @ constCycleTimeJob3A)

---

Оригинал:

Модуль работы% должен сделать трюк

Если я правильно читаю, у вас есть время последнего задания

• t = 1000 или
• т = 5000

и периодичность оценки выбора задания каждые 500 часов.

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

ОБЪЯВИТЬ @constEvaluationPeriodLength int
ОБЪЯВИТЬ @ constCycleTimeJob1A int
ОБЪЯВИТЬ @ constCycleTimeJob2A int
ОБЪЯВИТЬ @ constCycleTimeJob3A int

SET @constEvaluationPeriodLength = 500
SET @ constCycleTimeJob1A = 500
SET @ constCycleTimeJob2A = 1000
SET @ constCycleTimeJob3A = 1500

ОБЪЯВИТЬ @TimeLastJob int
ОБЪЯВИТЬ @TimeNextJob int
--SET @TimeLastJob = 1000
SET @TimeLastJob = 5000
SET @TimeNextJob = @TimeLastJob + @constEvaluationPeriodLength

ВЫБРАТЬ
Indicator1A = 1 - SIGN (@TimeNextJob% @ constCycleTimeJob1A)
, Indicator2A = 1 - SIGN (@TimeNextJob% @ constCycleTimeJob2A)
, Indicator3A = 1 - SIGN (@TimeNextJob% @ constCycleTimeJob3A)

Answer 5

Похоже, самая большая проблема общего знаменателя.

Answer 6

Это замаскированный FizzBuzz.

Вместо обычного сопоставления 3 для «Fizz» и 5 для «Buzz» у нас есть сопоставления 500 для задачи 1A, 1000 для задачи 2A и 3 для задачи 3A и так далее.

Полный список решений (или почти ошибок :)) можно найти здесь: Как вы решаете проблему FizzBuzz?

Answer 7

Требования:

1. Рассчитать LCM времени задач; это период полного цикла.
2. Вычислить временную шкалу события для полного цикла.

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