28
Nov
10

Nochmal Kruskal


Meine Kruskal-Implementierungen haben einen Haken: Das Verwalten der Knoten-Sets ist umständlich und langsam. Zumindest für die Scala-Version habe ich dafür jetzt eine bessere Variante: Ich habe einen eigenen Datentyp geschrieben, der intern eine Map von Knoten auf Knoten-Sets hält, aber speziell an die Aufgabe angepasste Operationen besitzt:

object Kruskal {

  case class Edge[A](v1:A, v2:A, d:Double)

  type LE[A] = List[Edge[A]]
  type OS[A] = Option[Set[A]]

  class SetMap[A](data:Map[A,collection.mutable.Set[A]] = Map[A,collection.mutable.Set[A]]()) {
    import collection.mutable.Set

    //checks if a value exists
    def contains(a:A) = data.contains(a);

    //checks if two values are in the same Set
    def sameSet(repr1:A, repr2:A) = data.get(repr1) == data.get(repr2)

    //adds a new Set with one initial value
    def add(a:A) = if (contains(a)) this else new SetMap(data + (a -> Set(a)))

    //adds a new value to an existing Set (specified by repr)
    def insert(a:A, repr:A) = if (contains(a) || ! contains(repr)) this else {
      val set = data(repr)
      set += a
      new SetMap(data + (a -> set))
    }

    //merges two sets (specified by two representants)
    def merge(repr1:A, repr2:A) = if(! contains(repr1) || ! contains(repr2)) this else {
       val set1 = data(repr1)
       val set2 = data(repr2) 
       if(set1 eq set2) this else {
         set1 ++= set2
         new SetMap(data ++ set2.map(a => a -> set1))
    }}
  }

  def kruskal[A](list: LE[A]) = list.sortBy(_.d).foldLeft((Nil:LE[A],new SetMap[A]()))(mst)._1

  def mst[A](t:(LE[A], SetMap[A]), e:Edge[A]) = {
    val ((es, sets), Edge(p,q,_)) = (t,e)
    (sets.contains(p), sets.contains(q)) match {
        case (false, false) => (e :: es, sets.add(p).insert(q,p))
        case (true, false) => (e :: es, sets.insert(q,p))
        case (false, true) => (e :: es, sets.insert(p,q))
        case (true,true) => if (sets.sameSet(p,q)) (es, sets) //circle
                            else (e :: es, sets.merge(p,q))
    }
  }
    
  def main(args:Array[String]) {
    println(kruskal(
        List(Edge('A,'B,7), Edge('A,'D,5),Edge('B,'C,8), Edge('B,'D,9),
             Edge('B,'E,7), Edge('C,'E,5), Edge('D,'E,15), Edge('D,'F,6),
             Edge('E,'F,8), Edge('E,'G, 9), Edge('F,'G,11))))
  }

}

Wie man sehen kann, braucht man keine Liste mehr zu durchsuchen, alle Operationen laufen auf der Map ab. Nur merge ist komplizierter, weil dabei stark in die Struktur der Map eingegriffen werden muss. Leider kann man obige Lösung nicht ohne weiteres auf Haskell übertragen, denn die verwalteten Sets sind veränderlich. Das ist ein Beispiel, wo veränderliche Daten für gute Performance sorgen, ohne übehaupt von außen sichtbar zu sein. Anstatt irgendwo ein Set zurückzugeben, arbeite ich mit “Repräsentanten”, also irgendeinem Wert im jeweiligen Set, was bei dieser Aufgabenstellung sogar bequemer ist.

Als positiver Nebeneffekt ist die Methode mst nun viel besser zu lesen – trotz der geschachtelten matches (korrigiert – danke für den Tipp an Lars).

About these ads

3 Responses to “Nochmal Kruskal”


  1. 1 Lars
    28. November 2010 um 16:28

    Ich hätte noch einen Vorschlag zur Vereinfachung. Den ersten match in mst kann man sich sparen – statt

    def mst[A](t:(LE[A], SetMap[A]), e:Edge[A]) = (t,e) match {
      case ((es, sets), Edge(p,q,_)) => //...
    

    könnte man auch

    def mst[A](t:(LE[A], SetMap[A]), e:Edge[A]) = {
      val ((es, sets), Edge(p,q,_)) = (t,e)
      //...
    

    notieren. Das macht sofort klar, dass man eigentlich nur eine Umbenennung von Komponenten erreichen will.

  2. 28. November 2010 um 20:25

    Vielen Dank, habe es gleich eingebaut :-)


Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ photo

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s


Folgen

Erhalte jeden neuen Beitrag in deinen Posteingang.

%d Bloggern gefällt das: