Scala Funktionales MergeSort - Laufzeit exponentiell

[Mujahiddin]

Hi,
bisschen funktional programmieren versucht, und es hieß ja "Scala optimiert den Code"
Naja, das folgende Programm scheint davon nicht betroffen zu sein:

object MergeSort {

	def divide: List[Int] => (List[Int], List[Int]) = {
		xs => ( xs take ( xs.length / 2 ), xs drop ( xs.length / 2 ) )
	}

	def conquer: ( (List[Int], List[Int]) ) => (List[Int], List[Int]) = {
		xt => ( mergeSort( xt._1 ), mergeSort( xt._2 ) )
	}

	def merge: ( (List[Int], List[Int]) ) => List[Int] = {
		xt => xt._1.foldLeft( xt._2 ) {
			case (Nil, x) => x::Nil
			case (f::fs, x) => if( x < f ) x::f::fs else f::merge( fs, x::Nil )
		}
	}

	def mergeSort: List[Int] => List[Int] = {
		case xs if ( xs.length < 2 ) => xs
		case xs => merge( conquer( divide( xs ) ) )
	}
}

1. Ist das alles funktional? (Kann ja sein, dass ich was übersehen hab!)
2. Sobald die Liste größer als 10 Elemente hat, dauert das Sortieren weit über 10 Sekunden, was wohl kein gewünschtes Ergebnis ist. Woran liegt das?

Und mal so nebenbei:
Was ist der grundlegende Unterschied zwischen

def square(x: Int) = x * x

und

def square: Int => Int = x => x * x

? Also ich verstehe den Sinn nicht ganz!

Danke für die Hilfe,

liebe Grüße!

 

[JohannisderKaeufer]

1. Ist das alles funktional? (Kann ja sein, dass ich was übersehen hab!)

IMHO, spricht nichts dagegen, das es als funktional bezeichnet werden kann.

Das

merge( conquer( divide( xs ) ) )

würde ich allerdings behaupten, daß es nicht dem Lambda Kalkül entspricht.

divide( xs ) wertet den Ausdruck aus und gibt ein Tuppel aus zwei Listen zurück.
conquer nimmt dieses Tuppel entgegen.

Wenn man conquer nun so umschreiben würde

def conquer(d: ( List[Int] => (List[Int],List[Int])), xs:List[Int]) : (List[Int], List[Int]) = ...

//Dann könnte man Konquer so aufrufen.
conquer( divide, xs)

//oder weiterändern in 
def conquer(d: ( List[Int] => (List[Int],List[Int]))) : List[Int] => (List[Int], List[Int]) = ...

Dadurch kann der Compiler dann schon im vorraus Teilausdrücke analysieren und optimieren was schlußendlich besseren ByteCode liefert.

2. Sobald die Liste größer als 10 Elemente hat, dauert das Sortieren weit über 10 Sekunden, was wohl kein gewünschtes Ergebnis ist. Woran liegt das?

Das liegt daran, dass eine deiner Funktionen irgendwo Käse ist. Und zwar die merge Funktion.

So hätte ich diese Funktion implementiert

      def merge(l: (List[Int], List[Int])): List[Int] = {
        (l._1, l._2) match {
          case (as, Nil) => as
          case (Nil, bs) => bs
          case (a :: as, b :: bs) => if (a < b) a :: (merge(as, l._2)) else b :: (merge(l._1, bs))
        }
      }

Eine wesentliche Verbesserung tritt ein wenn man eine kleine Anpassung vornimmt

    def merge: ( (List[Int], List[Int]) ) => List[Int] = {
        xt => xt._1.foldLeft( xt._2 ) {
            case (Nil, x) => x::Nil
            case (f::fs, x) => if( x < f ) x::f::fs else f::merge( x::Nil, fs )
        }
    }

Kann sich aber auch um puren Zufall handeln.

3. Was ist der grundlegende Unterschied zwischen
def square(x: Int) = x * x und def square: Int => Int = x => x * x ?

Das ist ein wenig schwierig in Worte zu fassen. Beides sind irgendwo Funktionen, die entweder angewendet werden könne, oder an andere Funktionen übergeben werden können. Es gibt aber Unterschiede wann diese Funktionen analysiert und erstellt werden. Hier würde es nicht Schaden das nochmal genauer zu recherchieren.

    def divide: List[Int] => (List[Int], List[Int]) = {
        xs => ( xs take ( xs.length / 2 ), xs drop ( xs.length / 2 ) )
    }
    def divide = {
        xs:List[Int] => ( xs take ( xs.length / 2 ), xs drop ( xs.length / 2 ) )
    }
    
    def divide(xs:List[Int]) = ( xs take ( xs.length / 2 ), xs drop ( xs.length / 2 ))

