高效的Python搜索算法在移动时间间隔内查找匹配项

Question

我有一个字典列表如下：

listofdicts = [{'Time':2015-03-14 11:54:00, 'Value':'Some Value'},
               {'Time':2015-03-14 13:23:00, 'Value':'Another Value'},
               {'Time':2015-03-14 12:52:00, 'Value':'Some Value'}, ...]

我想在列表中搜索具有以下条件的词典： 寻找三个或更多的字典，它们的值对值相同，时间值之间的间隔在10分钟之内。我希望这个算法在每个字典中创建一个匹配这个条件的新键，并将其标记为匹配。在

^{pr2}$

我已经创建了一个算法来实现这一点，但它并不是特别有效或可伸缩的。有没有人能就如何使之更好或研究领域提供任何建议？在

当前算法：

for dict in listofdicts:
   matchingdicts = []
   for dict2 in listofdicts:
      if dict['Value']==dict2['Value']:
         matchingdicts.append(dict2)
   listoftimeintervals = 
      [[dict['Time'] - datetime.timedelta(minutes=10),dict['Time']],
       [dict['Time'] - datetime.timedelta(minutes=9),dict['Time'] + datetime.timedelta(minutes=1)],
       ...,
       [dict['Time'],dict['Time'] + datetime.timedelta(minutes=10)]]
   for time in listoftimeintervals:
      dictsintimerange = []
      for matchingdict in matchingdicts:
         if time[0]<=matchingdict['Time']<=time[1]:
            dictsintimerange.append(matchingdict)
      if len(dictsintimerange)>=3:
         for eachdict in dictsintimerange:
            eachdict['Matching']=='True'

Answer 1

首先对列表进行排序，然后按顺序扫描，在10分钟内查找项目。 大致：

ordered = sorted(listofdicts, key=lambda e:e['Time'])
for i,value in enumerate(ordered):
    if value.get('Matching'):
        continue 
    for j in range(i+2,len(order)):
        if ordered[j]['Time'] - value['Time'] > timedelta(minutes=10):
            break
    if j-i>3:
        for x in range(i,j):
            ordered[x]['Matching']=True

对于排序，这应该是O（N lg N），对于比较，应该是O（N）

Answer 2

（注意：我甚至没有用解释器运行过这段代码。）

首先按值对dicts进行分区。在

import collections
listofdictsbyvalue = collections.defaultdict(list)
for d in listofdicts:
    listofdictsbyvalue[d['Value']].append(d)

然后按时间对每个列表进行排序并扫描。在

^{pr2}$