Abhängigkeiten auflösen

[henning]

Gestern im Chat war noch jemand an dem Problem interessiert, wie man Abhängigkeiten auflöst (z.B. von zu ladenden Modulen etc...).
Da meine Freundin aber grad gestern Premiere gekriegt hat, hab ich irgendwann nicht mehr antworten können um nicht die neue Staffel von $lieblingsserie zu verpassen

Für die Newbies: Ihr braucht diesen Code nicht um Abhängigkeiten von normalen python-modulen o.Ä. aufzulösen, das macht python selbstverständlich alles selbst!

So jetzt aber der Code:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-

# Folgende Zeile ist nur für python <2.4 nötig
from sets import Set as set

# Das liest sich so:
# - Für A muss B bereits vorhanden sein
# - Für B müssen D und I vorhanden sein
# usw...

d = {
  "A": ["B"],
  "B": ["D", "I"],
  "C": ["B"],
  "D": ["I"],
  "E": ["B"],
  "F": ["I"],
  "G": ["E"],
  "H": ["E", "G"],
  "I": [],
}

def calc_deps(d):
  # fullfilled sind die Abhängigkeiten, die schon erfüllt sind
  fullfilled = set()

  while len(d):
    for k, v in d.items():
      # Sind die Abhängigkeiten für k schon erfüllt?
      if set(v) <= fullfilled:
        yield k
        fullfilled.add(k)
        del d[k]
        break
    else:
      raise StandardError("Zirkuläre Abhängigkeit")

for x in calc_deps(d):
  print x

Das ganze muss man natürlich nicht als Generator implementieren, ich fands bloß innerhalb der Funktion ganz schön, mit sets zu hantieren, weil man sich da optisch ein paar schleifenkonstrukte spart, man kann aber auch komplett mit Listen arbeiten und die z.B. zum Vergleichen sortieren o.Ä..

Wenn ich das richtig sehe, braucht der Algo hier jetzt O(n^2) * O(subset-operation).
Wenn jemand was schnelleres findet, immer her damit!


edit:
Diese Funktion kann man z.B. auch benutzen, um herauszufinden, in welcher Reihenfolge man Klassen definieren muss, wenn diese untereinander eine unüberschaubare Vererbungsstruktur haben!

[modelnine]

Eine andere Herangehensweise ist die Tiefen-Traversierung des Abhängigkeitsbaums. Folgendes Script macht genau das:

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-
"""Abhängigkeiten auflösen aus einer Baumstruktur"""

d = { 
   "A": ["B"], 
   "B": ["D", "I"], 
   "C": ["B"], 
   "D": ["I"], 
   "E": ["B"], 
   "F": ["I"], 
   "G": ["E"], 
   "H": ["E", "G"], 
   "I": [], 
 }

class Node(object):

    def __init__(self,value):
        self._value = value
        self._children = []

    def addNode(self,node):
        self._children.append(node)

    def depthfirst(self,processed):
        if self._value in processed:
            raise StopIteration
        for child in self._children:
            for value in child.depthfirst(processed):
                yield value
        processed.add(self._value)
        yield self._value

    def show(self,depth=0):
        print "%sNode: %s" % (" "*depth,self._value)
        for child in self._children:
            child.show(depth+1)

    def __repr__(self):
        return "<%s: Wert %s>" % (self.__class__.__name__,self._value)

nodes = {}
for name, deps in d.iteritems():
    if name not in nodes:
        nodes[name] = Node(name)
    for dep in deps:
        if dep not in nodes:
            nodes[dep] = Node(dep)
        nodes[name].addNode(nodes[dep])

processed = set()
for node in nodes.itervalues():
    print
    print "Abhängigkeitsbaum für:", node
    node.show()
    for i in node.depthfirst(processed):
        print "Nimm jetzt:", i

Der Code kann nicht mit zirkulären Abhängigkeiten umgehen (im Sinne von "fail gracefully," er baut einfach eine Endlosrekursion in show() und depthfirst()), dafür ist die Baumstruktur und das walken zu rudimentär.

Die Laufzeit dieses Algorithmus ist erheblich besser als die des zuletzt geposteten, zumindest wenn der Baum nicht dicht ist. Eine genaue Laufzeituntersuchung ist in diesem Fall schwierig, aber im schlechtesten Fall ist er O(n^2), im Normalfall besser. Ich hab gerade noch mal ziemlich lange nachgegrübelt wie man ein O() für den Normalfall angeben kann, aber zu einem wirklichen Ergebnis bin ich nicht gekommen... Dafür bräuchte ich Stift und Papier.

[henning]

Danke für die Ergänzung! Ich wollte noch hinzufügen, dass ich jetzt auch vom wort-case ausgegangen bin, wies im mittleren Fall aussieht, weiß ich nicht, aber sicher auch besser...
Vielleicht kann man ja auch beide herangehensweisen komibieren, so dass man die Vorteile von deinem Algo hat aber trotzdem zirkel zuverlässig erkennt.

Also z.B. in dem man zwar tiefensuche macht, aber bereits abgehandelte Items aus dem dict löscht wie bei mir...