0

我有以下代码片段： 代码读取系统（Linux）字典（en）文件并将其保存在内存列表中。

代码 1：（使用可变列表）

  val word = scala.collection.mutable.LinkedList[String]("init");

  for(line <- Source.fromFile("/usr/share/dict/words").getLines()){
    val s : String = line.trim()

    if( // some checks
    ){
      word append scala.collection.mutable.LinkedList[String](s) 
    }

  }

代码 2：（使用不可变列表）

var word = List[String]()

  for(line <- Source.fromFile("/usr/share/dict/words").getLines()){
    val s : String = line.trim()

    if( // some checks
    ){
      word ::= s
    }

  }

代码 2：几乎立即返回，但代码 1：永远需要。

任何人都可以帮助我，为什么可变列表需要这么多时间？. 我们应该使用 Mutable 还是我做错了什么？

使用的 Scala 版本：2.10.3

在此先感谢您的帮助。

4

2 回答 2

1 
word append scala.collection.mutable.LinkedList[String](s)

遍历word列表，然后在最后附加另一个列表中的项目。

word ::= s

附加s在单词列表的前面并将新列表分配给单词变量。

与将项目添加到前面相比，追加到列表末尾总是昂贵的。

于 2013-11-14T10:48:48.350 回答
1

在第一个示例中，您将重复添加到列表的末尾（追加）。这需要列表长度的时间。在第二个示例中，您将添加到列表的开头 (::)。这需要恒定的时间。所以第一个例子的执行时间随着文件中行数的平方增加，第二个例子的执行时间随着文件的长度线性增加。

这是由于链表的性质，链表是 immutableList和 mutable的基础数据结构LinkedList。链表在前面访问快，在后面访问慢。

于 2013-11-14T10:52:02.743 回答