1

我有一个表示票的开始时间及其持续时间的元组列表

tickets = [(start1, duration1), (start2, duration2),...]

我想知道在给定时间 t 有多少票处于活动状态。

虚拟函数：

def activity(t, tickets):
    tickets.sort()
    gamma = 0
    for point, duration in tickets:
    if point < t and t < point + duration:
        gamma += 1
    return gamma

如果要计算时间增加的向量的活动，会花费太多时间并且很愚蠢。任何帮助表示赞赏。

4

1 回答 1

1

使用内置函数 

def activity(t):
       return  len(filter(lambda x:x[0]<t<x[0]+x[1],tickets))

过滤器在较低级别完成，并且比 for 循环更优化，因此它应该更快......它不依赖排序，它只返回剩余内容的计数

使用 numpy

import numpy as np
tickets = np.array([(start1, duration1), (start2, duration2),...])

def activity(t,tickets):
    t1 = tickets[tickets[:,0]<t] #start times before t
    return t2[t2[:,0]+t2[:,1]>t]   #start+duration after t

使用您的代码，因为它已排序，一旦开始大于 t，您总是可以退出循环，因此您不会评估所有项目

def activity(t, tickets):
    tickets.sort(key=lambda x:x[0]) #sort by start time
    gamma = 0
    for point, duration in tickets:
        if point < t and t < point + duration:
              gamma += 1
        elif point > t:
              break ; #we can quit looking
    return gamma

您还可以对列表进行预排序并确保在排序位置插入项目（保持列表排序，这样您就不必每次都对其进行排序）

[编辑] 更新以更正 numpy 函数

>>> x=np.array([(1,2),(2,2),(1,4),(1,1),(3,2)])
>>> x
array([[1, 2],
       [2, 2],
       [1, 4],
       [1, 1],
       [3, 2]])
>>> def activity(t,tickets):
...     tmp = tickets[tickets[:,0] < t]
...     return tmp[tmp[:,0]+tmp[:,1] > t]
...
>>> activity(2,x)
array([[1, 2],
       [1, 4]])
>>> activity(3,x)
array([[2, 2],
       [1, 4]])
于 2012-08-08T17:26:41.990 回答