Scala: Wie für das Verständnis von einem verschachtelten brechen

Question

Ich versuche, einige Codes wie unten zu schreiben -

def kthSmallest(matrix: Array[Array[Int]], k: Int): Int = { 
    val pq = new PriorityQueue[Int]() //natural ordering 
    var count = 0 

    for (
    i <- matrix.indices; 
    j <- matrix(0).indices 
) yield { 
     pq += matrix(i)(j) 
     count += 1 
    } //This would yield Any! 

    pq.dequeue() //kth smallest. 

} 

Meine Frage ist, dass ich nur eine Schleife wollen, bis die Zeitzählung kleiner als k (etwas wie takeWhile (count! = k)), aber da ich auch Elemente in die Prioritätswarteschlange in der Ausbeute einfüge, wird dies im aktuellen Zustand nicht funktionieren.

Meine anderen Optionen sind, eine verschachtelte Schleife zu schreiben und zurückzukehren, sobald die Anzahl k erreicht. Ist es möglich mit Ertrag zu tun? Ich konnte es noch nicht idiomatisch finden. Alle Hinweise wären hilfreich.

Answer 1

Es ist nicht idiomatisch für Scala, var s oder Break-Schleifen zu verwenden. Sie können für Rekursion, faule Bewertung oder Klebeband eine break gehen, auf etwas Leistung (wie return, es ist als Ausnahme implementiert, und wird nicht gut genug). Hier sind die Optionen unterteilt:

1. Verwendung Rekursion - rekursive Algorithmen sind die analoge von Schleifen in funktionalen Sprachen

   def kthSmallest(matrix: Array[Array[Int]], k: Int): Int = { 
       val pq = new PriorityQueue[Int]() //natural ordering 
   
       @tailrec 
       def fillQueue(i: Int, j: Int, count: Int): Unit = 
       if (count >= k || i >= matrix.length)() 
       else { 
        pq += matrix(i)(j) 
        fillQueue(
        if (j >= matrix(i).length - 1) i + 1 else i, 
        if (j >= matrix(i).length - 1) 0 else j + 1, 
        count + 1) 
       } 
   
       fillQueue(0, 0, 0) 
   
       pq.dequeue() //kth smallest. 
   } 
   

2. Verwenden Sie eine faule Struktur, wie chengpohi vorgeschlagen - dies nicht sehr klingen ähnlich wie eine reine Funktion. Ich würde vorschlagen, in diesem Fall eine Iterator anstelle einer Stream zu verwenden - da Iteratoren nicht die Schritte notieren, die sie durchlaufen haben (könnte Speicher für große Matrizen verschonen).

3. Für bereit diejenigen verzweifelt break zu verwenden, unterstützt Scala es in einem aufsetzbaren Art und Weise (beachten Sie die Leistung Vorbehalt oben erwähnt):

   import scala.util.control.Breaks 
   
   breakable { 
       // loop code 
       break 
   } 
   

Answer 2

Es gibt einen Weg mit der Streamfaul Bewertung, dies zu tun. Da for yield-flatMap gleich ist, können Sie for yield-flatMap mit Stream konvertieren:

matrix.indices.toStream.flatMap(i => { 
    matrix(0).indices.toStream.map(j => { 
    pq += matrix(i)(j) 
    count += 1 
    }) 
}).takeWhile(_ => count <= k) 

Verwenden toStream die Sammlung zu Stream, konvertieren und da Stream ist lazy evaluation, so können wir takeWhile zu verwenden Prädikat count, um die weniger Schleifen ohne init andere zu beenden.