Nach uns die Sintflut!


In einer Diskussion auf www.java-forum.org wurde argumentiert, dass einem die tolle Endrekursions-Optimierung nicht viel nützt, wenn man eine Rekursion hat, die „verzweigt“. Ein einfaches Beispiel dafür sei der Flood-Fill Algorithmus.

Dabei ist gerade Flood-Fill sehr einfach endrekursiv umzuschreiben, weil es nicht auf die Reihenfolge der Pixel ankommt. Rein intuitiv würde ich sagen, dass sich mit entsprechendem Aufwand jede verzweigte Rekursion „linearisieren“ lässt, aber das wissen die Theoretiker sicher besser.

Hier eine ganz einfache endrekursive Flood-Fill-Lösung in Scala, die statt Bilder „ASCII-Kunst“ bearbeitet:

object flood {
  val neighbors = List((-1,0),(1,0),(0,-1),(0,1))
  val pic = Array(
    "#####################################",
    "#........#...................#......#",
    "#..................####.......#######",
    "#...#....#..........................#",
    "#...##...####################.......#",
    "#...#....#..........................#",
    "#####################################").map(_.toArray)

  def floodFill(pixels:Set[(Int,Int)]) {
   if (pixels.isEmpty) pic.foreach{line => line.foreach(print); println}
   else floodFill(pixels.foldLeft(Set[(Int,Int)]()){ (set, point) =>
        val (x,y) = point
        pic(y)(x) = 'X'
        set ++ neighbors.map{case (px,py) => (px + x, py + y)}.
                         filter{case (px,py) => pic(py)(px) == '.'}
    })}

  def main(args:Array[String]) {
    floodFill(Set((2,2)))
  }
}

Wie im „richtigen Leben“ habe ich auf eine veränderliche Daten zurückgegriffen, denn bei einem größeren Bild müsste man erheblichen Aufwand betreiben, damit eine „pure“, auf unveränderlichen Daten basierende Implementierung auch nur halbwegs performant wäre.

Das Ergebnis sieht aus wie erhofft:

#####################################
#XXXXXXXX#XXXXXXXXXXXXXXXXXXX#......#
#XXXXXXXXXXXXXXXXXX####XXXXXXX#######
#XXX#XXXX#XXXXXXXXXXXXXXXXXXXXXXXXXX#
#XXX##XXX####################XXXXXXX#
#XXX#XXXX#XXXXXXXXXXXXXXXXXXXXXXXXXX#
#####################################

Selbstverständlich ist das nur eine Spiel-Implementierung, aber es ist schon erstaunlich, wie kurz sich das Ganze formulieren läßt. Dass die neu zu zeichnenden Punkte in einem Set statt einer Liste vorgehalten werden, spart das lästige Vergleichen auf Duplikate. Apropos Punkte: Die Verwendung einer Punkt-Klasse wäre eine sinnvolle Verbesserung, denn auf die Dauer wird die Arbeit mit Tupeln doch lästig, so praktisch sie als „Wegwerf-Lösung“ auch sein mögen.

Würde man das Bild bei jedem floodFill-Aufruf ausgeben, würde man sehen, wie sich trotz der „Linearisierung“ die „Farbe“ rings um den vorhandenen „Fleck“ ausbreitet, und nicht erst in eine Richtung, denn die verwendete Strategie ist eine Breitensuche. Da ich gerade ziemlich müde bin, sei die Implementierung einer Version mit Tiefensuche dem geneigten Leser als Übung überlassen 🙂

Advertisements

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+ Foto

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

Verbinde mit %s