Упорядоченный список Python на основе свойства - PullRequest
Новая
       61

Упорядоченный список Python на основе свойства

0 голосов
/ 21 февраля 2019

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

pp = [
    {"name": 'pipeline13', "deps": 'pipeline11' },
    {"name": 'pipeline1', "deps": 'pipeline4' },
    {"name": 'pipeline4'},
    {"name": 'pipeline2', "deps": 'pipeline4'},
    {"name": 'pipeline3'}, 
    {"name": 'pipeline5'},
    {"name": 'pipeline6', "deps": 'pipeline2'},
    {"name": 'pipeline7'},
    {"name": 'pipeline8', "deps": 'pipeline2'},
    {"name": 'pipeline9', "deps": 'pipeline3'},
    {"name": 'pipeline10', "deps": 'pipeline1' },
    {"name": 'pipeline11', "deps": 'pipeline10' }
]

В настоящее время у меня есть приведенный ниже код, который работает, но он не масштабируемый и не очень питонический. 

output = []
output_stage_1 = []
output_stage_2 = []
output_stage_3 = []
output_stage_4 = []
output_stage_5 = []


while pp:
    for p in pp:
        if not p.get('deps'):
            output.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output]:
            output_stage_1.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_1]:
            output_stage_2.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_2]:
            output_stage_3.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_3]:
            output_stage_4.append(p)
            pp.remove(p)


        if p.get('deps') in [i.get('name') for i in output_stage_4]:
            output_stage_5.append(p)
            pp.remove(p)



print(output + output_stage_1 + output_stage_2 + output_stage_3 + output_stage_4 + output_stage_5)

Ответы [ 2 ]

0 голосов
/ 22 февраля 2019

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

ordered = [ item["name"] for item in pp if "deps" not in item ]
while len(ordered) < len(pp):
    for item in pp:
        if "deps" not in item : continue
        if item["name"] not in ordered and item["deps"] in ordered:
            ordered.append(item["name"])

Обратите внимание, что я не оптимизировал его, поэтому он может быть немного медленным на больших наборах данных.

[EDIT] вотоптимизированная версия: 

ordered    = [ item for item in pp if "deps" not in item ]
dependents = [ (item["name"],item["deps"],item) for item in pp if "deps" in item]
included   = set([item["name"] for item in ordered])
remaining  = len(dependents)
while remaining > 0:
    nextGroup = []
    circularCount = remaining 
    for name,deps,item in dependents:
        if deps in included:
            ordered.append(item)
            included.add(name)
            remaining -= 1
        else:
            nextGroup.append((name,deps,item))
    dependents = nextGroup
    if remaining == circularCount : break 

if remaining > 0 : 
    # There was a circular dependency error
0 голосов
/ 21 февраля 2019

Я хочу отсортировать по порядку на основе зависимостей

Это называется топологическая сортировка .

Вот некоторые ресурсы, которые либо показывают вамкак сделать то или иное за вас дело:

...