Russische Bauernmultiplikation


Zufälligerweise habe ich von diesem kleinen Programmierwettberb auf „The Daily WTF“ gelesen. Die Aufgabe ist einfach: Implementiere die Russische Bauernmultiplikation. Das ist ein perfektes Beispiel für die Arbeit mit Scala-Collections, und auch unser alter Bekannter foldLeft kommt zum Einsatz.

Hier ist nun meine Lösung, die ich Schritt für Schritt sezieren möchte:

def russianMultiply(a:Int, b:Int) = {
  def loop(x:Int, y:Int, list:List[(Int,Int)]):List[(Int,Int)] = 
      if(x == 0) list else loop(x >> 1, y << 1, (x, y) :: list)
  loop(a, b, Nil).filter(_._1 % 2 == 1).foldLeft(0)(_+_._2)
}
&#91;/sourcecode&#93;

Das ist wieder eines dieser typische Scala-Beispiele: Kurz und unverständlich. Aber nicht mehr lange!

Fangen wir mit der inneren Funktion "loop" an. 

Als erstes muss man wissen, was ein Tupel ist. Ein Tupel kann man sich wie ein Array vorstellen, nur besitzt jedes Feld einen eigenen Typ. Ein Tupel ist also ein bequemer Weg, momentan zusammengehörige Werte zu "bündeln". Wenn in Java eine Funktion gleichzeitig einen String, ein int und ein Date zurückgeben soll, müsste man dafür einen extra Klasse schreiben, die die drei Werte aufnimmt. In Scala hat man dafür Tupel, und da sie so praktisch ist, gibt es einen Kurzschreibwiese, nämlich einfach nur Klammern. Wollten wir also ein Int, einen String und ein Date zurückgeben, würden wir schreiben (42, "answer", new Date), und dieses Konstrukt hätte den Typ Tuple3&#91;Int, String, Date&#93; oder kurz (Int, String, Date). 

Was wollen wir nun vertupeln? Nun, die Wertepaare mit den halbierten und verdoppelten Multiplikanden. Und die Tupel packen wir in eine Liste. So eine Liste ist entweder leer (dafür gibt es den Untertyp Nil) oder sie besteht aus einem Listenkopf und der Restliste, und beide sind durch den Operator :: verknüpft. Eine Liste der Zahlen 1 bis 3 kann man bequem als List(1, 2, 3) schreiben, aber genauso gut ginge 1 :: List(2, 3) oder 1 :: 2 :: 3 :: Nil.

Die Funktion loop hat drei Argumente: den zu halbierenden Wert, den zu verdoppelnden Werte und eine "Sammel-Liste" mit allen Tupel-Paaren, die wir schon berechnet haben. Ist der erste Wert gleich 0, sind wir fertig und geben einfach unsere Sammel-Liste zurück (man nennt so ein Sammel-Argument auch "Akkumulator"). Ist das nicht der Fall, packen wir ein Tupel aus unseren aktuellen Argument-Werten zur vorhandenen Liste dazu, berechnen die neuen Werte (wir halbieren und verdoppeln ganz elegant mit den beiden Bit-Schubs-Operatoren &gt;&gt; und &lt;&lt;) und rufen mit diesen Argumenten loop rekursiv auf.

So, probieren wir loop einmal alleine aus, z.B. auf <a href="http://www.simplyscala.com">Simply Scala</a>:


def loop(x:Int, y:Int, list:List[(Int,Int)]):List[(Int,Int)] = 
   if(x == 0) list else loop(x >> 1, y <<1, (x,y)::list)
//--> loop: (Int,Int,List[(Int, Int)])List[(Int, Int)]
loop(23,34,Nil)
//--> res1: List[(Int, Int)] = List((1,544), (2,272), (5,136), (11,68), (23,34))

Gut, die Wertepaare sind rückwärts geordnen, weil wir ja immer am Listenanfang angefügt haben. Aber an dieser Stelle ist uns das egal, Hauptsache wir haben die Wertepaare. Nun wäre es schön, wenn wir nur die Paare mit einem ungeraden ersten Wert hätten. Auf das erste Element eines Tupels tupel greift man mit tupel._1 zu, auf das zweite mit tupel._2 usw. Und filtern tut man eine Collection mit der Funktion „filter“ – wer hätte das gedacht! Kurz ausprobieren:

List((1,544), (2,272), (5,136), (11,68), (23,34)).filter(_._1 % 2 == 1)
//--> res2: List[(Int, Int)] = List((1,544), (5,136), (11,68), (23,34))

Sehr schön! Nun hatte ich letzten Mal geschrieben, dass man foldLeft oder foldRight oft verwenden kann, wenn es irgendwie ums „Daten sammeln“ geht, und auch in unserem Fall passt es prima: Starte mit 0 und addiere fortlaufend die zweiten Werte der Tupel hinzu. Wieder ein kleiner Test:

List((1,544), (5,136), (11,68), (23,34)).foldLeft(0)(_+_._2)
//-->res3: Int = 782

Damit sind hätten wir alle Zutaten beisammen und sind fertig. Der Trick beim Schreiben solcher Funktionen ist, sich vom typischen „Schleifendenken“ in Java zu lösen, und stattdessen die Aufgabe in logische Schritte zu zerteilen: „Erst einmal brauche ich die ganzen Wertepaare, vielleicht in einer Liste oder so. Wenn ich die habe, werfe ich alle mit geradem ersten Wert weg und addiere die zweiten Werte vom Rest zusammen“.

So, ich hoffe, dass jetzt der obige Code nicht mehr ganz so furchteinflößend aussieht. War doch gar nicht so schlimm, oder?

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