Bevorzugte Methode zum Erstellen einer Scala-Liste

116

Es gibt verschiedene Möglichkeiten, eine unveränderliche Liste in Scala zu erstellen (siehe Beispielcode unten). Sie können einen veränderlichen ListBuffer verwenden, eine varListe erstellen und ändern, eine rekursive Schwanzmethode verwenden und wahrscheinlich andere, die ich nicht kenne.

Instinktiv verwende ich den ListBuffer, aber ich habe keinen guten Grund dafür. Gibt es eine bevorzugte oder idiomatische Methode zum Erstellen einer Liste oder gibt es Situationen, die für eine Methode gegenüber einer anderen am besten geeignet sind?

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

Antworten:

108

ListBufferist eine veränderbare Liste mit zeitlich konstantem Anhängen und zeitkonstanter Konvertierung in a List.

List ist unveränderlich und hat ein konstantes und ein lineares Anhängen.

Wie Sie Ihre Liste erstellen, hängt von dem Algorithmus ab, für den Sie die Liste verwenden, und von der Reihenfolge, in der Sie die Elemente zum Erstellen der Liste erhalten.

Wenn Sie beispielsweise die Elemente in der entgegengesetzten Reihenfolge erhalten, in der sie verwendet werden sollen, können Sie einfach a verwenden Listund voranstellen. Ob Sie dies mit einer rekursiven Funktion foldLeftoder mit etwas anderem tun , ist nicht wirklich relevant.

Wenn Sie die Elemente in derselben Reihenfolge erhalten, in der Sie sie verwenden, ListBufferist a höchstwahrscheinlich die bevorzugte Wahl, wenn die Leistung kritisch ist.

Wenn Sie sich jedoch nicht auf einem kritischen Pfad befinden und die Eingabe niedrig genug ist, können Sie reversedie Liste immer später oder nur foldRightoder reversedie Eingabe mit linearer Zeit verwenden.

Was Sie NICHT tun, ist ein zu verwenden Listund daran anzuhängen. Dies führt zu einer viel schlechteren Leistung als nur das Voranstellen und Umkehren am Ende.

Daniel C. Sobral
quelle
What you DON'T do is use a List and append to itLiegt das daran, dass eine neue Liste erstellt wird? Während bei Verwendung einer Voranstelloperation keine neue Liste erstellt wird?
Kevin Meredith
2
@ KevinMeredith Ja. Anhängen ist O (n), Voranstellen ist O (1).
Daniel C. Sobral
@pgoggijr Das ist nicht wahr. Erstens gibt es nirgendwo eine "Veränderung", weil sie unveränderlich ist. Eine Durchquerung ist erforderlich, da alle Elemente kopiert werden müssen, damit eine Kopie des letzten Elements erstellt werden kann, die auf ein neues Element anstatt auf zeigt Nil. Zweitens gibt es beim Voranstellen keinerlei Kopie: Es wird ein Element erstellt, das auf die vorhandene Liste verweist, und das war's.
Daniel C. Sobral
65

Und für einfache Fälle:

val list = List(1,2,3) 

:) :)

Tomasz Nurkiewicz
quelle
10
Vergessen Sie nicht den Nachteile Operator! 1 :: 2 :: 3 :: Nil
André Laszlo
22

Ähm ... diese scheinen mir zu komplex. Darf ich vorschlagen

def listTestD = (0 to 3).toList

oder

def listTestE = for (i <- (0 to 3).toList) yield i
Alexander Azarov
quelle
Vielen Dank für die Antwort, aber die Frage ist, was Sie im nicht trivialen Fall tun. Ich habe einen Kommentar in den Code eingefügt, der erklärt, dass sie alle 0 bis 3 toList entsprechen.
Agilefall
Ups, tut mir leid! Ehrlich gesagt benutze ich ListBuffer nie.
Alexander Azarov
5

Sie möchten sich generell auf die Unveränderlichkeit in Scala konzentrieren, indem Sie alle Vars entfernen. Die Lesbarkeit ist für Ihren Mitmenschen immer noch wichtig.

Versuchen:

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)

