python - 在给定到达和离开时间矩阵的情况下，想出给定时间排队的人数？

Question

几个小时以来，我一直在思考如何做到这一点，但还是卡住了。

我有一个包含客户到达时间的矩阵 A 和一个包含客户离开时间的矩阵 D。例如。到达矩阵中的时间表示该时间一位顾客到达，离开矩阵中的时间表示一位顾客离开。

我正在尝试绘制商店中顾客数量的时间序列，从 t=1..800 开始，间隔为 1。但是，顾客的到达和离开时间由随机变量决定，这是一个随着时间步长以随机间隔增加而运行的模拟，所以我发现很难在模拟本身中存储给定时间间隔的客户数量。

我认为一定有一种方法可以在给定到达和离开时间矩阵的情况下，以均匀间隔的时间间隔用客户数量填充矩阵 N，但我想不出它是什么。有人可以指出我正确的方向吗？

Answer 1

到达和离开是“事件”，您的数组包含这些事件的时间。基本逻辑是找到下一个事件的时间并进行与该事件相关的更新。对于到达，队列长度增加。对于出发，队列长度递减。以下是该想法的一个相当蛮力的实现(Python3，因为您没有指定)，它会在更改时打印出时间和队列长度:

a = [1.1, 2.9, 5.1, 6.5]
d = [3.5, 5.2, 7.2, 8.0]

queue = 0
a_index = 0
d_index = 0
print(0, ':', queue)

while a_index < len(a) and d_index < len(d):
    if a[a_index] < d[d_index]:  # did an arrival come first?
        queue += 1
        print(a[a_index], ':', queue)
        a_index += 1
    else:
        queue -= 1
        print(d[d_index], ':', queue)
        d_index += 1

# ran out of elements in one of the arrays,
# iterate through remainder of the other

while a_index < len(a):
    queue += 1
    print(a[a_index], ':', queue)
    a_index += 1

while d_index < len(d):
    queue -= 1
    print(d[d_index], ':', queue)
    d_index += 1

如果你只想在整数时间打印，也将它们设置为事件:

a = [1.1, 2.9, 5.1, 6.5]
d = [3.5, 5.2, 7.2, 8.0]

queue = 0
a_index = 0
d_index = 0
print_time = 1
max_time = 10
print(0, ':', queue)

while a_index < len(a) and d_index < len(d):
    if a[a_index] < d[d_index] and a[a_index] <= print_time:
        queue += 1
        a_index += 1
    elif d[d_index] <= print_time:
        queue -= 1
        d_index += 1
    else:
        print(print_time, ':', queue)
        print_time += 1

while a_index < len(a):
    if a[a_index] <= print_time:
        queue += 1
        a_index += 1
    else:
        print(print_time, ':', queue)
        print_time += 1

while d_index < len(d):
    if d[d_index] <= print_time:
        queue -= 1
        d_index += 1
    else:
        print(print_time, ':', queue)
        print_time += 1

while print_time <= max_time:
    print(print_time, ':', queue)
    print_time += 1

这些无疑可以收紧，但它们传达了方法。

如果您有超过这一数量的事件，更好的组织原则是将事件放入优先级队列中，按发生时间排序，然后将它们一个接一个地拉出并分派(dispatch)到适当的状态基于发生的事件类型的转换逻辑。您可以在 this paper 中找到此方法的逻辑。 .本文在 Java 中实现了这些想法，但可以使用 Python3 实现和演示队列模型 here .