algorithm - 如何随着时间的推移在不同业务的容器中均匀分布周期性事件？

Question

假设我们有 N 个箱子，并且想要在给定时间段 P 中的每个箱子上触发 #[n] 事件 (n < N)，方式如下:

• 事件在全局定期触发:每 P/sum(#[n])，触发一个事件。
• 在每个 bin 上，事件大致定期触发:也就是说，大致每隔 P/#[n]。

目标是计算单个循环，该循环将令人作呕地重复(在过程的生命周期内)。事件应该均匀地分布在这个循环的重复中。

例如，假设我们有 3 个容器 A、B 和 C，使得 #[A] = 5、#[B] = 10 和 #[C] = 15，那么一个好的循环大概是:

[C, B, C, B, C, A,
 C, B, C, B, C, A,
 C, B, C, B, C, A,
 C, B, C, B, C, A,
 C, B, C, B, C, A]

但尚不清楚这是否是最优的，因为 B 分布不均。

当然不能保证事件的数量分布得如此均匀；事实上，事件的数量可能是互质的。

注意:同样好的循环会将 Bs 列与 As 列切换。

---

数量级:

• 最多十几个垃圾箱。
• 每个容器最多数十万个事件。

---

实用的解决方案是依靠随机算法:对于上述情况，将 5 个 A、10 个 B 和 15 个 C 放入一个序列中，然后随机打乱序列。它不是最优的，但具有良好的复杂性和相对分散的相对较好的概率。

---

我有一个初步的 Python 解决方案:

def select_minimum(weights):
    n, w = 0, weights[0][1]

    for i in range(len(weights)):
        if weights[i][1] < w:
            n, w = i, weights[i][1]

    return n


def spread_bins(bins):
    total = sum(bins)
    pace = [total * 1.0 / b for b in bins]

    c = [(i, pace[i]) for i in range(len(bins))]

    result = []

    for _ in range(total):
        n = select_minimum(c)

        bin, w = c[n]
        c = c[:n] + c[n+1:] + [(bin, w + pace[bin])]
        c = [(i, w - 1) for i, w in c]

        result.append(bin)

    return result

这似乎适用于这个特定的例子，产生:

[2, 1, 2, 0, 1, 2,
 2, 1, 2, 0, 1, 2,
 2, 1, 2, 0, 1, 2,
 2, 1, 2, 0, 1, 2,
 2, 1, 2, 0, 1, 2]

但我不相信 (1) 它是正确的并且 (2) 它是最优的。

---

如何在不同业务的 bin 中随时间均匀分布周期性事件？

Answer 1

请注意，您的问题本质上等同于 Bresenham line drawing algorithm .

虽然 Bresehham 算法将两个位移值 dx 和 dy 均匀地(尽可能)分配到 dx+dy 步上，但您的任务需要“更多尺寸”- N = 3..12

Bresenham 算法可能会在 3D 案例等方面得到扩展(example of 3d and 6d)，但我还没有看到简明的概括(例如，使用优先级队列来处理累积错误等)——也许这样的概括确实存在。 ( some words towards common case )