Perché l'aggiunta ad una lista in Scala ha una complessità temporale (n)?

11

Ho appena letto che il tempo di esecuzione dell'operazione append per List (: +) cresce linearmente con la dimensione del List .

L'aggiunta a List sembra un'operazione abbastanza comune. Perché il modo idiomatico per fare ciò è anteporre i componenti e invertire la lista? Non può anche essere un errore di progettazione in quanto l'implementazione potrebbe essere modificata in qualsiasi momento.

Dal mio punto di vista, sia in fase di preparazione che di aggiunta dovrebbe essere O (1).

C'è qualche motivo legittimo per questo?

    
posta DPM 06.11.2013 - 19:07
fonte

1 risposta

22

Espanderò un po 'il mio commento. La struttura di dati List[T] , da scala.collection.immutable è ottimizzata per funzionare come funziona un elenco immutabile in un linguaggio di programmazione più puramente funzionale. Ha antepone molto velocemente e si presume che lavorerai in testa per quasi tutti i tuoi accessi.

Gli elenchi immutabili hanno tempi di antefatto molto rapidi a causa del fatto che modellano le loro liste collegate come una serie di "celle di controllo". La cella definisce un singolo valore e un puntatore alla cella successiva (stile classico con elenchi singoli):

Cell [Value| -> Nil]

Quando ti anteponi a un elenco, stai solo creando una singola nuova cella, con il resto dell'elenco esistente puntato a:

Cell [NewValue| -> [Cell[Value| -> Nil]]

Poiché l'elenco è immutabile, sei sicuro di farlo senza alcuna copia effettiva . Non c'è pericolo che il vecchio elenco cambi e che tutti i valori del nuovo elenco non siano più validi. Tuttavia, perdi la possibilità di avere un puntatore mutabile al fine del tuo elenco come compromesso.

Questo si presta molto bene a lavorare in modo ricorsivo sugli elenchi. Supponiamo che tu abbia definito la tua versione di filter :

def deleteIf[T](list : List[T])(f : T => Boolean): List[T] = list match {
  case Nil => Nil
  case (x::xs) => f(x) match {
    case true => deleteIf(xs)(f)
    case false => x :: deleteIf(xs)(f)
  }
}

Questa è una funzione ricorsiva che funziona esclusivamente dal capo della lista e sfrutta la corrispondenza dei pattern tramite :: extractor. Questo è qualcosa che vedi in molte lingue come Haskell.

Se vuoi davvero degli allegati veloci, Scala offre molte strutture dati mutevoli e immutabili tra cui scegliere. Sul lato mutabile, potresti esaminare ListBuffer . In alternativa, Vector da scala.collection.immutable ha un tempo di aggiunta veloce.

    
risposta data 06.11.2013 - 19:25
fonte

Leggi altre domande sui tag