Qual è la performance Big O delle mappe in golang?

Question

"Map types" section of the go language specification descrive l'interfaccia e l'utilizzo generale dei tipi di mappe e lo "Go maps in action" post on The Go Blog indica casualmente tabelle hash e "ricerche rapide, aggiunte ed eliminazioni".

Il current runtime/hashmap.go source code descrive la sua implementazione come una tabella hash (che sono tipicamente ammortizzati O(1)); tuttavia, non vedo alcuna garanzia delle caratteristiche delle prestazioni (come le prestazioni di Big O) nelle specifiche della lingua o in altri materiali.

Condivide la lingua andare a fare qualsiasi prestazioni garanzie (ad esempio costante di tempo di inserimento/di ricerca/cancellazione?) Per i tipi di carta o solo interfaccia garanzie? (Confronta con il linguaggio Java in cui interfacce e implementazioni sono chiaramente separati.)

Answer 1

Il riferimento alla lingua non offre garanzie esplicite sull'esecuzione delle mappe. Esiste un'aspettativa implicita che le mappe funzionino come ci si aspetta dalle hash-tabelle. Non vedo come una garanzia sulle prestazioni eviterebbe di essere o specificatamente errata o imprecisa.

La complessità del Big-O è un modo inadeguato per descrivere i tempi di esecuzione delle mappe: praticamente l'ora effettiva è rilevante e la complessità no. Teoricamente, le mappe con chiavi da domini finiti (come gli ints) sono banalmente O (1) nello spazio e nel tempo, e le mappe con chiavi con domini infiniti (come le stringhe) richiedono l'hashing e le specifiche del test di uguaglianza da includere nel costo , che rende in media gli inserti e le ricerche migliori maiuscole (N log N) (poiché le chiavi devono essere almeno O (log N) di dimensioni medie per costruire una tabella hash con N voci. A meno che non si ottengano questi dettagli direttamente la specifica sarà imprecisa e il vantaggio di ottenerla non è chiaramente la pena.

Per fornire garanzie sull'effettivo tempo di esecuzione piuttosto che sulla complessità, sarebbe anche difficile: c'è una vasta gamma di macchine target, così come i problemi di confusione della memorizzazione nella cache e della raccolta dei rifiuti.

Answer 2

Da quello che posso vedere, il Go Programming Language Specification non fa alcuna garanzia di rendimento per i tipi di carta. Hash tables in generale sono O (1) per l'inserimento, la ricerca e l'eliminazione dei dati; possiamo supporre che questo sia vero anche per le mappe di Go.

Se si è preoccupati delle prestazioni della mappa, è sempre possibile il codice benchmark su carichi diversi e decidere se utilizzare le mappe di Go o qualche altra struttura di dati.

Answer 3

Per essere precisi, le prestazioni delle tabelle hash sono O (1 + n/k) per risolvere le collisioni, dove n/k si riferiscono al fattore di carico. Vai specifica dichiarare le mappe come non restrittive nella quantità delle chiavi. Quindi hanno bisogno di un ridimensionamento dinamico con rilasci in parte per mantenere il fattore di carico durante la crescita o la contrazione. Ciò significa che vicino a O (1) può essere facilmente raggiunto per la ricerca in mappe di dimensioni costanti, ma non può nemmeno essere teoricamente garantito per l'inserimento o la cancellazione massiccia. Tali operazioni richiedono la riallocazione, il parziale rimodellamento e le possibili raccolte di dati inutili per mantenere il fattore di carico e l'utilizzo ragionevole della memoria.