python - 高效的 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'}, ...]

我想在列表中搜索符合以下条件的词典: 查找三个或更多具有相同 Value 值且 Time 值彼此相差在 10 分钟以内的字典。我希望此算法在每个符合此条件的字典中创建一个新键并将其标记为匹配。

e.g. The search algorithm would find:
{'Time':2015-03-14 11:54:00, 'Value':'Same Value'}
{'Time':2015-03-14 11:56:00, 'Value':'Same Value'}
{'Time':2015-03-14 11:52:00, 'Value':'Same Value'}
and add the matching key to each dictionary:
{'Time':2015-03-14 11:54:00, 'Value':'Same Value', 'Matching':'True'}
{'Time':2015-03-14 11:56:00, 'Value':'Same Value', 'Matching':'True'}
{'Time':2015-03-14 11:52:00, 'Value':'Same Value', 'Matching':'True'}

我已经创建了一个算法来执行此操作，但它不是特别有效或可扩展。任何人都可以就如何让它变得更好或需要研究的研究领域提供任何建议吗？

当前算法:

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

(注意:我什至没有通过解释器运行这段代码。)

首先按值对字典进行分区。

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

然后按时间对每个列表进行排序并浏览。

import operator
k = 3
for lst in listofdictsbyvalue.values():
    lst.sort(key=operator.itemgetter('Time'))
    for i in range(len(lst) - (k - 1)):
        if lst[i + (k - 1)]['Time'] - lst[i]['Time'] <= datetime.timedelta(minutes=10):
            for j in range(i, i + k):
                lst[j]['Matching'] = 'True'