通过另一个日期列表拆分日期列表

Question

我在网络中有许多节点。节点每小时发送一次状态信息以表明它们还活着。所以我有一个节点列表和他们上次活着的时间。我想绘制一段时间内活动节点的数量。

节点列表按照它们上次的活动时间排序，但我无法找出一个很好的方法来计算每个日期有多少活着。

from datetime import datetime, timedelta 

seen = [ n.last_seen for n in c.nodes ] # a list of datetimes 
seen.sort() 
start = seen[0] 
end = seen[-1] 

diff = end - start 
num_points = 100 

step = diff/num_points 

num = len(c.nodes) 

dates = [ start + i * step for i in range(num_points) ] 

我想是基本上

alive = [ len([ s for s in seen if s > date]) for date in dates ] 

但那不是真的有效。解决方案应该使用seen列表进行排序并且不会遍历整个列表中每个日期的事实。

Answer 1

python bisect module会为您找到正确的索引，并且可以扣除前后项目的数量。

如果我理解正确的，这将是O（日期）* O（日志（看到））

---

编辑1

应该可以在一个通做的，只是像SilentGhost演示。然而，itertools.groupby工作正常排序的数据，应该能够在这里做一些事情，也许是这样的（这比O（n）的更多，但可以提高）：

import itertools 

# numbers are easier to make up now 
seen = [-1, 10, 12, 15, 20, 75] 
dates = [5, 15, 25, 50, 100] 

def finddate(s, dates): 
    """Find the first date in @dates larger than s""" 
    for date in dates: 
     if s < date: 
      break 
    return date 


for date, group in itertools.groupby(seen, key=lambda s: finddate(s, dates)): 
    print date, list(group) 

Answer 2

这种发电机遍历该列表只有一次：

def get_alive(seen, dates): 
    c = len(seen) 
    for date in dates: 
     for s in seen[-c:]: 
      if s >= date:  # replaced your > for >= as it seems to make more sense 
       yield c 
       break 
      else: 
       c -= 1 

Answer 3

我将SilentGhosts生成器解决方案进一步使用显式迭代器。这是我想到的线性时间解决方案。

def splitter(items, breaks): 
    """ assuming `items` and `breaks` are sorted """ 
    c = len(items) 

    items = iter(items) 
    item = items.next() 
    breaks = iter(breaks) 
    breaker = breaks.next() 

    while True: 
     if breaker > item: 
      for it in items: 
       c -= 1 
       if it >= breaker: 
        item = it 
        yield c 
        break 
      else:# no item left that is > the current breaker 
       yield 0 # 0 items left for the current breaker 
       # and 0 items left for all other breaks, since they are > the current 
       for _ in breaks: 
        yield 0 
       break # and done 
     else: 
      yield c 
      for br in breaks: 
       if br > item: 
        breaker = br 
        break 
       yield c 
      else: 
       # there is no break > any item in the list 
       break