Aber wenn man scala anschaut und sieht dass alle 3 Arten, für divide(xs) funktionieren und doch irgendwo feine Unterschiede sind dann ist das doch sehr verwirrend.

Ich hab mich aber selbst mal an einem MergeSort in Scala versucht.

object MergeSort {

  def mergeSort(xs: List[Int], comp: ((Int, Int) => Boolean)): List[Int] = {

    def divide2 = xs splitAt (xs.length / 2)

    def conquer = (mergeSort(divide2._1, comp), mergeSort(divide2._2, comp))

    def merge = {
      def merge(l: (List[Int], List[Int])): List[Int] = {
        (l._1, l._2) match {
          case (as, Nil) => as
          case (Nil, bs) => bs
          case (a :: as, b :: bs) => if (comp(a, b)) a :: (merge(as, l._2)) else b :: (merge(l._1, bs))
        }
      }

      merge(conquer)
    }

    if (xs.length < 2) xs
    else merge
  }
}

Hier ist noch eine Funktion comp dabei, mit der man eine Comparator ((Int, Int) => Boolean), als Auf oder Absteigend definieren kann.

 

[schlingel]

Das merge( conquer( divide( xs ) ) ) würde ich allerdings behaupten, daß es nicht dem Lambda Kalkül entspricht.

Warum?

 

[JohannisderKaeufer]

Warum?

Ein kleines Beispiel:

def square(d:Double) = d * d

def root(d:Double) = Math.sqrt(d)

Unter der Annahme

assert ( square(root(d)) == d )

Meiner Meinung nach wird ein

square(root(4))

zu sowas gemacht:

val a = root(4)
val b = 2
val c = square(2)
4

hätte man nun allerdings:

def square(d:Double) = d * d

def root( f: (Double => Double), d: Double) = Math.root(f(d))

def complex(d:Double) = root(square, d)

Dann könnte ein entsprechender Compiler hingehen und das ganze früher evaluieren und optimieren.

Was dann zu folgendem führen könnte.

def complex(d:Double) = d

Dies wäre natürlich der allerbeste Fall, keine Frage und soweit ist man heute vielleicht noch nicht.
Eine Optimierung bei der ich mir ziemlich sicher bin, die hier zu tragen kommt ist, daß
wenn aus zwei Funktionen eine wird, auch nur einmal Speicher im Stack reserviert werden muß, wohin bei zwei Funktionen zweimal Speicher reserviert werden muß und eventuell noch was umgeschaufelt werden muß. Das ist aber nicht gerade mein Spezialgebiet. Da gibt es bestimmt das ein oder andere Landei, daß hier besser bescheit weiß =P

 

[JohannisderKaeufer]

Bei meinem Lösungsvorschlag haben ein paar Dinge auch nicht gepasst deshalb

object MergeSort {

  def mergeSort(xs: List[Int], comp: ((Int, Int) => Boolean)): List[Int] = {

    def divide2 = xs splitAt (xs.length / 2)

    def conquer = (mergeSort(divide2._1, comp), mergeSort(divide2._2, comp))

    def mergentr = {
      /**
       * this funktion is not tailrec, therefore causes Stackoverflows for big lists
       */
      def merge(l: (List[Int], List[Int])): List[Int] = {
        (l._1, l._2) match {
          case (as, Nil) => as
          case (Nil, bs) => bs
          case (a :: as, b :: bs) => if (comp(a, b)) a :: (merge(as, l._2)) else b :: (merge(l._1, bs))
        }
      }

      merge(conquer)
    }
    
    def mergetr = {
      @tailrec
      def merge(acc:List[Int], l: (List[Int], List[Int])): List[Int] = {
        (l._1, l._2) match {
          case (as, Nil) => (acc.reverse):::as
          case (Nil, bs) => (acc.reverse):::bs
          case (a :: as, b :: bs) if (comp(a, b)) => (merge(a:: acc, (as, l._2))) 
          case (a:: as, b:: bs) if (! comp(a,b)) =>  (merge(b:: acc, (l._1, bs)))
        }
      }

      merge(Nil, conquer)
    }
    /**
     * defines which mergefkt to use
     */
    def merge = mergetr

    if (xs.length < 2) xs
    else merge
  }
}

Wenn man in Scala rekursive Funktionsaufrufe nutzt dann sollte auch sichergestellt werden, daß eine Tail-Call-Optimierung stattfinden kann. Hier ist die annotation @tailrec nützlich, da Sie auf solche Fehlerquellen hinweist.

