Complessità dello spazio ausiliario di mappa contro mappa!

Naviga le tue risposte
2

Sono curioso della differenza di complessità spaziale tra map e map! in ruby.

Se ho i metodi: 

def mult_by_two(arr)
  arr.map {|i| i * 2 }
end

def mult_by_two!(arr)
  arr.map! {|i| i * 2 }
end

Sebbene non esista un'assegnazione esplicita nel primo metodo, raccoglie implicitamente il risultato di map da qualche parte e non funziona sul posto come il secondo metodo.

Sarebbe corretto dire che il primo ha O (n) complessità dello spazio ausiliario mentre il secondo è O (1)? Come dovrei rappresentarli quando osservo la complessità dello spazio ausiliario di un metodo?

    
posta jstim 09.02.2014 - 09:57
fonte

2 risposte

2

La risposta è nascosta nell'origine della pagina Ruby-doc: Core Array

Se si va a Ruby-doc: Core Array # map o Ruby-doc: Core Array # map! e mouse sopra il blocco, vedranno

Facendoclicsul"clic per alternare la sorgente", forniamo il codice sorgente C che implementa il metodo nell'interprete.

Per map il codice è: 

collect = rb_ary_new2(RARRAY_LEN(ary));
for (i = 0; i < RARRAY_LEN(ary); i++) {
    rb_ary_push(collect, rb_yield(RARRAY_AREF(ary, i)));
}

Per map! il codice è: 

rb_ary_modify(ary);
for (i = 0; i < RARRAY_LEN(ary); i++) {
    rb_ary_store(ary, i, rb_yield(RARRAY_AREF(ary, i)));
}

Si può chiaramente vedere che map alloca un nuovo array della lunghezza dell'array originale e spinge i valori usati in questo array mentre map! memorizza il valore nell'array iniziale.

Quindi, sei corretto - map usa O (n) spazio ausiliario mentre map! usa O (1) (nessuna).

    
risposta data 09.02.2014 - 15:16
fonte
0

array.map: "Invoca il blocco dato una volta per ogni elemento di sé. Crea un nuovo array contenente i valori restituiti dal blocco.".

array.map !: "Invoca il blocco indicato una volta per ciascun elemento di sé, sostituendo l'elemento con il valore restituito dal blocco.".

Il primo assegna un nuovo array della stessa dimensione, il secondo no. La "complessità spaziale" di entrambi è esattamente la stessa: O (1). L'uso dello spazio ausiliario della mappa è O (N), per la mappa! è O (1).

La ragione principale per usare la mappa! è quello di evitare l'allocazione extra che alla fine deve essere raccolta dalla spazzatura.

    
risposta data 09.02.2014 - 15:23
fonte

Leggi altre domande sui tag

Costanti e proprietà pubbliche per la configurazione Le sottoclassi hanno solo metodi senza variabili