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 に答える