Эффективная итерация с индексом в Scala

Поскольку в Scala нет старых forциклов в стиле Java с индексом,

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

Как мы можем эффективно выполнять итерацию, не используя var's?

Ты мог бы сделать это

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

но список просматривается дважды - не очень эффективно.

Намного хуже, чем двойной обход, он создает промежуточный массив пар. Вы можете использовать view. Когда вы это сделаете collection.view, вы можете думать о последующих вызовах как о ленивых действиях во время итерации. Если вы хотите получить обратно полностью реализованную коллекцию, звоните forceв конце. Здесь это было бы бесполезно и дорого. Так что измените свой код на

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

Было отмечено , что Scala делает имеет синтаксис для forпетель:

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

или просто

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

Однако вы также просили об эффективности. Оказывается, forсинтаксис Scala на самом деле является синтаксическим сахаром для методов более высокого порядка, таких как map, foreachи т. Д. Таким образом, в некоторых случаях эти циклы могут быть неэффективными, например, как оптимизировать циклы for и циклы в Scala?

(Хорошая новость в том, что команда Scala работает над улучшением этого. Проблема в системе отслеживания ошибок: https://issues.scala-lang.org/browse/SI-4633 )

Для максимальной эффективности можно использовать whileцикл или, если вы настаиваете на исключении использования varхвостовой рекурсии:

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

Обратите внимание, что необязательная @tailrec аннотация полезна для обеспечения того, чтобы метод действительно рекурсивный. Компилятор Scala переводит хвостовые рекурсивные вызовы в байтовый код, эквивалентный циклам while.

Еще один способ:

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

Собственно, в scala есть старые циклы в стиле Java с индексом:

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

Где 0 until xs.lengthили 0.until(xs.length)- RichIntметод, который возвращает Rangeподходящий для цикла.

Кроме того, вы можете попробовать цикл с 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

Как насчет этого?

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

Вывод:

0: One
1: Two
2: Three

Зацикливание в scala довольно просто. Создайте любой массив по вашему выбору, например.

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

Виды петель,

for(data <- myArray)println(data)

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

Действительно, вызов zipWithIndexколлекции будет проходить по ней, а также создавать новую коллекцию для пар. Чтобы этого избежать, вы можете просто вызвать zipWithIndexитератор для коллекции. Это просто вернет новый итератор, который отслеживает индекс во время итерации, поэтому без создания дополнительной коллекции или дополнительного обхода.

Вот как scala.collection.Iterator.zipWithIndexэто реализовано в 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
    }
  }

Это должно быть даже немного эффективнее, чем создание представления коллекции.

В stdlib нет ничего, что могло бы сделать это за вас без создания мусора кортежей, но написать свое собственное не так уж и сложно. К сожалению, я никогда не удосужился выяснить, как сделать правильный неявный дождь CanBuildFrom, чтобы сделать такие вещи общими для того типа коллекции, к которой они применяются, но если это возможно, я уверен, что кто-то просветит нас. :)

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

Еще несколько способов итерации:

scala>  xs.foreach (println) 
first
second
third

foreach и тому подобное, карта, которая что-то вернет (результаты функции, для println это Unit, то есть список единиц)

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

работать с элементами, а не с индексом

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

складывание

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

можно сделать с рекурсией:

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) 

Переносимая часть - это всего лишь пример того, как что-то сделать с i и j. Это не обязательно должен быть Int.

для более простых вещей, ближе к обычным циклам 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)

или без заказа:

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

У меня есть следующие подходы

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

   }
}

Простой и эффективный способ, вдохновленный реализацией transformв SeqLike.scala

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

Предлагаемые решения страдают тем фактом, что они либо явно перебирают коллекцию, либо помещают ее в функцию. Более естественно придерживаться обычных идиом Scala и помещать индекс в обычные методы map или foreach. Это можно сделать с помощью мемоизации. Результирующий код может выглядеть как

myIterable map (doIndexed(someFunction))

Вот способ достичь этой цели. Рассмотрим следующую утилиту:

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

Это уже все, что вам нужно. Вы можете применить это, например, следующим образом:

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

что приводит к списку

List(97, 99, 101)

Таким образом, вы можете использовать обычные Traversable-функции за счет обертывания вашей эффективной функции. Наслаждайтесь!