Есть ли более быстрая альтернатива этому подходу, чтобы получить последнее сообщение об обновлении из списка dict?

Question

Мне нужно получить последнее сообщение об обновлении из потока данных. Данные поступают так:

test_data = 
[{u'category': u'3',
  u'entity': u'entityA',
  u'length': u'0',
  u'timestamp': u'1562422690'},
 {u'category': u'3',
  u'entity': u'entityA',
  u'length': u'1',
  u'timestamp': u'1562422680'},
 {u'category': u'3',
  u'entity': u'entityB',
  u'length': u'2',
  u'timestamp': u'1562422691'},
 {u'category': u'3',
  u'entity': u'entityB',
  u'length': u'3',
  u'timestamp': u'1562422688'},
 {u'category': u'3',
  u'entity': u'entityC',
  u'length': u'4',
  u'timestamp': u'1562422630'},
 {u'category': u'3',
  u'entity': u'entityC',
  u'length': u'5',
  u'timestamp': u'1562422645'},
 {u'category': u'3',
  u'entity': u'entityD',
  u'length': u'6',
  u'timestamp': u'1562422645'}]

Был предложен следующий подход здесь

test_alexander = {entity: sorted([d for d in test_data if d.get('entity') == entity], key=lambda x: x['timestamp'])[-1]
     for entity in set(d.get('entity') for d in test_data)}

, который возвращает это (работает точно так, как задумано):

{u'entityA': {u'category': u'3',
  u'entity': u'entityA',
  u'length': u'0',
  u'timestamp': u'1562422690'},
 u'entityB': {u'category': u'3',
  u'entity': u'entityB',
  u'length': u'2',
  u'timestamp': u'1562422691'},
 u'entityC': {u'category': u'3',
  u'entity': u'entityC',
  u'length': u'5',
  u'timestamp': u'1562422645'},
 u'entityD': {u'category': u'3',
  u'entity': u'entityD',
  u'length': u'6',
  u'timestamp': u'1562422645'}}

Проблема в том, что у меня 7k уникальных "сущностей" и целых 7 миллионов элементов списка в "test_data". Приведенное выше решение занимает много времени, и мне интересно, есть ли более быстрый подход.

Answer 1

кажется, что решения на чистом python могут быть слишком медленными для ваших нужд, я бы предложил использовать pandas, который может работать намного лучше.

ты можешь попробовать это?

import pandas as pd

test_data = [{u'category': u'3',
              u'entity': u'entityA',
              u'length': u'0',
              u'timestamp': u'1562422690'},
             {u'category': u'3',
              u'entity': u'entityA',
              u'length': u'1',
              u'timestamp': u'1562422680'},
             {u'category': u'3',
              u'entity': u'entityB',
              u'length': u'2',
              u'timestamp': u'1562422691'},
             {u'category': u'3',
              u'entity': u'entityB',
              u'length': u'3',
              u'timestamp': u'1562422688'},
             {u'category': u'3',
              u'entity': u'entityC',
              u'length': u'4',
              u'timestamp': u'1562422630'},
             {u'category': u'3',
              u'entity': u'entityC',
              u'length': u'5',
              u'timestamp': u'1562422645'},
             {u'category': u'3',
              u'entity': u'entityD',
              u'length': u'6',
              u'timestamp': u'1562422645'}]

df = pd.DataFrame(test_data)
df["timestamp"] = df["timestamp"].astype(int)

print(df.loc[df.groupby("entity")["timestamp"].idxmax()].to_dict(orient='records'))

Answer 2

Вы должны быть в состоянии сделать это как один цикл с одним сравнением. Просто следите за максимумом, видимым до сих пор для каждой категории, пока вы проходите через цикл:

from collections import defaultdict

def getMax(test_data):
    d = defaultdict(lambda: {'timestamp':0})

    for item in test_data:
        if int(item['timestamp']) > int(d[item['entity']]['timestamp']):
            d[item['entity']] = item
    return d

Возвращаемым значением будет словарь с ключом entity с максимальным значением для каждого. Это должно быть значительно быстрее, чем сортировка или построение массивов в цикле. Тем не менее 7mil занимает некоторое время.

Answer 3

Это должно сработать. Он просматривает тестовые данные один раз и записывает последнее сообщение для каждого объекта:

from collections import defaultdict

latest_message = defaultdict(lambda: dict('timestamp'=0)

for data in test_data:
    latest = latest_message[data[entity]]
    if data['timestamp'] > latest['timestamp']:
        latest_message[data[entity]].update(data)

Answer 4

Я бы начал с разбиения по сущностям, а затем использовал бы max, чтобы взять самую новую запись для каждой сущности.Это будет иметь линейную сложность.Код, который у вас есть, фильтрует, а затем сортирует записи для каждой сущности, близкой к кубической.

В Python это будет выглядеть следующим образом:

partitions = dict()
for record in test_data:
    partitions.setdefault(record['entity'], []).append(record)
# replace this with defaultdict for 2x performance 

for key in partitions:
    partitions[key] = max(partitions[key], key=lambda x: int(x['timestamp']))

Результат в partitions.И имеет форму {entity:[{}]}.

Использование памяти может быть уменьшено путем замены накопления на максимальный вызов, но это может быть на самом деле медленнее.

Answer 5

вы можете использовать max вместо sorted, потому что вам нужна только максимальная запись, а не сортировать остальную часть элемента:

test_alexander = {entity: max([d for d in test_data if d.get('entity') == entity], key=lambda x: x['timestamp'])
                  for entity in set(d.get('entity') for d in test_data)}

(max займет O (n), а сортировка - O (n * logn))