Effiziente Iteration mit Index in Scala

82

Da Scala keine alten Java- forSchleifen mit Index hat,

// does not work
val xs = Array("first", "second", "third")
for (i=0; i<xs.length; i++) {
  println("String #" + i + " is " + xs(i))
}

Wie können wir effizient und ohne Verwendung von vars iterieren ?

Du könntest das tun

val xs = Array("first", "second", "third")
val indexed = xs zipWithIndex
for (x <- indexed) println("String #" + x._2 + " is " + x._1)

Die Liste wird jedoch zweimal durchlaufen - nicht sehr effizient.

bissig
quelle
Dies sind alles gute Antworten. Was mir in Java 'for'-Schleifen fehlt, ist die Fähigkeit, mehrere Initialisierer zu haben, und die Fähigkeit, mit mehr als nur Inkrementen / Dekrementen zu "iterieren". Dies ist eine Instanz, in der Java präziser sein kann als Scala.
bissig
... "iterieren" mit mehr als nur Inkrementen / Dekrementen ... In Scala ist es möglich, mit Schritt zu iterieren oder mit "if" -Bedingung im Schleifenheader zu iterieren. Oder suchen Sie etwas anderes?
Om-Nom-Nom
1
/ * Java * / for (int i = 0, j = 0; i + j <100; i + = j * 2, j + = i + 2) {...} Wie können Sie dies in einer Zeile in Scala tun?
bissig
3
@snappy: Meiner Meinung nach wäre die natürlichste Übersetzung zu Scala eine whileSchleife. Soweit ich mich erinnere, gab es vor einigen Jahren eine Debatte darüber, ob Scala Javas for(;;)Schleife erben sollte , und es wurde entschieden, dass der Nutzen nicht ausreichte, um die zusätzliche Komplexität zu rechtfertigen.
Kipton Barros

Antworten:

130

Viel schlimmer als zweimaliges Durchlaufen, erzeugt es ein Zwischenarray von Paaren. Sie können verwenden view. Wenn Sie dies tun collection.view, können Sie sich nachfolgende Anrufe als träge während der Iteration vorstellen. Wenn Sie eine ordnungsgemäß vollständig realisierte Sammlung zurückerhalten möchten, rufen Sie forceam Ende an. Hier wäre das nutzlos und teuer. Ändern Sie also Ihren Code in

