你如何将一个时间段分成相等的间隔并找到当前的？

Question

我需要为很多用户安排定期作业。此作业将运行以固定速率、间隔进行。我想在该时间间隔内为每个用户统一分配作业的执行。例如，如果间隔为 4 天，我会使用 consistent hashing function 和每个用户的标识符同时安排作业，例如。每 4 天，第 3 天。

间隔是相对于所有用户都相同的原始时刻的。给定这样一个原始时刻，例如 Instant#EPOCH 或其他一些常数值，我如何找到当前间隔的开始日期？

我可以

Instant now = Instant.now();
Instant origin = Instant.EPOCH;
Duration interval = Duration.ofDays(4);

Duration duration = Duration.between(origin, now);
long sinceOrigin = duration.toMillis();
long millisPerInterval = interval.toMillis();

long intervalsSince = sinceOrigin / millisPerInterval;
Instant startNext = origin.plus(interval.multipliedBy(intervalsSince));

int cursor = distributionStrategy.distribute(hashCode, millisPerInterval);

然后我可以使用 cursor 将作业安排在相对于当前间隔开始的 Instant 处。

这里有很多数学运算，我不确定所有地方都转换为毫秒是否会支持实际日期。有没有更精确的方法来划分两个瞬间之间的时间并找到我们当前所在的那个（细分）？

Answer 1

我会尝试将每个时间段定义为具有开始日期和结束日期的对象。然后使用 RB 树来存储 Period 对象。然后您可以在树中导航特定日期：

如果日期在第一个时间段内，您就找到了。如果日期早于期间的开始日期，则导航到左侧节点并检查该期间如果日期晚于该期间的结束日期，请导航至右侧节点并检查该期间

Answer 2

假设您实际上对瞬间和持续时间感兴趣（即与句点、日期、时区等无关），那么您的代码应该没问题。在这种情况下，我实际上会进入毫秒更早...这里的数学很简单。

Interval getInterval(Instant epoch, Duration duration, Instant now) {
    long epochMillis = epoch.getMillis();
    long durationMillis = duration.getMillis();

    long millisSinceEpoch = now.getMillis() - epochMillis;        
    long periodNumber = millisSinceEpoch / durationMillis;
    long start = epochMillis + periodNumber * durationMillis;
    return new Interval(start, start + durationMillis);
}

这假设您不需要担心 now 在 epoch 之前 - 在这一点上您必须根据需要做一些工作 除法运算的 floor，而不是向 0 截断。

(如果你只想开始，你可以 return new Instant(start)。)

Answer 3

如果你只想减少这里的数学运算，你可以使用余数而不是除法和乘法。

long millisSinceIntervalStart = sinceOrigin % millisPerInterval;
Instant startNext = now.minusMillis(millisSinceIntervalStart);

在这里您不必计算自原点以来经过的间隔数。只需获取自 intervalStart 以来经过的时间，然后从当前时间中减去它。

此外，您的 startNext 似乎表示当前间隔的开始，而不是下一个间隔。正确吗？

Answer 4

我认为你把事情复杂化了。您不需要了解代码所建议的那么多。

你只需要回答"when should this object next run?"，使得答案在区间内统计均匀分布且一致（不依赖于"now"，除了下一个运行总是在 "now").

之后

此方法可以做到这一点：

public static long nextRun(long origin, long interval, Object obj) {
    long nextRunTime = origin + (System.currentTimeMillis() - origin)
       / interval * interval + Math.abs(obj.hashCode() % interval);
    return nextRunTime > System.currentTimeMillis() ? nextRunTime : nextRunTime + interval;
}

此方法 returns 下一次对象应该运行使用它的 hashCode() 来确定它应该被安排在持续时间内的什么地方，然后 returns下一次实际发生的时间。

小实现注意事项：使用Math.abs(obj.hashCode() % interval)代替Math.abs(obj.hashCode()) % interval来防止hashCode() returning Integer.MIN_VALUE并知道Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE

如果您需要在 API 中使用 java.time 类，这里是相同的代码，但使用 java.time 参数和 return 类型：

