Sortuj wartości mapy Go według kluczy

Podczas iteracji po zwróconej mapie w kodzie, zwróconej przez funkcję topic, klucze nie pojawiają się w kolejności.

Jak mogę sprawić, aby klucze były uporządkowane / posortowane na mapie, aby klucze były w porządku, a wartości odpowiadały?

Oto kod .

Go blog: Mapy w akcji ma doskonałe wyjaśnienie.

Podczas iteracji po mapie z pętlą zakresu kolejność iteracji nie jest określona i nie ma gwarancji, że będzie taka sama w kolejnych iteracjach. Od czasu Go 1 środowisko wykonawcze losuje kolejność iteracji mapy, ponieważ programiści polegali na stabilnej kolejności iteracji poprzedniej implementacji. Jeśli potrzebujesz stabilnej kolejności iteracji, musisz zachować oddzielną strukturę danych, która określa tę kolejność.

Oto moja zmodyfikowana wersja przykładowego kodu: http://play.golang.org/p/dvqcGPYy3-

package main

import (
    "fmt"
    "sort"
)

func main() {
    // To create a map as input
    m := make(map[int]string)
    m[1] = "a"
    m[2] = "c"
    m[0] = "b"

    // To store the keys in slice in sorted order
    keys := make([]int, len(m))
    i := 0
    for k := range m {
        keys[i] = k
        i++
    }
    sort.Ints(keys)

    // To perform the opertion you want
    for _, k := range keys {
        fmt.Println("Key:", k, "Value:", m[k])
    }
}

Wynik:

Key: 0 Value: b
Key: 1 Value: a
Key: 2 Value: c

Zgodnie ze specyfikacją Go , kolejność iteracji na mapie jest nieokreślona i może różnić się między uruchomieniami programu. W praktyce jest nie tylko niezdefiniowany, ale w rzeczywistości jest celowo losowy. Dzieje się tak, ponieważ kiedyś był przewidywalny, a programiści języka Go nie chcieli, aby ludzie polegali na nieokreślonym zachowaniu, więc celowo losowali to, aby poleganie na tym zachowaniu było niemożliwe.

W takim razie musisz pociągnąć klucze do kawałka, posortować je, a następnie przesunąć po kawałku w następujący sposób:

var m map[keyType]valueType
keys := sliceOfKeys(m) // you'll have to implement this
for _, k := range keys {
    v := m[k]
    // k is the key and v is the value; do your computation here
}

Wszystkie odpowiedzi tutaj zawierają teraz stare zachowanie map. W Go 1.12+ możesz po prostu wydrukować wartość mapy, a zostanie ona automatycznie posortowana według klucza. Zostało to dodane, ponieważ umożliwia łatwe testowanie wartości map.

func main() {
    m := map[int]int{3: 5, 2: 4, 1: 3}
    fmt.Println(m)

    // In Go 1.12+
    // Output: map[1:3 2:4 3:5]

    // Before Go 1.12 (the order was undefined)
    // map[3:5 2:4 1:3]
}

Mapy są teraz drukowane w kolejności sortowania według kluczy, aby ułatwić testowanie. Zasady zamawiania to:

• W stosownych przypadkach zero porównuje niskie
• int, float i stringi są uporządkowane według <
• NaN porównuje mniej niż zmiennoprzecinkowe bez NaN
• bool porównuje fałsz przed prawdą
• Złożone porównuje rzeczywiste, a następnie urojone
• Wskaźniki są porównywane według adresu komputera
• Wartości kanałów są porównywane według adresu maszyny
• Struktury po kolei porównują poszczególne pola
• Tablice porównują po kolei każdy element
• Wartości interfejsów są porównywane najpierw przez odbicie.Type opisujące konkretny typ, a następnie przez konkretną wartość, zgodnie z opisem w poprzednich regułach.

Podczas drukowania map nierefleksyjne wartości kluczowe, takie jak NaN, były wcześniej wyświetlane jako <nil>. Od tej wersji drukowane są prawidłowe wartości.

Przeczytaj więcej tutaj .

W odpowiedzi na James Craig Burley za odpowiedź . Aby stworzyć czysty i nadający się do ponownego wykorzystania projekt, można wybrać podejście bardziej zorientowane obiektowo. W ten sposób metody można bezpiecznie powiązać z typami określonej mapy. Wydaje mi się, że takie podejście jest czystsze i zorganizowane.

Przykład:

package main

import (
    "fmt"
    "sort"
)

type myIntMap map[int]string

func (m myIntMap) sort() (index []int) {
    for k, _ := range m {
        index = append(index, k)
    }
    sort.Ints(index)
    return
}