for((x,i) <- xs.view.zipWithIndex) println("String #" + i + " is " + x)
Didier Dupont
quelle
6
Gute Idee, nur eine Durchquerung, aber es werden auch n Paare erstellt, auch wenn keine neue Sammlung erstellt wird.
bissig
2
Ganz richtig. Nun, es mag eine vage Hoffnung geben, dass die JVM diese Kreation wegoptimiert, aber darauf würde ich nicht zählen. Ich sehe keine Lösung, die dann nicht auf der Iteration von Indizes basieren würde.
Didier Dupont
1
@snappy Dieser sollte als Antwort gewählt worden sein! Der Zugriff auf Elemente über den Index, der in den meisten anderen Antworten vorgeschlagen wurde, verstößt gegen die Funktionsweise von Scala und führt bei verknüpften Listen (wie Listder am häufigsten verwendeten Sammlung in Scala) zu einer schrecklichen Leistung - und nicht nur bei diesen. Überprüfen Sie die applyOperation hier . In einer verknüpften listenähnlichen Sammlung führt jeder Zugriff auf ein Element nach Index zu einem Durchlaufen der Liste.
Nikita Volkov
Hier werden ganz andere Ansätze gezeigt: stackoverflow.com/questions/6821194/…
Neil
Warum ist das effizient? Es erstellt ein neues Array-Objekt und verwendet eine zusätzliche Funktion (`view '), sodass ich nur schwer erkennen kann, warum dies für den Entwickler oder die Maschine effizient ist, abgesehen davon, dass ich mich schlau idiomatisch fühle.
Matanster
69

Es wurde erwähnt , dass Scala tut haben Syntax für forSchleifen:

for (i <- 0 until xs.length) ...

oder einfach

for (i <- xs.indices) ...

Sie haben jedoch auch nach Effizienz gefragt. Es stellt sich heraus , dass die Scala forSyntax höherer Ordnung Methoden wie eigentlich syntaktischer Zucker ist map, foreachusw. Als solche in einigen Fällen diese Schleifen kann ineffizient sein, zB Wie optimize for-Comprehensions und Schleifen in Scala?

(Die gute Nachricht ist, dass das Scala-Team daran arbeitet, dies zu verbessern. Hier ist das Problem im Bug-Tracker: https://issues.scala-lang.org/browse/SI-4633 )

Um ein Höchstmaß an Effizienz zu erzielen, können Sie eine whileSchleife oder, wenn Sie darauf bestehen, die Verwendung von zu verwenden var, die Schwanzrekursion verwenden:

import scala.annotation.tailrec

@tailrec def printArray(i: Int, xs: Array[String]) {
  if (i < xs.length) {
    println("String #" + i + " is " + xs(i))
    printArray(i+1, xs)
  }
}
printArray(0, Array("first", "second", "third"))

Beachten Sie, dass die optionale @tailrec Annotation hilfreich ist, um sicherzustellen, dass die Methode tatsächlich rekursiv ist. Der Scala-Compiler übersetzt rekursive Aufrufe in den Bytecode, der while-Schleifen entspricht.

Kipton Barros
quelle
+1 für die Erwähnung der Methode / Funktion von Indizes, wie ich es für vorzuziehen halte, da praktisch eine ganze Reihe von Programmierfehlern nacheinander beseitigt werden.
chaotic3quilibrium
1
Es muss hier angemerkt werden, dass, wenn xses sich um eine verknüpfte Liste handelt (wie die weit verbreitete List), der Zugriff auf ihre Elemente über einen Index xs(i)linear ist und daher for (i <- xs.indices) println(i + " : " + xs(i))eine for((x, i) <- xs.zipWithIndex) println(i + " : " + x)weitaus schlechtere Leistung als gerade erzielt wird , da dies zu viel mehr als nur führt zwei Durchquerungen unter der Haube. Daher sollte die Antwort von @didierd, die die Verwendung von Ansichten vorschlägt, als die allgemeinste und idiomatischste, IMO, akzeptiert werden.
Nikita Volkov
1
Wenn maximale Effizienz erforderlich ist (z. B. beim numerischen Rechnen), ist es schneller, Arrays zu indizieren, als eine verknüpfte Liste zu durchlaufen. Die Knoten einer verknüpften Liste werden separat Heap zugewiesen, und das Springen über verschiedene Speicherorte funktioniert nicht gut mit dem CPU-Cache. Wenn a viewverwendet wird, übt diese selbst hohe Abstraktionsebene mehr Druck auf den Heap und den GC aus. Nach meiner Erfahrung kann die Leistung häufig um den Faktor 10 gesteigert werden, indem die Heap-Zuordnung im numerischen Code vermieden wird.
Kipton Barros
20

Noch ein Weg:

scala> val xs = Array("first", "second", "third")
xs: Array[java.lang.String] = Array(first, second, third)

scala> for (i <- xs.indices)
     |   println(i + ": " + xs(i))
0: first
1: second
2: third
fehlender Faktor
quelle
5
Ich mag es wirklich, wenn Sie auf die Methode / Funktion der Indizes hinweisen. Es reduziert die Komplexität und eliminiert praktisch eine ganze Reihe von "Off-by-One" -Fehlern, was der häufigste Programmierfehler / -fehler in der gesamten Softwareentwicklung ist.
chaotic3quilibrium
14

Tatsächlich hat Scala alte Java-Schleifen mit Index:

scala> val xs = Array("first","second","third")
xs: Array[java.lang.String] = Array(first, second, third)

scala> for (i <- 0 until xs.length)
     | println("String # " + i + " is "+ xs(i))

String # 0 is first
String # 1 is second
String # 2 is third

Wobei 0 until xs.lengthoder 0.until(xs.length)ist eine RichIntMethode, die Rangefür eine Schleife geeignet ist.

Sie können auch versuchen, Schleife mit to:

scala> for (i <- 0 to xs.length-1)
     | println("String # " + i + " is "+ xs(i))
String # 0 is first
String # 1 is second
String # 2 is third
OM Nom Nom
quelle
5
xs(i)auf Listen erhöht die Komplexität auf O (n ^ 2)
Vadzim
@Vadzim Das stimmt, aber das wäre auch der Fall , in Java sein in Sie eine for - Schleife auf den Indizes mit einem LinkedList verwendet
francoisr
1
Im Fall von xs (i) auf Arrays lautet der obige Code O (n), richtig? Da Arrays in Scala nahezu zeitlich konstanten Direktzugriff bieten?
Dhfromkorea
2
@dhfromkorea ja, sollte schnell für Arrays sein (in der Tat O (n))
om-nom-nom
6

Wie wäre es damit?

val a = Array("One", "Two", "Three")
a.foldLeft(0) ((i, x) => {println(i + ": " + x); i + 1;} )

Ausgabe:

0: One
1: Two
2: Three
Matthew Saltz
quelle
4

Das Einlaufen in Scala ist ziemlich einfach. Erstellen Sie beispielsweise ein Array Ihrer Wahl.

val myArray = new Array[String](3)
myArray(0)="0";
myArray(1)="1";
myArray(2)="2";

Arten von Schleifen,

for(data <- myArray)println(data)

for (i <- 0 until myArray.size)
println(i + ": " + myArray(i))
Prakhyat
quelle
4

Wenn Sie zipWithIndexeine Sammlung aufrufen, wird diese durchlaufen und eine neue Sammlung für die Paare erstellt. Um dies zu vermeiden, können Sie einfach zipWithIndexden Iterator für die Sammlung aufrufen . Dadurch wird nur ein neuer Iterator zurückgegeben, der den Index während der Iteration verfolgt, ohne dass eine zusätzliche Sammlung oder ein zusätzliches Durchlaufen erstellt werden muss.

So wird scala.collection.Iterator.zipWithIndexderzeit in 2.10.3 implementiert:

  def zipWithIndex: Iterator[(A, Int)] = new AbstractIterator[(A, Int)] {
    var idx = 0
    def hasNext = self.hasNext
    def next = {
      val ret = (self.next, idx)
      idx += 1
      ret
    }
  }

Dies sollte sogar etwas effizienter sein als das Erstellen einer Ansicht für die Sammlung.

ihr Mann
quelle
3

Es gibt nichts in der stdlib, was es für Sie tun könnte, ohne Tupelmüll zu erzeugen, aber es ist nicht zu schwer, Ihren eigenen zu schreiben. Leider habe ich mich nie darum gekümmert, herauszufinden, wie man die richtige implizite CanBuildFrom-Raindance ausführt, um solche Dinge in der Art der Sammlung, auf die sie angewendet werden, generisch zu machen, aber wenn es möglich ist, wird uns sicher jemand aufklären. :) :)

def foreachWithIndex[A](as: Traversable[A])(f: (Int,A) => Unit) {
  var i = 0
  for (a <- as) {
    f(i, a)
    i += 1
  }
}

def mapWithIndex[A,B](in: List[A])(f: (Int,A) => B): List[B] = {
  def mapWithIndex0(in: List[A], gotSoFar: List[B], i: Int): List[B] = {
    in match {
      case Nil         => gotSoFar.reverse
      case one :: more => mapWithIndex0(more, f(i, one) :: gotSoFar, i+1)
    }
  }
  mapWithIndex0(in, Nil, 0)
}

// Tests....

@Test
def testForeachWithIndex() {
  var out = List[Int]()
  ScalaUtils.foreachWithIndex(List(1,2,3,4)) { (i, num) =>
    out :+= i * num
  }
  assertEquals(List(0,2,6,12),out)
}

@Test
def testMapWithIndex() {
  val out = ScalaUtils.mapWithIndex(List(4,3,2,1)) { (i, num) =>
    i * num
  }

  assertEquals(List(0,3,4,3),out)
}
Alex Cruise
quelle
Dies ist definitiv sinnvoll, um zur Standardbibliothek hinzugefügt zu werden.
bissig
1
Ich bin mir nicht so sicher, denn wenn Sie sich an die üblichen foreach / map-APIs anpassen möchten, stecken Sie sowieso mit Tupeln fest.
Alex Cruise
3

Einige weitere Möglichkeiten zum Iterieren:

scala>  xs.foreach (println) 
first
second
third

foreach und ähnliche Karte, die etwas zurückgeben würde (die Ergebnisse der Funktion, die für println Unit ist, also eine Liste von Einheiten)

scala> val lens = for (x <- xs) yield (x.length) 
lens: Array[Int] = Array(5, 6, 5)

arbeite mit den Elementen, nicht mit dem Index

scala> ("" /: xs) (_ + _) 
res21: java.lang.String = firstsecondthird

falten

for(int i=0, j=0; i+j<100; i+=j*2, j+=i+2) {...}

kann mit Rekursion durchgeführt werden:

def ijIter (i: Int = 0, j: Int = 0, carry: Int = 0) : Int =
  if (i + j >= 100) carry else 
    ijIter (i+2*j, j+i+2, carry / 3 + 2 * i - 4 * j + 10) 

Das Carry-Teil ist nur ein Beispiel, um etwas mit i und j zu tun. Es muss kein Int sein.

für einfachere Sachen, näher an üblichen For-Loops:

scala> (1 until 4)
res43: scala.collection.immutable.Range with scala.collection.immutable.Range.ByOne = Range(1, 2, 3)

scala> (0 to 8 by 2)   
res44: scala.collection.immutable.Range = Range(0, 2, 4, 6, 8)

scala> (26 to 13 by -3)
res45: scala.collection.immutable.Range = Range(26, 23, 20, 17, 14)

oder ohne Bestellung:

List (1, 3, 2, 5, 9, 7).foreach (print) 
Benutzer unbekannt
quelle
3

Ich habe die folgenden Ansätze

object HelloV2 {

   def main(args: Array[String]) {

     //Efficient iteration with index in Scala

     //Approach #1
     var msg = "";

     for (i <- args.indices)
     {
       msg+=(args(i));
     }
     var msg1="";

     //Approach #2
     for (i <- 0 until args.length) 
     {
       msg1 += (args(i));
     }

     //Approach #3
     var msg3=""
     args.foreach{
       arg =>
        msg3 += (arg)
     }


      println("msg= " + msg);

      println("msg1= " + msg1);

      println("msg3= " + msg3);

   }
}
Anish
quelle
2

Ein einfacher und effizienter Weg, inspiriert von der Implementierung transformin SeqLike.scala

    var i = 0
    xs foreach { el =>
      println("String #" + i + " is " + xs(i))
      i += 1
    }
Adrian
quelle
0

Die vorgeschlagenen Lösungen leiden unter der Tatsache, dass sie entweder explizit über eine Sammlung iterieren oder die Sammlung in eine Funktion einfügen. Es ist natürlicher, sich an die üblichen Redewendungen von Scala zu halten und den Index in die üblichen Karten- oder Foreach-Methoden einzufügen. Dies kann durch Auswendiglernen erfolgen. Der resultierende Code könnte so aussehen

myIterable map (doIndexed(someFunction))

Hier ist ein Weg, um diesen Zweck zu erreichen. Betrachten Sie das folgende Dienstprogramm:

object TraversableUtil {
    class IndexMemoizingFunction[A, B](f: (Int, A) => B) extends Function1[A, B] {
        private var index = 0
        override def apply(a: A): B = {
            val ret = f(index, a)
            index += 1
            ret
        }
    }

    def doIndexed[A, B](f: (Int, A) => B): A => B = {
        new IndexMemoizingFunction(f)
    }
}

Das ist schon alles was du brauchst. Sie können dies beispielsweise wie folgt anwenden:

import TraversableUtil._
List('a','b','c').map(doIndexed((i, char) => char + i))

was zu der Liste führt

List(97, 99, 101)

Auf diese Weise können Sie die üblichen Traversable-Funktionen auf Kosten der Umhüllung Ihrer effektiven Funktion verwenden. Genießen!

Matt Brasen
quelle