Sortieren Sie die Go-Kartenwerte nach Schlüsseln

93

Beim Durchlaufen der zurückgegebenen Karte im Code, der von der Themenfunktion zurückgegeben wird, werden die Tasten nicht in der richtigen Reihenfolge angezeigt.

Wie kann ich die Schlüssel in Ordnung bringen / die Karte so sortieren, dass die Schlüssel in Ordnung sind und die Werte übereinstimmen?

Hier ist der Code .

gramme.ninja
quelle
Mögliches Duplikat von Wie man eine Karte in Golang der Reihe nach durchläuft?
RedGrittyBrick

Antworten:

156

Der Go-Blog: Go-Karten in Aktion bietet eine hervorragende Erklärung.

Beim Iterieren über eine Karte mit einer Bereichsschleife wird die Iterationsreihenfolge nicht angegeben und es wird nicht garantiert, dass sie von einer Iteration zur nächsten gleich ist. Seit Go 1 randomisiert die Laufzeit die Reihenfolge der Karteniterationen, da sich Programmierer auf die stabile Iterationsreihenfolge der vorherigen Implementierung verlassen haben. Wenn Sie eine stabile Iterationsreihenfolge benötigen, müssen Sie eine separate Datenstruktur verwalten, die diese Reihenfolge angibt.

Hier ist meine modifizierte Version des Beispielcodes: 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])
    }
}

Ausgabe:

Key: 0 Value: b
Key: 1 Value: a
Key: 2 Value: c
Mingyu
quelle
38
Dies kann mit keys := make([]int, len(m))und dann durch Index keys[i] = kanstelle vonappend
jpillora
18

Gemäß der Go-Spezifikation ist die Reihenfolge der Iteration über eine Karte undefiniert und kann zwischen den Programmläufen variieren. In der Praxis ist es nicht nur undefiniert, sondern auch absichtlich randomisiert. Dies liegt daran, dass es früher vorhersehbar war und die Entwickler der Go-Sprache nicht wollten, dass sich Menschen auf nicht spezifiziertes Verhalten verlassen. Deshalb haben sie es absichtlich randomisiert, sodass es unmöglich war, sich auf dieses Verhalten zu verlassen.

Was Sie dann tun müssen, ist, die Schlüssel in eine Scheibe zu ziehen, sie zu sortieren und dann wie folgt über die Scheibe zu strecken:

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
}
joshlf
quelle
Wait Slices sind Teile eines Arrays. Wie mache ich ein Stück nur der Schlüssel in der Karte?
gramme.ninja
1
In Go bezieht sich das Wort "Slice" auf eine Datenstruktur, die im Wesentlichen analog zu Java-Arrays ist. Es ist nur ein Terminologieproblem. Um die Schlüssel zu erhalten, müssen Sie sich explizit über die Karte erstrecken und ein Slice erstellen,
joshlf
Ah, okay. Danke, dass sie mich belehrt haben. Jetzt wird alles gerade gedruckt, dann alles ungerade. play.golang.org/p/K2y3m4Zzqd Wie kann ich es abwechseln, damit es in Ordnung ist?
gramme.ninja
1
Sie müssen das Slice sortieren, das Sie zurückerhalten (oder es alternativ in mapKeys sortieren, bevor Sie zurückkehren). Sie sollten das Sortierpaket überprüfen .
Joshlf
14

Alle Antworten hier enthalten jetzt das alte Verhalten von Karten. In Go 1.12+ können Sie einfach einen Kartenwert drucken und dieser wird automatisch nach Schlüssel sortiert. Dies wurde hinzugefügt, da es das Testen von Kartenwerten auf einfache Weise ermöglicht.

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]
}

Karten werden jetzt in schlüsselsortierter Reihenfolge gedruckt, um das Testen zu vereinfachen. Die Bestellregeln sind:

  • Wenn zutreffend, vergleicht Null niedrig
  • Ints, Floats und Strings werden nach <sortiert
  • NaN vergleicht weniger als Nicht-NaN-Floats
  • bool vergleicht false vor true
  • Komplex vergleicht real, dann imaginär
  • Zeiger vergleichen nach Maschinenadresse
  • Kanalwerte werden nach Maschinenadresse verglichen
  • Strukturen vergleichen nacheinander jedes Feld
  • Arrays vergleichen nacheinander jedes Element
  • Schnittstellenwerte werden zuerst nach Reflect verglichen. Typ, der den konkreten Typ beschreibt, und dann nach konkretem Wert, wie in den vorherigen Regeln beschrieben.

