Python Reduce List of Dicts на основе совпадающих пар ключ/значение

Question

У меня есть список dicts, который определяет потоки (источник для перехода к удалению с соответствующим объемом). Теперь я хочу разделить эти потоки на ссылку (например, (источник для прыжка с громкостью, прыжок в пункт назначения с объемом) и объединить все повторяющиеся ссылки вместе, суммируя их тома.

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

Но если у меня есть миллионы потоков, которые могут стать довольно неэффективен и медленный, я думаю.

Мои исходные данные выглядят так:

flows = [ 
    { 
     'source': 1, 
     'hop': 2, 
     'destination': 3, 
     'volume': 100, 
    },{ 
     'source': 1, 
     'hop': 2, 
     'destination': 4, 
     'volume': 50, 
    },{ 
     'source': 2, 
     'hop': 2, 
     'destination': 4, 
     'volume': 200, 
    }, 
] 

Что мой результат должен быть:

links = [ 
    { 
     'source': 1, 
     'hop': 2, 
     'volume': 150, 
    },{ 
     'hop': 2, 
     'destination': 3, 
     'volume': 100, 
    },{ 
     'hop': 2, 
     'destination': 4, 
     'volume': 250, 
    },{ 
     'source': 2, 
     'hop': 2, 
     'volume': 200, 
    }, 
] 

Большое спасибо за вашу помощь!

Answer 1

Вы можете получить ссылки на двух различных словарей, один между источником & хмеля и другой между хмелевой & назначения. Затем вы можете легко создать список результатов отдельно от обоих dicts. Ниже Counter используется который dict как объект с 0 в качестве значения по умолчанию:

import pprint 
from collections import Counter 

flows = [ 
    { 
     'source': 1, 
     'hop': 2, 
     'destination': 3, 
     'volume': 100.5, 
    },{ 
     'source': 1, 
     'hop': 2, 
     'destination': 4, 
     'volume': 50, 
    },{ 
     'source': 2, 
     'hop': 2, 
     'destination': 4, 
     'volume': 200.7, 
    }, 
] 

sources = Counter() 
hops = Counter() 

for f in flows: 
    sources[f['source'], f['hop']] += f['volume'] 
    hops[f['hop'], f['destination']] += f['volume'] 

res = [{'source': source, 'hop': hop, 'volume': vol} for (source, hop), vol in sources.items()] 
res.extend([{'hop': hop, 'destination': dest, 'volume': vol} for (hop, dest), vol in hops.items()]) 
pprint.pprint(res) 

Выход:

[{'hop': 2, 'source': 1, 'volume': 150.5}, 
{'hop': 2, 'source': 2, 'volume': 200.7}, 
{'destination': 3, 'hop': 2, 'volume': 100.5}, 
{'destination': 4, 'hop': 2, 'volume': 250.7}] 

Выше будет работать в O (п) времени, поэтому он должен работать с миллионами потоков если у вас достаточно памяти.

Answer 2

алгоритм

псевдо:

1. создать пустой список результатов/установить/словарь
2. перебирает де потоки списка
3. разделить каждый отдельный поток в 2-х звенья
4. для каждого из этих 2-х ссылок если они уже находятся в списке результатов (на основе двух узлов).
5. если нет: добавьте их. если да: обновите том, который уже есть в списке.