2013-03-19 14 views
17

Si consideri il semplice problema di utilizzare una mappa mutabile per tenere traccia di eventi/conta, cioè con:accesso/inizializzare e aggiornare i valori in una mappa mutabile

val counts = collection.mutable.Map[SomeKeyType, Int]() 

mio approccio attuale per incrementare un conteggio è:

counts(key) = counts.getOrElse(key, 0) + 1 
// or equivalently 
counts.update(key, counts.getOrElse(key, 0) + 1) 

questo si sente in qualche modo un po 'goffo, perché devo specificare la chiave due volte. In termini di prestazioni, mi aspetto anche che lo key debba essere posizionato due volte nella mappa, cosa che vorrei evitare. È interessante notare che questo problema di accesso e di aggiornamento non si verificherebbe se Int fornisse qualche meccanismo per modificarsi. Il passaggio da Int a una classe Counter che fornisce una funzione increment avrebbe per esempio permettere:

// not possible with Int 
counts.getOrElseUpdate(key, 0) += 1 
// but with a modifiable counter 
counts.getOrElseUpdate(key, new Counter).increment 

In qualche modo io sono sempre in attesa di avere le seguenti funzionalità con una mappa mutabile (in qualche modo simile a transform ma senza restituire una nuova collezione e su un tasto specifico con un valore di default):

// fictitious use 
counts.updateOrElse(key, 0, _ + 1) 
// or alternatively 
counts.getOrElseUpdate(key, 0).modify(_ + 1) 

Tuttavia, per quanto posso vedere, tale funzionalità non esiste. Non avrebbe senso, in generale (prestazioni e sintassi saggia) avere una tale possibilità di modifica sul posto da f: A => A? Probabilmente mi manca qualcosa qui ... Immagino ci debba essere una soluzione migliore a questo problema rendendo inutile tale funzionalità?

Aggiornamento:

avrei chiarito che io sappia withDefaultValue ma il problema rimane lo stesso: l'esecuzione di due ricerche è ancora due volte più lento di uno, non importa se si tratta di un O (1) operazione o meno. Francamente, in molte situazioni sarei più che felice di ottenere un'accelerazione del fattore 2. E ovviamente la costruzione della chiusura di modifica può spesso essere spostata al di fuori del ciclo, quindi questo non è un grosso problema rispetto alla gestione di un operazione inutilmente due volte.

+2

ricerca della chiave in uno standard Mappa di solito dovrebbe essere O (1), quindi non c'è una grande pena nel guardare in su due volte - probabilmente meno di quanto pagato dal costruendo la chiusura per la funzione di passare in 'updateOrElse'. – Impredicative

+1

@Impredicative: questo è un buon punto in questo esempio. Ma la funzionalità nel tratto stesso non fa alcuna ipotesi al riguardo. Ad esempio, 'Map' è anche implementato da' TreeMap' e 'ListMap' che sono rispettivamente O (log N) e O (N). Quindi, senza fare un'ipotesi di O (1), la modifica sul posto sarebbe comunque auspicabile in generale. – bluenote10

+1

Sono con te, bluenote10 - Ero sicuro che ci sarebbe stato qualcosa come 'map.update (chiave, initValue) {}' perché ha prestazioni sostanzialmente migliori * e * è più pulito. Se le prestazioni non fossero importanti, probabilmente non utilizzeremmo una mappa mutabile in primo luogo. E come menzionato in un altro commento, '(_ + 1)' non * non * una chiusura, poiché non si chiude su nessuna variabile libera - non c'è nulla da costruire. – AmigoNico

risposta

20

è possibile creare la mappa con un valore di default, che permetterebbe di effettuare le seguenti operazioni:

scala> val m = collection.mutable.Map[String, Int]().withDefaultValue(0) 
m: scala.collection.mutable.Map[String,Int] = Map() 

scala> m.update("a", m("a") + 1) 

scala> m 
res6: scala.collection.mutable.Map[String,Int] = Map(a -> 1) 

Come accennato impredicativa, mappa le ricerche sono veloci, quindi non mi preoccuperei circa 2 ricerche.

Aggiornamento:

Come Debilski ha sottolineato che si può fare questo ancora più semplicemente effettuando le seguenti operazioni:

scala> val m = collection.mutable.Map[String, Int]().withDefaultValue(0) 
scala> m("a") += 1 
scala> m 
res6: scala.collection.mutable.Map[String,Int] = Map(a -> 1) 
+3

Nota che 'm (" a ") + = 1' è zucchero (^) per' m ("a") = m ("a") + 1' è zucchero per 'm.update (" a ", m ("a") + 1) '. (^ o meglio zucchero per convenzione, come il metodo '+ =' possibilmente implementato direttamente su 'mutable.Map') – Debilski

+0

Grazie! Ho aggiornato la mia risposta per riflettere questo! – coltfred

+0

Ero a conoscenza dell'approccio al valore predefinito ma sfortunatamente ho dimenticato di menzionarlo nella mia domanda. Non l'ho considerato qui poiché la mia preoccupazione reale (la doppia ricerca) non è risolta con questo approccio. Grazie comunque! – bluenote10

1

volevo pigro-inizializzare la mia mappa mutevole invece di fare una piega (per l'efficienza della memoria). Il metodo collection.mutable.Map.getOrElseUpdate() è adatto ai miei scopi. La mia mappa conteneva un oggetto mutabile per sommare i valori (di nuovo, per l'efficienza).

 val accum = accums.getOrElseUpdate(key, new Accum) 
     accum.add(elem.getHours, elem.getCount) 

collection.mutable.Map.withDefaultValue() non mantiene il valore predefinito per una chiave richiesta successiva.

+0

Si noti che la domanda riguardava soprattutto il caso in cui 'getOrElseUpdate' non è applicabile (scalari), che è anche l'esempio che ho dato nella domanda. Se hai oggetti mutabili, questa è la scelta più ovvia. – bluenote10

Problemi correlati