In den meisten Fällen müssen Sie wahrscheinlich nicht einmal in eine Liste konvertieren :)

Die indizierte Sequenz enthält alles, was Sie benötigen:

Das heißt, Sie können jetzt an diesem IndexedSeq arbeiten:

scala> list.foldLeft(0)(_+_)
res0: Int = 55
JasonG
quelle
NB Vectorist jetzt auch die Standardimplementierung Seq.
Connor Doyle
2

Ich bevorzuge immer List und verwende "Fold / Reduce" vor "zum Verständnis". "Zum Verständnis" wird jedoch bevorzugt, wenn verschachtelte "Falten" erforderlich sind. Rekursion ist der letzte Ausweg, wenn ich die Aufgabe mit "Fold / Reduce / For" nicht ausführen kann.

Für Ihr Beispiel werde ich Folgendes tun:

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

bevor ich es tue:

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

Hinweis: Ich verwende hier "foldRight (: \)" anstelle von "foldLeft (/ :)" wegen der Reihenfolge von "_". Verwenden Sie für eine Version, die keine StackOverflowException auslöst, stattdessen "foldLeft".

Walter Chang
quelle
18
Ich bin absolut anderer Meinung; Ihre bevorzugte Form sieht einfach wie Linienrauschen aus.
Matt R
14
Werde ich Ich habe Haskell 1999 zum ersten Mal gelernt und beschäftige mich seit einigen Jahren mit Scala. Ich denke, Falten sind großartig, aber wenn das Anwenden einer Falte in einer bestimmten Situation das Schreiben einer kryptischen Folge von Interpunktionssymbolen erfordert, würde ich einen anderen Ansatz in Betracht ziehen.
Matt R
11
@ Matt R: Ich stimme zu. Es gibt so etwas wie Übertreiben, und dies ist einer von ihnen.
Ryeguy
8
@WalterChang Ich mag das Aussehen all dieser Emoticons. Moment mal, ist das Code? : P
David J.
4
Ist es fair, ((0 to 3) :\ List[Int]())(_ :: _)Emoticode zu nennen ?
David J.
2

Verwenden Sie List.tabulatewie folgt:

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)
Ulme
quelle
2

Hinweis: Diese Antwort wurde für eine alte Version von Scala geschrieben.

Die Scala-Sammlungsklassen werden ab Scala 2.8 neu gestaltet. Seien Sie also bereit, die Art und Weise, wie Sie Listen erstellen, sehr bald zu ändern.

Was ist die vorwärtskompatible Methode zum Erstellen einer Liste? Ich habe keine Ahnung, da ich die 2.8-Dokumente noch nicht gelesen habe.

Ein PDF-Dokument, das die vorgeschlagenen Änderungen der Sammlungsklassen beschreibt

André Laszlo
quelle
2
Die meisten Änderungen betreffen die Art und Weise, wie Dinge intern implementiert werden, und fortgeschrittene Dinge wie Projektionen. Wie Sie eine Liste erstellen, ist davon nicht betroffen.
Marcus Downing
Ok, das ist gut zu wissen. Sie sind auch betroffen, wenn Sie eine Klasse im Paket collection.jcl verwenden.
André Laszlo
1

Als neuer Scala-Entwickler habe ich einen kleinen Test geschrieben, um die Erstellungszeit der Liste mit den oben vorgeschlagenen Methoden zu überprüfen. Es sieht so aus (für (p <- (0 bis x)) ergibt p), um den schnellsten Ansatz aufzulisten.

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")
    }
  }
}
Yuli Reiri
quelle
0

Nur ein Beispiel, das collection.breakOut verwendet

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)
Arne
quelle
0

Verwenden Sie Folgendes, um eine Liste mit Zeichenfolgen zu erstellen:

val l = List("is", "am", "are", "if")
KayV
quelle
1
Wenn Sie eine so alte Frage (10 Jahre) und mit so vielen vorhandenen Antworten (9) beantworten, empfiehlt es sich zu erklären, warum sich Ihre Antwort von allen anderen unterscheidet. Es sieht so aus, als hätten Sie die Frage nicht verstanden.
Jwvh