public static Instant nextRun(Instant origin, Duration interval, Object target) {
    long start = origin.toEpochMilli();
    long width = interval.toMillis();
    long nextRunTime = start + (System.currentTimeMillis() - start)
       / width * width + Math.abs(target.hashCode() % width);
    nextRunTime = nextRunTime > System.currentTimeMillis() ? nextRunTime : nextRunTime + width;
    return Instant.ofEpochMilli(nextRunTime);
}

为了帮助理解数学，这里有一个更长的版本，其中组件计算被分解并分配给有意义的变量名称：

public static Instant nextRun(Instant origin, Duration duration, Object target) {
    long now = System.currentTimeMillis();
    long start = origin.toEpochMilli();
    long intervalWidth = duration.toMillis();
    long ageSinceOrigin = now - start;
    long totalCompleteDurations = ageSinceOrigin / intervalWidth * intervalWidth;
    long mostRecentIntervalStart = start + totalCompleteDurations;
    long offsetInDuration = Math.abs(target.hashCode() % intervalWidth);
    long nextRun = mostRecentIntervalStart + offsetInDuration;
    // schedule for next duration if this duration's time has already passed
    if (nextRun < now) { 
        nextRun += intervalWidth;
    }
    return Instant.ofEpochMilli(nextRun);
}

Answer 5

好吧，正如已经说过的那样，找到包含 Duration 的区间，就像您已经在做的那样，或者直接使用 millis 就足以满足这个用例，并且所涉及的数学很简单。但是，如果您确实有一个需要 Period 时间间隔的用例，那么处理方法如下：

将 Period 转换为大约几小时的持续时间，并使用它来估计目标与原点的间隔距离。
根据您的估计缩放 Period。将 24 小时的聚合视为额外的天数。
按缩放周期移动原点间隔。如果移动的间隔包含您的目标，您就完成了。如果不是，请根据您错过的数量重新估算。

找到包含区间时要注意的重要一点是，所有 Period 加法必须直接从原点开始，而不是从中间区间开始，以保持一致性。例如，如果您有一个月的 Period，起点为 1 月 31 日，则起点间隔之后的间隔应从 2 月 28 日和 3 月 31 日开始。将 1 月 31 日加两个月会正确得出 3 月 31 日，但将 2 月 28 日加一个月会错误地得出 3 月 28 日。

以下是上述方法的代码。请注意，这种事情有很多异常情况，我只测试了其中的一些，所以不要认为这段代码经过严格测试。

public static final int NUM_HOURS_IN_DAY = 24;
public static final int NUM_HOURS_IN_MONTH = 730;  // approximate

public ZonedDateTime startOfContainingInterval(ZonedDateTime origin, Period period, int hours, ZonedDateTime target) {
    return intervalStart(origin, period, hours, containingIntervalNum(origin, period, hours, target));
}

public int containingIntervalNum(ZonedDateTime origin, Period period, int hours, ZonedDateTime target) {
    int intervalNum = 0;
    ZonedDateTime intervalStart = origin, intervalFinish;
    long approximatePeriodHours = period.toTotalMonths() * NUM_HOURS_IN_MONTH + period.getDays() * NUM_HOURS_IN_DAY + hours;
    do {
        long gap = ChronoUnit.HOURS.between(intervalStart, target);
        long estimatedIntervalsAway = Math.floorDiv(gap, approximatePeriodHours);
        intervalNum += estimatedIntervalsAway;
        intervalStart = intervalStart(origin, period, hours, intervalNum);
        intervalFinish = intervalStart(origin, period, hours, intervalNum + 1);
    } while (!(target.isAfter(intervalStart) && target.isBefore(intervalFinish) || target.equals(intervalStart)));
    return intervalNum;
}

public ZonedDateTime intervalStart(ZonedDateTime origin, Period period, int hours, int intervalNum) {
    Period scaledPeriod = period.multipliedBy(intervalNum).plusDays(hours * intervalNum / NUM_HOURS_IN_DAY);
    long leftoverHours = hours * intervalNum % NUM_HOURS_IN_DAY;
    return origin.plus(scaledPeriod).plusHours(leftoverHours);
}

你如何将一个时间段分成相等的间隔并找到当前的？

How do you divide a time period into equal intervals and find the current one?

java

jodatime

java-time