Qual è la differenza tra Seq e IndexedSeq/LinearSeq in Scala?

Question

In Scala Collection documentation, c'è qualche indizio a questa domanda:

Trait Seq ha due subtraits LinearSeq e IndexedSeq. Queste non aggiungono nuove operazioni, ma ognuna offre caratteristiche di performance diverse: una sequenza lineare ha efficienti operazioni head e tail, mentre una sequenza indicizzata ha efficienti operazioni di aggiornamento, lunghezza e (se modificabile).

Ma questo non mi affronta quando utilizzare IndexedSeq invece di Seq? Ho bisogno di qualche esempio reale di IndexedSeq o LinearSeq dove queste raccolte funzionano meglio di Seq.

Answer 1

Seq è il super-tratto, quindi è più generico, ha le caratteristiche comuni a tutte le sequenze, sia lineare che indicizzato.

Se vi state chiedendo che tipo di sequenza viene creato con il metodo Seq.apply nell'oggetto compagna di Seq, possiamo avere uno sguardo alla realizzazione.

Tenete presente che se si utilizza Seq.apply, si sta implicando che basta un Seq e che il codice non si preoccupa se è lineare o indicizzate

Il tl; dr risposta è allora: si utilizza LinearSeq o IndexedSeq quando è necessario avere un certo caratteristiche di prestazioni, si utilizza il più generale Seq quando non vi interessa circa la differenza

Questo è l'oggetto associato di Seq:

object Seq extends SeqFactory[Seq] { 
    implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] 

    def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A] 
} 

Il metodo newBuilder[A] è quello che viene utilizzato per costruire il Seq, come si può verificare nel metodo Seq.apply (definito sul tratto GenericCompanion):

def apply[A](elems: A*): CC[A] = { 
    if (elems.isEmpty) empty[A] 
    else { 
    val b = newBuilder[A] 
    b ++= elems 
    b.result() 
    } 
} 

Ora la domanda è: che cosa fa un immutable.Seq.newBuilder[A] build? Andiamo a vedere, questa volta sull'oggetto immutable.Seq compagna:

object Seq extends SeqFactory[Seq] { 
// stuff 
    def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer 
} 

Si costruisce un mutabile ListBuffer! Perché? Questo perché un mutable.ListBuffer è anche un Builder[A, Seq[A]], ovvero una classe che viene utilizzata dalla raccolta di raccolte per creare nuove raccolte.

La collezione di uscita effettiva viene da questa linea (come potete vedere sopra):

b.result() 

Allora, qual è il tipo di ritorno del ListBuffer.result()? Andiamo a vedere in ListBuffer:

// Implementation of abstract method in Builder 
def result: List[A] = toList 

ecco qui: è una lista.

Seq(1,2,3) restituisce un List[Int] sotto il cofano, ma il punto qui è che se si sta utilizzando Seq(), non è necessario sapere che tipo di raccolta si ha perché si sta implicando che il più astratto l'interfaccia è sufficiente per le vostre esigenze

Answer 2

Seq è semplicemente super-caratteristica di IndexedSeq e LinearSeq. Seq è un elenco ordinato, a differenza di Set, che è univoco & non ordinato di solito, e al contrario di Mappa, che è una coppia di valori chiave.
Ora viene IndexedSeq vs LinearSeq.
Sottoclassi IndexedSeq, ad esempio Vector, Range, String, sono tutti accessi basati su indice rapido e, in genere, aggiornamenti rapidi. Questo è possibile perché usano strutture di dati adatte per questo come array internamente (come in String) o un albero (in realtà un albero 32 fan out usato da Vector .. per ulteriori dettagli vedi this) o Range, che è solo tre numeri. inizio, fine, passaggio .. da cui i calcoli dell'indice sono diretti.
Al contrario, LinearSeq è basato su indice lento e accesso e lento negli aggiornamenti. Solitamente perché hanno un tipo di struttura di elenco collegato. Prepend è veloce per tutti, ad esempio Queue, Stack, List .. ma append è notoriamente lento in quanto deve andare al limite della struttura interna della lista collegata .. tranne per la coda che usa un trucco con i propri problemi. Il trucco è descritto here.
Quindi, in generale, IndexedSeq sono quelle strutture di dati con accesso e aggiornamento basati su indice rapido e LinearSeq sono quelle strutture di dati che hanno subito un precarico.