Dann klappts auch bei Großen Listen ohne Stackoverflow.

Beim Sortieren, von 1 Mio Ints benötige ich mit diesem MergeSort ca. 10%- 20% mehr Zeit als mit sort aus scala.collection.List, daß auch einen Mergesort implementiert.

Allerdings etwa das 3 - 4 -fache an Zeit gegenüber sortWith aus scala.collection.SeqLike.

Beeindruckend.

 

[Landei]

"Funktional" bedeutet nicht, dass du alles mit Funktionen schreiben solltest. Scala läuft auf der VM, die nun mal bei der Optimierung auf Methoden ausgelegt ist. Wenn du so was [c]def x: Int => Int = ...[/c] schreibst, wird von Scala bei jedem Aufruf ein neues Funktions-Objekt angelegt. Mit [c]val x: Int => Int = ...[/c] nur ein einziges Funktionsobjekt, das wiederverwendet wird, bei [c]def x(y:Int):Int..[/c] gar keins, solange es nicht notwendig ist (also solange x z.B. nicht als Argument für eine andere Methode dient).

Mal ein kleiner Trick, eine Liste in einem Durchlauf aufzusplitten:

def divide(list:List[Int]) = list.foldLeft((List[Int](),List[Int]())){ (xs,x) => (xs._2, x::xs._1)}

Wie schon angemerkt, ist deine merge-Funktion Quatsch. In einem fold rekursiv die umschließende Funktion aufzurufen, muss zu quadratischem Verhalten führen, wo eine merge-Operation doch O(n) ist.

 

[Mujahiddin]

"Funktional" bedeutet nicht, dass du alles mit Funktionen schreiben solltest. Scala läuft auf der VM, die nun mal bei der Optimierung auf Methoden ausgelegt ist. Wenn du so was [c]def x: Int => Int = ...[/c] schreibst, wird von Scala bei jedem Aufruf ein neues Funktions-Objekt angelegt. Mit [c]val x: Int => Int = ...[/c] nur ein einziges Funktionsobjekt, das wiederverwendet wird, bei [c]def x(y:Int):Int..[/c] gar keins, solange es nicht notwendig ist (also solange x z.B. nicht als Argument für eine andere Methode dient).

Ist das dann so ähnlich wie bei primitiven Datentypen?

1.toString

ist ja gültiger Scala-Code.

1

wird als primitiver Datentyp behandelt, außer man verwendet es wie ein Objekt.
Ist das also auch so bei

def f(x:Int):Int [...]

, dass es wie eine Standard Funktion verwendet wird?

Dass meine merge-Funktion Quatsch war, weiß ich. Ich hatte davor die beiden Argumente beim rekursiven Aufruf in "richtiger" Reihenfolge. Wenn man sie in falscher Reihenfolge übergibt, steigt die Anzahl der Aufrufe ins Unermessliche. Ich hatte das zu Testzwecken so getauscht und es danach vergessen.

Was spricht denn gegen meine divide Funktion oder

splitAt

von Johannes? Ist das nicht funktional?
Und passt meine merge Funktion, nachdem die Argumente nun in richtiger Reihenfolge sind? Ich meine, ohne Rekursion ist die merge Funktion wohl undenkbar. Das war zumindest mein intuitiver Ansatz, sie umzusetzen. Übrigens sind die Methoden divide/conquer/merge/mergeSort und ihre Rückgabewerte vorgegeben, ich darf also nicht davon abweichen.

Warum genau

merge( conquer( divide( xs ) ) )

nicht funktional sein soll, ist mir auch nicht ganz klar...

Ansonsten noch danke für die Hilfsbereitschaft,
liebe Grüße!

 

[Landei]

Ist das dann so ähnlich wie bei primitiven Datentypen?

1.toString

ist ja gültiger Scala-Code.

1

wird als primitiver Datentyp behandelt, außer man verwendet es wie ein Objekt.
Ist das also auch so bei

def f(x:Int):Int [...]

, dass es wie eine Standard Funktion verwendet wird?

[c]f[/c] ist eine ganz normale Methode. Allerdings konvertiert Scala diese wenn nötig auch zu einer Funktion. Die Details hatte ich schon einmal zusammengeschrieben: Methoden und Funktionen eSCALAtion Blog

Was spricht denn gegen meine divide Funktion oder

splitAt

von Johannes? Ist das nicht funktional?

Nichts. Meine Version sollte ein klein wenig performanter sein, weil sie - wie gesagt - die Ausgangsliste nur einmal durchläuft.

Warum genau

