Efficient iteration with index in Scala

问题:

Since Scala does not have old Java style for loops with index,

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

How can we iterate efficiently, and without using var's?

You could do this

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

but the list is traversed twice - not very efficient.

回答1:

Much worse than traversing twice, it creates an intermediary array of pairs. You can use view. When you do collection.view, you can think of subsequent calls as acting lazily, during the iteration. If you want to get back a proper fully realized collection, you call force at the end. Here that would be useless and costly. So change your code to

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

回答2:

It has been mentioned that Scala does have syntax for for loops:

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

or simply

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

However, you also asked for efficiency. It turns out that the Scala for syntax is actually syntactic sugar for higher order methods such as map, foreach, etc. As such, in some cases these loops can be inefficient, e.g. How to optimize for-comprehensions and loops in Scala?

(The good news is that the Scala team is working on improving this. Here's the issue in the bug tracker: https://issues.scala-lang.org/browse/SI-4633)

For utmost efficiency, one can use a while loop or, if you insist on removing uses of var, tail recursion:

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

Note that the optional @tailrec annotation is useful for ensuring that the method is actually tail recursive. The Scala compiler translates tail-recursive calls into the byte code equivalent of while loops.

回答3:

One more way:

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

回答4:

Actually, scala has old Java-style loops with 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

Where 0 until xs.length or 0.until(xs.length) is a RichInt method which returns Range suitable for looping.

Also, you can try loop with 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

回答5:

How about this?

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

Output:

0: One
1: Two
2: Three

回答6:

Indeed, calling zipWithIndex on a collection will traverse it and also create a new collection for the pairs. To avoid this, you can just call zipWithIndex on the iterator for the collection. This will just return a new iterator that keeps track of the index while iterating, so without creating an extra collection or additional traversing.

This is how scala.collection.Iterator.zipWithIndex is currently implemented in 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
    }
  }

This should even be a bit more efficient than creating a view on the collection.

回答7:

There's nothing in the stdlib that will do it for you without creating tuple garbage, but it's not too hard to write your own. Unfortunately I've never bothered to figure out how to do the proper CanBuildFrom implicit raindance to make such things generic in the type of collection they're applied to, but if it's possible, I'm sure someone will enlighten us. :)

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

回答8:

Some more ways to iterate:

scala>  xs.foreach (println) 
first
second
third

foreach, and similar, map, which would return something (the results of the function, which is, for println, Unit, so a List of Units)

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

work with the elements, not the index

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

folding

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

can be done with recursion:

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) 

The carry-part is just some example, to do something with i and j. It needn't be an Int.

for simpler stuff, closer to usual 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)

or without order:

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

回答9:

Looping in scala is pretty simple. Create any array of your choice for ex.

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

Types of loops,

for(data <- myArray)println(data)

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

回答10:

A simple and efficient way, inspired from the implementation of transform in SeqLike.scala

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

回答11:

I have the following approaches

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

   }
}

回答12:

The proposed solutions suffer from the fact that they either explicitly iterate over a collection or stuff the collection into a function. It is more natural to stick with the usual idioms of Scala and put the index inside the usual map- or foreach-methods. This can be done using memoizing. The resulting code might look like

myIterable map (doIndexed(someFunction))

Here is a way to achieve this purpose. Consider the following utility:

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

This is already all you need. You can apply this for instance as follows:

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

which results in the list

List(97, 99, 101)

This way, you can use the usual Traversable-functions at the expense of wrapping your effective function. Enjoy!