Scala中的高效索引迭代

95

由于Scala没有旧的Java风格的带索引的for循环,

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

我们如何高效地迭代,而且不使用var

你可以这样做

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

但是这个列表被遍历了两次——并不是很高效。


这些都是很好的回应。我在Java的“for”循环中缺少的是具有多个初始化程序的能力,以及使用除增量/减量之外的更多迭代方式的能力。这是Java比Scala更简洁的一个例子。 - snappy
在编程中,“迭代”不仅可以使用增量/减量。在Scala中,可以使用步长进行迭代,或者在循环头中使用“if”条件进行迭代。或者您正在寻找其他内容? - om-nom-nom
1
/Java/ for(int i=0, j=0; i+j<100; i+=j*2, j+=i+2) {...} 你如何在Scala中用一行代码实现这个功能? - snappy
3
在我看来,将Scala翻译成最自然的方式是使用while循环。据我回忆,几年前曾经有一个争论,是否应该让Scala继承Java的for(;;)循环,而当时决定不采用这种方式是因为其增加的复杂性没有带来足够的好处。 - Kipton Barros
12个回答

146

遍历两次比这个糟糕得多,它会创建一个中间的键值对数组。 你可以使用 view。当你执行 collection.view时,你可以将后续的调用看作是在迭代期间进行的惰性操作。如果你想要获得一个完全实现的集合,你可以在最后调用 force。但在这里,这样做是无用且昂贵的。所以请修改你的代码为:

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

6
好的主意,只需要一次遍历,但它仍会创建n对,即使不创建新集合。 - snappy
2
非常正确。也许JVM可以优化这些创建,但我不会指望它。我认为唯一的解决方案是基于索引迭代。 - Didier Dupont
1
@snappy 这个应该被选为答案!通过索引访问元素违反了Scala的函数式特性,并且在链表(如List,Scala中最常用的集合)上表现非常糟糕 - 不仅仅是在链表上。请查看这里apply操作。在类似于链表的集合中,每次通过索引访问元素都会导致对列表的遍历。 - Nikita Volkov
这里展示了不同的方法:https://dev59.com/_Gw15IYBdhLWcg3wG4AJ - Neil
为什么这样更有效率呢?它创建了一个新的数组对象,并使用了一个额外的函数(`view'),所以我很难看出这对开发者或机器来说为什么是高效的,除了感觉上聪明而惯用。 - matanster
@DidierDupont 怎么获取返回值,return x 报错了。 - RUDRA GANESH SUBBARAYULU

77

有人提到Scala确实有for循环的语法:

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

或者简单地说

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

然而,你也提到了效率。实际上,Scala的for语法是高阶方法(如mapforeach等)的语法糖。因此,在某些情况下,这些循环可能效率低下,例如:如何优化Scala中的for-comprehensions和loops?

好消息是,Scala团队正在努力改进这一点。以下是bug跟踪器中的问题链接: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循环的字节码等价形式。


+1 是因为我发现 indices 方法/函数更可取,因为它几乎消除了一整套的 off-by-one 编程错误。 - chaotic3quilibrium
1
需要注意的是,如果xs是任何类型的链表(例如广泛使用的List),像xs(i)这样通过索引访问它的元素将是线性的,因此for (i <- xs.indices) println(i + " : " + xs(i)) 的性能甚至比for((x, i) <- xs.zipWithIndex) println(i + " : " + x)还要差,因为它会在底层导致多次遍历。因此,建议使用视图的答案@didierd应该被接受为最通用和最符合惯用法的答案,在我看来。 - Nikita Volkov
1
如果需要最大效率(例如在数值计算中),索引数组比遍历链表更快。链表的节点是单独堆分配的,跳跃到不同的内存位置与CPU缓存不兼容。如果使用“视图”,即使高级别的抽象也会对堆和GC施加更大的压力。根据我的经验,在数值代码中避免堆分配可以获得10倍的性能提升。 - Kipton Barros
嗨。我对Scala还不熟悉。我想问一下,为什么在定义printArray()函数时没有使用"="符号? - Seven

20

还有一种方式:

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

5
我很喜欢你指出索引方法/函数。它能降低复杂度,几乎消除了一组“偏移量为一”的错误,这是软件工程中最常见的编程错误/漏洞之一。 - chaotic3quilibrium

17

实际上,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.length0.until(xs.length)是一个返回Range适用于循环的RichInt方法。

此外,您还可以尝试使用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
在列表中使用xs(i)会使复杂度变为O(n^2)。 - Vadzim
@Vadzim 这是真的,但如果你在 LinkedList 上使用索引的 for 循环,在 Java 中也会出现这种情况。 - francoisr
1
在数组中使用xs(i)时,上述代码是O(n),对吗?由于Scala中的数组提供几乎恒定时间的随机访问。 - dhfromkorea
3
@dhfromkorea 是的,对于数组来说应该很快(确实是O(n))。 - om-nom-nom

6
这个怎么样?
val a = Array("One", "Two", "Three")
a.foldLeft(0) ((i, x) => {println(i + ": " + x); i + 1;} )

输出:

0: One
1: Two
2: Three

5
在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))

5
我有以下几种方法:
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);

   }
}

4

在集合上调用 zipWithIndex 方法会遍历集合并创建一个新的包含索引对的集合。为了避免这种情况,可以直接在集合的迭代器上调用 zipWithIndex 方法。这将返回一个新的迭代器,它会在迭代时跟踪索引,而不会创建额外的集合或进行额外的遍历。

下面是 2.10.3 版本中 scala.collection.Iterator.zipWithIndex 的实现方式:

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

这甚至比在集合上创建视图更有效率。

3

标准库中没有现成的方法可以帮你避免创建元组垃圾,但自己实现并不难。可惜我从未花时间去弄清楚如何进行适当的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)
}

这是一定要添加到标准库中的东西。 - snappy
1
我不太确定,因为如果你想符合通常的foreach/map API,你仍然需要使用元组。 - Alex Cruise

2

更多的迭代方式:

scala>  xs.foreach (println) 
first
second
third

foreach等类似函数,以及map函数会返回某些东西(函数的结果,对于println函数来说是Unit类型,因此返回一个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) {...}

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) 

carry-part只是一些示例,用于处理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) 

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接