merge( conquer( divide( xs ) ) )

nicht funktional sein soll, ist mir auch nicht ganz klar...

Doch, das ist meiner Meinung nach funktional.

 

[Landei]

Hier meine Version:

import collection.mutable.ListBuffer
import annotation.tailrec

object MergeSort {

  type ListPair = (List[Int], List[Int])

  def divide(list: List[Int]) = list.foldLeft[ListPair]((Nil, Nil)) {
    (xs, x) => (xs._2, x :: xs._1)
  }

  def conquer(lists: ListPair) = merge((mergeSort(lists._1), mergeSort(lists._2)))

  def merge(lists: ListPair) = {
    @tailrec
    def merge(pair: ListPair, accu: ListBuffer[Int]): List[Int] = pair match {
      case (x :: xs, y :: ys) =>
        if (x <= y) merge((xs, y :: ys), accu += x)
        else merge((x :: xs, ys), accu += y)
      case (xs, ys) => (accu ++= xs ++= ys).toList
    }
    merge(lists, new ListBuffer[Int]())
  }

  def mergeSort(xs: List[Int]): List[Int] = xs match {
    case Nil | _ :: Nil => xs
    case _ => conquer(divide(xs))
  }

}

Diese Version ist nicht hundertprozent funktional, weil merge aus Performancegründen die mutable Klasse Listbuffer verwendet. Das ist nicht weiter schlimm, weil davon "von außen" nichts zu sehen ist, dieses merge also von einer rein funktionalen Implementierung nicht zu unterscheiden ist und keine Seiteneffekte hat. Insbesondere würde sonst die Endrekursion ein reverse der Liste erfordern (wie bei JohannisDerKäufer's mergetr)

 

[JohannisderKaeufer]

Nichts. Meine Version sollte ein klein wenig performanter sein, weil sie - wie gesagt - die Ausgangsliste nur einmal durchläuft.

En contraire. Da solltest du wirklich mal nachmessen. Zuerst dachte ich auch das das performanter sein müsste, da z.B. für das length die Liste einmal durchlaufen wird (O(n)), und dann nochmal für das splitAt.

Tatsache ist aber das beim splitAt die Liste nur bis zur Mitte durchlaufen werden muß, wobei die Elemente über einen ListBuffer in eine neue Liste gelegt werden. Komplexität hierfür O(n/2) also, O(n)
Der Rest, also der zweite Teil des Tuppels ist dann nur der Tail des "Mittleren" Elements. Und das bekommt man für: O(1).

Zusammengefaßt bleibt es bei O(n), allerdings ist die ganze Liste einmal durchgehen und dann nur aus der einen Hälfte eine neue Liste erstellen im gegensatz zu zwei neue Listen erstellen weniger aufwändig.

Bei einer Million Intwerten sieht man es schon recht deutlich. Da werden dann aus ca. 13 Sekunden über 30.

merge( conquer( divide( xs ) ) )

Funktional, ja. Da habe ich nichts Gegenteiliges behauptet. Ich wollte damit nur anregen, gerade wenn man sich mit FP beschäftigt und es damit Möglich ist, Funktionen auch als Parameter zu nutzen, dies auch in betracht zu ziehen, zumal ja auch gefragt wurde ob es sich um ein funktionales Programm handelt. Copy-by-name und Copy-by-value finde ich in dem Hinblick ganz spannend.


Ach ja und der ListBuffer trägt zur Performance soviel bei wie ein Backstein beim Schwimmen.(Zumindest hier bei mir).
Es ist richtig, daß ein append beim ListBuffer in konstanter Zeit gehen mag
toList liefert die Liste auch in konstanter Zeit. Keine Frage.
Aber das append wird in der Methode n Mal aufgerufen. Daher ist das merge insgesamt gesehen O(n).

Das Merge mit dem reverse hat für das Einfügen in die Liste je Element konstante Zeit. Für das Reverse allerdings O(n). Da das Reverse bei der Methode allerdings nur einmal am Recursionsende aufgerufen wird, bleibt die Komplexität der gesamten merge Methode bei O(n).

Der Unterschied sind bei 1 Mio. Einträgen in einer zu sortierenden Liste etwa 3-4 Sekunden die der ListBuffer länger braucht.

Daraus kann ich nur schließen, daß ein einzelnes append in ListBuffer mehr als doppelt so lange benötigt wie ein vorne anfügen in List.


Irgendwie lächerlich. Fast so, wie Kopfschmerzen mit dem Revolver zu behandeln. Wenn tatsächlich Skepsis besteht, dann kann ich das gut verstehen und empfehle mal nachzumessen.