0

I have the following code snippets: The code reads the system (Linux) dictionary(en) file and keeps it in memory List.

Code 1 : (With mutable List)

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

  }

Code 2 : (With Immutable List)

var word = List[String]()

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

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

  }

Code 2 : returns almost immediately , But Code 1 : Takes for ever .

Can any one help me out , why is it taking so much time for mutable List? . Should we use Mutable at all or Am I doing something wrong?

Scala version used : 2.10.3

Thanks in Advance for your help.

4

2 に答える 2

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

リストをトラバースwordし、最後に他のリストの項目を追加します。

word ::= s

単語リストの先頭に追加sし、新しいリストを単語変数に割り当てます。

リストの最後に追加することは、項目を前に追加することに比べて常にコストがかかります。

于 2013-11-14T10:48:48.350 に答える
1

最初の例では、リストの末尾に繰り返し追加 (追加) しています。これには、リストの長さのオーダーで時間がかかります。2 番目の例では、リスト (::) の先頭に追加しています。これには一定の時間がかかります。したがって、最初の例の実行時間はファイル内の行数の 2 乗に比例して増加し、2 番目の例の実行時間はファイルの長さに比例して増加します。

Listこれは、 immutableと mutableの両方の基礎となるデータ構造である連結リストの性質によるものLinkedListです。リンクされたリストは、前面ではアクセスが速く、背面ではアクセスが遅くなります。

于 2013-11-14T10:52:02.743 に答える