algorithm - 如何跟踪 a/a + b？

Question

我想随着时间的推移跟踪 a/(a+b) 的比率。 a 和 b 的值随时间增加。增量存储在字典中，其中键代表离散时间。示例:

a = {1:1, 15:1, 17:2, 21:1, ..}
b = {1:1, 4:1, 13:2, 22:1, ..}

输出应该是

ratio = {1:1/2, 4:1/3, 13:1/5, 15:2/6, 17:4/11, 21:5/9, 22:5/10, ..} 

对于根据a 和b 计算ratio，您有什么建议？

Answer 1

这是一个非常标准的基于事件的模拟模式。您需要将输入映射转换为“事件”，按发生时间对它们进行排序，然后按时间顺序处理它们以跟踪分子和分母。当排序的时间发生跳跃时，就该发出输出值了。最后一个细节是，如果在数据耗尽时有一个“等待”尚未发生的跳转，则确保发出最终值。像这样:

def track(a, b):
  # Events are triples: (a/b, time, value).
  events = map(
      lambda item: ('a', item[0], item[1]), a.items()) + map(
      lambda item: ('b', item[0], item[1]), b.items())
  events.sort(key = lambda item: item[1])
  num = 0
  den = 0
  t = events[1][1]
  result = {}
  for event in events:
    t_new = event[1]
    # If the previous time step has ended, emit its fraction.
    if t_new != t:
      result[t] = str(num) + '/' + str(den)
      t = t_new
    # Update the fraction.
    den += event[2]
    if event[0] == 'a':
      num += event[2]
  # Emit the final time step.
  if t not in result:
    result[t] = str(num) + '/' + str(den)
  return result

a = {1:1, 15:1, 17:2, 21:1};
b = {1:1, 4:1, 13:2, 22:1};

print track(a, b)

然后……

$ python foo.py
{1: '1/2', 4: '1/3', 13: '1/5', 15: '2/6', 17: '4/8', 21: '5/9', 22: '5/10'}