1. ホーム
  2. scala

[解決済み] Scalaのリストを作成するための好ましい方法

2022-09-02 15:57:11

質問

Scalaでイミュータブルリストを構築する方法はいくつかあります(以下の工夫されたサンプルコードを参照)。ミュータブルなListBufferを使う方法と、リスト内で var リストを作成し、それを変更する。 末尾再帰的 メソッドを使うなど、おそらく私が知らない他の方法があります。

本能的に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)
}

どのように解決するのですか?

ListBuffer はミュータブルリストであり、一定時間ごとに追加を行い、一定時間ごとに List .

List は不変であり、一定時間のプリペンドと線形時間のアペンドを持ちます。

リストをどのように構築するかは、リストを使用するアルゴリズムと、リストを作成するために要素を取得する順序に依存します。

例えば、要素を取得する順番が使用するときと逆であれば、単に List と言ってプリペンドを行う。末尾再帰関数でそうするかどうか。 foldLeft などで行うかどうかは、あまり関係ありません。

要素を使う順番と同じように取得するのであれば ListBuffer は、パフォーマンスが重要である場合、最も望ましい選択です。

しかし、クリティカルパスでなく、入力が十分に少ない場合は、常に reverse を使用するか、あるいは単に foldRight または reverse という入力があり、これは線形時間です。

あなたが DON'T を使用することです。 List を使い、それに追加することです。これは、単に前置して最後に反転させるよりもはるかに悪いパフォーマンスを与えるでしょう。