func main() {
    m := myIntMap{
        1:  "one",
        11: "eleven",
        3:  "three",
    }
    for _, k := range m.sort() {
        fmt.Println(m[k])
    }
}

Przykład rozszerzonego placu zabaw z wieloma typami map.

Ważna uwaga

We wszystkich przypadkach mapa i posortowany wycinek są oddzielane od momentu zakończenia forpętli nad mapą range. Oznacza to, że jeśli mapa zostanie zmodyfikowana po logice sortowania, ale zanim jej użyjesz, możesz wpaść w kłopoty. (Nie jest bezpieczny dla wątków / przejść). Jeśli nastąpi zmiana równoległego dostępu do zapisu Map, będziesz musiał użyć muteksu wokół zapisów i posortowanej forpętli.

mutex.Lock()
for _, k := range m.sort() {
    fmt.Println(m[k])
}
mutex.Unlock()

Jeśli, tak jak ja, okaże się, że potrzebujesz zasadniczo tego samego kodu sortowania w więcej niż jednym miejscu lub po prostu chcesz zachować złożoność kodu, możesz przenieść samo sortowanie do oddzielnej funkcji, do której przekazujesz funkcję, która to robi rzeczywistą pracę, jaką chcesz (która będzie oczywiście inna w każdym miejscu telefonicznym).

Biorąc pod uwagę, mapa z kluczem typu Ki rodzaju wartości V, reprezentowane <K>i <V>poniżej, wspólna funkcja sortowania może wyglądać ten szablon Go-kodu (który Go w wersji 1 nie obsługuje jak jest):

/* Go apparently doesn't support/allow 'interface{}' as the value (or
/* key) of a map such that any arbitrary type can be substituted at
/* run time, so several of these nearly-identical functions might be
/* needed for different key/value type combinations. */
func sortedMap<K><T>(m map[<K>]<V>, f func(k <K>, v <V>)) {
    var keys []<K>
    for k, _ := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)  # or sort.Ints(keys), sort.Sort(...), etc., per <K>
    for _, k := range keys {
        v := m[k]
        f(k, v)
    }
}

Następnie wywołaj go z mapą wejściową i funkcją (przyjmującą (k <K>, v <V>)jako argumenty wejściowe), która jest wywoływana nad elementami mapy w kolejności posortowanych kluczy.

Tak więc wersja kodu w odpowiedzi opublikowanej przez Mingu może wyglądać następująco:

package main

import (
    "fmt"
    "sort"
)

func sortedMapIntString(m map[int]string, f func(k int, v string)) {
    var keys []int
    for k, _ := range m {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    for _, k := range keys {
        f(k, m[k])
    }
}

func main() {
    // Create a map for processing
    m := make(map[int]string)
    m[1] = "a"
    m[2] = "c"
    m[0] = "b"

    sortedMapIntString(m,
        func(k int, v string) { fmt.Println("Key:", k, "Value:", v) })
}

sortedMapIntString()Funkcja może być ponownie wykorzystane dla każdego map[int]string(zakładając, że pożądany jest taki sam porządek), utrzymując każdym użyciu tylko dwóch przewodów kodu.

Wady obejmują:

• Trudniej go czytać osobom nieprzyzwyczajonym do używania funkcji jako pierwszorzędnych
• Może być wolniejszy (nie robiłem porównań wydajności)

Inne języki mają różne rozwiązania:

• Jeśli użycie <K>and <V>(do oznaczania typów dla klucza i wartości) wygląda trochę znajomo, ten szablon kodu nie różni się zbytnio od szablonów C ++.
• Clojure i inne języki obsługują posortowane mapy jako podstawowe typy danych.
• Chociaż nie wiem w żaden sposób, w jaki sposób Go tworzy rangetyp pierwszej klasy, tak aby można go było zastąpić niestandardowym ordered-range(zamiast rangew oryginalnym kodzie), myślę, że niektóre inne języki zapewniają iteratory, które są wystarczająco potężne, aby osiągnąć to samo rzecz.

To zapewnia przykład kodu na mapie sortowania. Zasadniczo to, co zapewniają:

var keys []int
for k := range myMap {
    keys = append(keys, k)
}
sort.Ints(keys)

// Benchmark1-8      2863149           374 ns/op         152 B/op          5 allocs/op

i oto, co sugerowałbym użycie zamiast tego :

keys := make([]int, 0, len(myMap))
for k := range myMap {
    keys = append(keys, k)
}
sort.Ints(keys)

// Benchmark2-8      5320446           230 ns/op          80 B/op          2 allocs/op

Pełny kod można znaleźć w tym Go Playground .