Wydajna iteracja z indeksem w Scali

Ponieważ Scala nie ma starych forpętli w stylu Java z indeksem,

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

Jak możemy wydajnie iterować bez używania var?

Możesz to zrobić

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

ale lista jest przeglądana dwukrotnie - niezbyt wydajna.

Znacznie gorzej niż dwukrotne przechodzenie, tworzy pośredni zestaw par. Możesz użyć view. Kiedy to zrobisz collection.view, możesz myśleć, że kolejne wywołania działają leniwie podczas iteracji. Jeśli chcesz odzyskać w pełni zrealizowaną kolekcję, dzwonisz forcena koniec. Tutaj byłoby to bezużyteczne i kosztowne. Więc zmień swój kod na

for((x,i) <- xs.view.zipWithIndex) println("String #" + i + " is " + x)

Wspomniano już, że Scala nie ma składni forpętli:

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

lub po prostu

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

Jednak prosiłeś również o wydajność. Okazuje się, że Scala forskładnia jest rzeczywiście cukier syntaktyczny dla wyższego rzędu, takich jak metody map, foreachitd Jako takie, w niektórych przypadkach te pętle mogą być nieskuteczne, np jak zoptymalizować dla-listowe i pętli w Scala?

(Dobra wiadomość jest taka, że ​​zespół Scala pracuje nad poprawieniem tego. Oto problem w narzędziu do śledzenia błędów: https://issues.scala-lang.org/browse/SI-4633 )

Aby uzyskać najwyższą wydajność, można użyć whilepętli lub, jeśli nalegasz na usunięcie zastosowań var, rekurencji ogonowej:

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"))

Zauważ, że opcjonalna @tailrec adnotacja jest przydatna, aby upewnić się, że metoda jest rzeczywiście rekurencyjna. Kompilator Scala tłumaczy wywołania rekurencyjne tail na kod bajtowy odpowiednika pętli while.

Jeszcze jeden sposób:

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

Właściwie scala ma stare pętle w stylu Java z indeksem:

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

Gdzie 0 until xs.lengthlub 0.until(xs.length)jest RichIntmetodą, która zwraca Rangeodpowiednią do zapętlenia.

Możesz także wypróbować pętlę za pomocą 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

Co powiesz na to?

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

Wynik:

0: One
1: Two
2: Three

Zapętlenie w scali jest dość proste. Utwórz dowolną tablicę, np.

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

Rodzaje pętli,

for(data <- myArray)println(data)

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

Rzeczywiście, wywołanie zipWithIndexkolekcji przejdzie przez nią, a także stworzy nową kolekcję dla par. Aby tego uniknąć, możesz po prostu wywołać zipWithIndexiterator kolekcji. Spowoduje to po prostu zwrócenie nowego iteratora, który śledzi indeks podczas iteracji, więc bez tworzenia dodatkowej kolekcji lub dodatkowego przechodzenia.

Oto jak scala.collection.Iterator.zipWithIndexjest obecnie zaimplementowane w 2.10.3:

  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
    }
  }

Powinno to być nawet bardziej wydajne niż tworzenie widoku kolekcji.

W stdlib nie ma nic, co zrobi to za Ciebie bez tworzenia krotek śmieci, ale nie jest zbyt trudne napisanie własnego. Niestety nigdy nie zadałem sobie trudu, aby dowiedzieć się, jak zrobić właściwy CanBuildFrom ukryty taniec, aby takie rzeczy były ogólne w typie kolekcji, do której są stosowane, ale jeśli to możliwe, jestem pewien, że ktoś nas oświeci. :)

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)
}

Więcej sposobów na iterację:

scala>  xs.foreach (println) 
first
second
third

foreach i podobna mapa, która zwróciłaby coś (wyniki funkcji, która jest dla println, Unit, a więc List of Units)

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

pracować z elementami, a nie indeksem

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

składanie

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

można zrobić z rekurencją:

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) 

Część przenosząca to tylko przykład zrobienia czegoś z i i j. Nie musi to być Int.

dla prostszych rzeczy, bliżej zwykłych pętli for:

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)

lub bez zamówienia:

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

Mam następujące podejścia

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);

   }
}

Prosty i skuteczny sposób, zainspirowany wdrożeniem transformw SeqLike.scala

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

Proponowane rozwiązania obarczone są tym, że albo jawnie iterują po kolekcji, albo umieszczają ją w funkcji. Bardziej naturalne jest trzymanie się zwykłych idiomów Scali i umieszczanie indeksu wewnątrz zwykłych metod map- lub foreach. Można to zrobić za pomocą zapamiętywania. Wynikowy kod może wyglądać tak

myIterable map (doIndexed(someFunction))

Oto sposób na osiągnięcie tego celu. Rozważ następujące narzędzie:

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)
    }
}

To już wszystko, czego potrzebujesz. Możesz to zastosować na przykład w następujący sposób:

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

co powoduje wyświetlenie listy

List(97, 99, 101)

W ten sposób możesz używać zwykłych funkcji Traversable kosztem opakowywania efektywnej funkcji. Cieszyć się!