Perché iterare su una mappa è molto più lento di iterare su una porzione di Golang?

Question

Stavo implementando una matrice sparsa utilizzando una mappa in Golang e ho notato che il mio codice ha iniziato a richiedere molto più tempo per completare dopo questo cambiamento, dopo aver eliminato altre possibili cause, sembra che il colpevole sia l'iterazione sulla mappa stessa. Go Playground link (non funziona per qualche motivo).

package main 

import (
    "fmt" 
    "time" 
    "math" 
) 

func main() { 
    z := 50000000 
    a := make(map[int]int, z) 
    b := make([]int, z) 

    for i := 0; i < z; i++ { 
     a[i] = i 
     b[i] = i 
    } 

    t0 := time.Now() 
    for key, value := range a { 
     if key != value { // never happens 
      fmt.Println("a", key, value) 
     } 
    } 
    d0 := time.Now().Sub(t0) 

    t1 := time.Now() 
    for key, value := range b { 
     if key != value { // never happens 
      fmt.Println("b", key, value) 
     } 
    } 
    d1 := time.Now().Sub(t1) 

    fmt.Println(
     "a:", d0, 
     "b:", d1, 
     "diff:", math.Max(float64(d0), float64(d1))/math.Min(float64(d0), float64(d1)), 
    ) 
} 

iterazione di oggetti 50M restituisce i seguenti orari:

alix@local:~/Go/src$ go version 
go version go1.3.3 linux/amd64 
alix@local:~/Go/src$ go run b.go 
a: 1.195424429s b: 68.588488ms diff: 17.777154632611037 

mi chiedo, perché è l'iterazione di una mappa quasi 20 volte più lento rispetto ad una fetta?

Answer 1

Questo si riduce alla rappresentazione in memoria. Quanto sei familiare con la rappresentazione di diverse strutture dati e il concetto di complessità algoritmica? L'iterazione su una matrice o una sezione è semplice. I valori sono contigui in memoria. Tuttavia, l'iterazione su una mappa richiede di attraversare lo spazio chiave e di effettuare ricerche nella struttura della tabella hash.

La capacità dinamica delle mappe di inserire chiavi di qualsiasi valore senza utilizzare tonnellate di spazio per allocare un array sparse e il fatto che le ricerche possono essere eseguite in modo efficiente nello spazio chiave pur non essendo veloci come un array, Ecco perché le tabelle hash vengono talvolta preferite su un array, sebbene gli array (e le slice) abbiano un tempo di ricerca "costante" (O(1)) "costante" dato un indice.

Tutto si riduce alla necessità di disporre delle funzionalità di questa o quella struttura dati e se si è disposti ad affrontare gli effetti collaterali oi trucchi coinvolti.

Answer 2

Sembra ragionevole inserire il mio commento come risposta. Le strutture sottostanti a cui si sta confrontando il rendimento di iterazione sono una tabella hash e un array (https://en.wikipedia.org/wiki/Hash_table rispetto a https://en.wikipedia.org/wiki/Array_data_structure). L'astrazione dell'intervallo è in realtà (la speculazione, non riesce a trovare il codice) iterando tutti i tasti, accedendo a ciascun valore e assegnando i due a k,v :=. Se non si ha familiarità con l'accesso nell'array, è un tempo costante perché basta aggiungere sizeof (tipo) * i al puntatore iniziale per ottenere l'oggetto. Non so cosa siano gli interni della mappa in golang, ma so abbastanza per sapere che è la rappresentazione della memoria e quindi l'accesso non è niente di così efficiente.

La dichiarazione delle specifiche sull'argomento non è molto; http://golang.org/ref/spec#For_statements

Se trovo il tempo di cercare l'implementazione dell'intervallo per mappa e slice/array, inserirò alcuni dettagli tecnici.