Beim Drucken von Karten wurden zuvor nichtreflexive Schlüsselwerte wie NaN als angezeigt <nil>. Ab dieser Version werden die richtigen Werte gedruckt.

Lesen Sie hier mehr .

Inanc Gumus
quelle
7
Dies scheint nur für das fmt-Paket und das Drucken zu gelten. Die Frage lautet, wie eine Karte sortiert werden soll und nicht, wie eine sortierte Karte gedruckt werden soll.
Tim
1
Er teilte einen Spielplatz Link. Dort druckt er nur eine Karte.
Inanc Gumus
2

Wenn Sie wie ich feststellen, dass Sie im Wesentlichen denselben Sortiercode an mehr als einer Stelle wünschen oder nur die Codekomplexität gering halten möchten, können Sie die Sortierung selbst in eine separate Funktion abstrahieren, an die Sie die entsprechende Funktion übergeben die eigentliche Arbeit, die Sie möchten (die natürlich an jedem Anrufort unterschiedlich wäre).

Bei einer Karte mit Schlüsseltyp Kund Werttyp V, dargestellt als <K>und <V>unten könnte die gemeinsame Sortierfunktion so etwas wie diese Vorlage Go-Code aussehen (die 1 Go - Version nicht als Service - Leistung nicht unterstützt):

/* 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)
    }
}

Rufen Sie es dann mit der Eingabekarte und einer Funktion ( (k <K>, v <V>)als Eingabeargumente) auf, die über die Kartenelemente in sortierter Schlüsselreihenfolge aufgerufen wird.

Eine Version des Codes in der Antwort von Mingu könnte also so aussehen:

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) })
}

Die sortedMapIntString()Funktion kann für jede wiederverwendet werden map[int]string(vorausgesetzt, die gleiche Sortierreihenfolge ist erwünscht), wobei jede Verwendung auf nur zwei Codezeilen beschränkt bleibt.

Nachteile sind:

  • Es ist schwieriger zu lesen für Leute, die nicht daran gewöhnt sind, Funktionen als erstklassig zu nutzen
  • Es könnte langsamer sein (ich habe keine Leistungsvergleiche durchgeführt)

Andere Sprachen haben verschiedene Lösungen:

  • Wenn die Verwendung von <K>und <V>(um Typen für den Schlüssel und den Wert zu bezeichnen) ein wenig vertraut erscheint, unterscheidet sich diese Codevorlage nicht wesentlich von C ++ - Vorlagen.
  • Clojure und andere Sprachen unterstützen sortierte Karten als grundlegende Datentypen.
  • Obwohl ich nicht weiß, wie Go rangeeinen erstklassigen Typ so erstellt, dass er durch einen benutzerdefinierten Typ ersetzt werden kann ordered-range(anstelle des rangeursprünglichen Codes), denke ich, dass einige andere Sprachen Iteratoren bereitstellen, die leistungsfähig genug sind, um dasselbe zu erreichen Ding.
James Craig Burley
quelle
2
Für Anfänger kann es sinnvoll sein, darauf hinzuweisen, dass die Syntax <K>, <V> in Go nicht unterstützt wird.
Justinhj
2

In ihrer Antwort auf James Craig Burley Antwort . Um ein sauberes und wiederverwendbares Design zu erstellen, könnte man sich für einen objektorientierteren Ansatz entscheiden. Auf diese Weise können Methoden sicher an die Typen der angegebenen Karte gebunden werden. Für mich fühlt sich dieser Ansatz sauberer und organisierter an.

Beispiel:

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])
    }
}

Erweitertes Spielplatzbeispiel mit mehreren Kartentypen.

Wichtige Notiz

In allen Fällen werden die Karte und das sortierte Segment ab dem Moment entkoppelt, an dem die forSchleife über die Karte rangebeendet ist. Das heißt, wenn die Karte nach der Sortierlogik geändert wird, aber bevor Sie sie verwenden, können Probleme auftreten. (Nicht Thread / Go Routine sicher). Wenn sich der parallele Map-Schreibzugriff ändert, müssen Sie einen Mutex um die Schreibvorgänge und die sortierte forSchleife verwenden.

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

Hier finden Sie das Codebeispiel zum Sortieren der Karte. Grundsätzlich bieten sie Folgendes:

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

und dies ist, was ich vorschlagen würde, stattdessen zu verwenden :

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

Den vollständigen Code finden Sie auf diesem Go-Spielplatz .

Erikas
quelle