Python 基于属性排序的列表

Question

我有以下对象列表，我想根据依赖关系对其进行排序。首先，没有依赖关系的对象将首先添加到列表中，然后是对添加的第一个批次具有依赖关系的批次，依此类推，直到所有项目都从列表中删除。

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' }
]

目前，我有以下有效的代码，但它不可扩展，也不是很 pythonic。

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)

Answer 1

I want to sort into order based on dependencies

这叫做topological sorting。

这里有一些资源可以告诉您如何做或为您完成工作：

Answer 2

你可以这样做：

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"])

请注意，我没有对其进行优化，因此在大型数据集上它可能会有点慢。

[编辑]这是一个优化版本：

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

Python 基于属性排序的列表

Python ordered list based on property

python

topological-sort

Python 基于 属性 排序的列表

Python ordered list based on property

python

topological-sort

Python 基于属性排序的列表