Maximaler Wert in einer Liste rekursiv in Scala

Question

Ich bin neu in Scala, gibt es eine bessere Möglichkeit, dies mit dem grundlegendsten Wissen möglich auszudrücken?

def findMax(xs: List[Int]): Int = { 
     xs match { 
     case x :: tail => (if (tail.length==0) x else (if(x>findMax(tail)) x else (findMax(tail)))) 
     } 
    } 

Answer 1

Sie sind zwei Probleme hier. Zuerst rufen Sie tail.length an, was eine Operation der Bestellung O(N) ist, also kostet Sie das im schlimmsten Fall N * N Schritte, wobei N die Länge der Sequenz ist. Die zweite ist, dass Ihre Funktion nicht tail-rekursiv ist - Sie verschachteln die findMax Aufrufe "von außen nach innen".

Die übliche Strategie die richtige rekursive Funktion zu schreiben, ist

• über jedes mögliche Muster Fall zu denken: hier gibt es entweder die leere Liste Nil oder die nicht-leere Liste head :: tail haben. Dies löst dein erstes Problem.
• , um das temporäre Ergebnis (hier die aktuelle Schätzung des Maximalwerts) als weiteres Argument der Funktion mitzuführen. Dies löst Ihr zweites Problem.

Das gibt:

import scala.annotation.tailrec 

@tailrec 
def findMax(xs: List[Int], max: Int): Int = xs match { 
    case head :: tail => findMax(tail, if (head > max) head else max) 
    case Nil => max 
} 

val z = util.Random.shuffle(1 to 100 toList) 
assert(findMax(z, Int.MinValue) == 100) 

Wenn Sie das zusätzliche Argument nicht verfügbar machen möchten, können Sie eine innere Hilfsfunktion schreiben.

def findMax(xs: List[Int]): Int = { 
    @tailrec 
    def loop(ys: List[Int], max: Int): Int = ys match { 
    case head :: tail => loop(tail, if (head > max) head else max) 
    case Nil => max 
    } 
    loop(xs, Int.MinValue) 
} 

val z = util.Random.shuffle(1 to 100 toList) 
assert(findMax(z) == 100) 

Zur Vereinfachung kehren wir Int.MinValue, wenn die Liste leer ist. Eine bessere Lösung könnte darin bestehen, eine Ausnahme für diesen Fall auszulösen.

---

Die @tailrec Anmerkung hier optional ist, versichert es einfach, dass wir in der Tat einen Schwanz rekursive Funktion definiert. Dies hat den Vorteil, dass wir keinen Stack-Overflow erzeugen können, wenn die Liste extrem lang ist.

Answer 2

Wenn Sie eine Sammlung auf einen einzelnen Wert reduzieren, sollten Sie eine der Funktionen fold anstelle einer expliziten Rekursion verwenden.

List(3,7,1).fold(Int.MinValue)(Math.max) 
// 7 

Answer 3

Verwendung Muster eine Rekursion passende,

def top(xs: List[Int]): Int = xs match { 
    case Nil  => sys.error("no max in empty list") 
    case x :: Nil => x 
    case x :: xs => math.max(x, top(xs)) 
} 

Pattern Matching wird verwendet, um die Liste in dem Kopf zu zersetzen und ruhen. Eine einzelne Elementliste wird mit x :: Nil bezeichnet. Wir untersuchen den Rest der Liste und vergleichen für jede rekursive Stufe das Maximum auf dem Kopfelement der Liste. Um die Fälle erschöpfend zu machen (um eine wohldefinierte Funktion zu erhalten), betrachten wir auch leere Listen (Nil).

Answer 4

def maxl(xl: List[Int]): Int = { 
    if ((xl.head > xl.tail.head) && (xl.tail.length >= 1)) 
    return xl.head 
    else 
    if(xl.tail.length == 1) 
     xl.tail.head 
    else 
     maxl(xl.tail) 
}