代码之家 › 专栏 › 技术社区 › agilefall

创建scala列表的首选方法

scala

114

agilefall · 技术社区 · 15 年前

有几种方法可以在scala中构造不可变列表(请参见下面的人为示例代码)。可以使用可变的ListBuffer,创建 var 列出并修改它,使用 tail recursive 方法,可能还有其他我不知道的方法。

我本能地使用listbuffer,但我没有充分的理由这样做。是否有创建列表的首选或惯用方法,或者是否存在一种方法优于另一种方法的情况?

import scala.collection.mutable.ListBuffer

// THESE are all the same as: 0 to 3 toList.
def listTestA() ={
    var list:List[Int] = Nil

    for(i <- 0 to 3) 
        list = list ::: List(i)
    list
}


def listTestB() ={
    val list = new ListBuffer[Int]()

    for (i <- 0 to 3) 
        list += i
    list.toList
}


def listTestC() ={
    def _add(l:List[Int], i:Int):List[Int] = i match {
        case 3 => l ::: List(3)
        case _ => _add(l ::: List(i), i +1)
    }
    _add(Nil, 0)
}

9 回复 | 直到 8 年前

107

Daniel C. Sobral 15 年前

ListBuffer 是一个可变列表,它具有常量时间附加和常量时间转换为 List .

表 是不可变的,具有恒定的时间前置和线性时间附加。

如何构建列表取决于您将使用的算法以及元素创建的顺序。

例如,如果元素的使用顺序与它们的使用顺序相反,那么可以使用 表 做准备工作。无论您是否要使用尾部递归函数, foldLeft 或者其他不相关的东西。

如果元素的使用顺序相同,则 列表缓冲区 如果性能至关重要,则最可能是首选。

但是,如果您不在关键路径上,并且输入足够低,则可以始终 reverse 列表稍后,或只是 foldRight 或 颠倒 输入,即线性时间。

你什么不要使用的是 表 并附加到它上面。这将使您的性能比只在末尾进行预处理和反转差得多。

Tomasz Nurkiewicz 13 年前

对于简单情况:

val list = List(1,2,3)

Alexander Azarov 15 年前

嗯…这些对我来说太复杂了。我可以提议吗?

def listTestD = (0 to 3).toList

或

def listTestE = for (i <- (0 to 3).toList) yield i

Peter Mortensen John Conde 11 年前

您通常希望通过消除任何变量来关注scala中的不变性。可读性对你的同伴来说仍然很重要,所以:

尝试:

scala> val list = for(i <- 1 to 10) yield i
list: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

在大多数情况下,您甚至不需要转换为列表:)

索引序列将包含您需要的所有内容:

也就是说,您现在可以使用indexedseq:

scala> list.foldLeft(0)(_+_)
res0: Int = 55

Walter Chang 15 年前

我总是喜欢列表,我在“理解”之前使用“折叠/缩小”。但是,如果需要嵌套的“折叠”,则最好使用“用于理解”。如果我不能使用“fold/reduce/for”完成任务,那么递归是最后的方法。

因此,对于您的示例,我将这样做:

((0 to 3) :\ List[Int]())(_ :: _)

在我这样做之前:

(for (x <- 0 to 3) yield x).toList

注意:我在这里使用“foldRight(:\)”而不是“foldLeft/:)”,因为使用的顺序是“u”。对于不引发stackOverflowException的版本,请使用“foldLeft”。

elm 10 年前

使用 List.tabulate ,像这样,

List.tabulate(3)( x => 2*x )
res: List(0, 2, 4)

List.tabulate(3)( _ => Math.random )
res: List(0.935455779102479, 0.6004888906328091, 0.3425278797788426)

List.tabulate(3)( _ => (Math.random*10).toInt )
res: List(8, 0, 7)

André Laszlo 9 年前

注意:这个答案是为旧版本的scala编写的。

从scala 2.8开始,scala集合类将被重新设计,因此准备很快改变创建列表的方式。

创建列表的前向兼容方式是什么?我不知道,因为我还没有读过2.8文档。

A PDF document describing the proposed changes of the collection classes

Yuli Reiri 11 年前

作为一个新的scala开发人员,我用上面建议的方法编写了小测试来检查列表的创建时间。似乎(对于(p<-(0到x))产生p)列出了最快的方法。

import java.util.Date
object Listbm {

  final val listSize = 1048576
  final val iterationCounts = 5
  def getCurrentTime: BigInt = (new Date) getTime

  def createList[T] ( f : Int => T )( size : Int ): T = f ( size )

  // returns function time execution
  def experiment[T] ( f : Int => T ) ( iterations: Int ) ( size :Int ) : Int  = {

    val start_time = getCurrentTime
    for ( p <- 0 to iterations )  createList ( f ) ( size )
    return (getCurrentTime - start_time) toInt

  }

  def printResult ( f:  => Int ) : Unit = println ( "execution time " + f  )

  def main( args : Array[String] ) {


    args(0) match {

      case "for" =>  printResult ( experiment ( x => (for ( p <- ( 0 to x ) ) yield p) toList  ) ( iterationCounts ) ( listSize ) )
      case "range"  =>  printResult ( experiment ( x => ( 0 to x ) toList ) ( iterationCounts ) ( listSize ) )
      case "::" => printResult ( experiment ( x => ((0 to x) :\ List[Int]())(_ :: _) ) ( iterationCounts ) ( listSize ) )
      case _ => println ( "please use: for, range or ::\n")
    }
  }
}

Arne 8 年前

只是一个使用collection.breakout的示例

scala> val a : List[Int] = (for( x <- 1 to 10 ) yield x * 3)(collection.breakOut)
a: List[Int] = List(3, 6, 9, 12, 15, 18, 21, 24, 27, 30)

scala> val b : List[Int] = (1 to 10).map(_ * 3)(collection.breakOut)
b: List[Int] = List(3, 6, 9, 12, 15, 18, 21, 24, 27, 30)