Сортировать значения карты Go по ключам
При переборе возвращенной карты в коде, возвращенном функцией темы, ключи отображаются не по порядку.
Как получить ключи в порядке / отсортировать карту, чтобы ключи были в порядке и значения соответствовали?
Вот код
8 ответов
Блог Go: Карты Go в действии имеют отличное объяснение.
При итерации по карте с помощью цикла диапазона порядок итераций не указывается и не гарантируется, что он будет одинаковым от одной итерации к следующей. Начиная с Go 1 среда выполнения рандомизирует порядок итераций карты, так как программисты полагались на стабильный порядок итераций предыдущей реализации. Если вам требуется стабильный порядок итераций, вы должны поддерживать отдельную структуру данных, которая определяет этот порядок.
Вот моя модифицированная версия примера кода: 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
var keys []int
for k := range m {
keys = append(keys, k)
}
sort.Ints(keys)
// To perform the opertion you want
for _, k := range keys {
fmt.Println("Key:", k, "Value:", m[k])
}
}
Выход:
Key: 0 Value: b
Key: 1 Value: a
Key: 2 Value: c
Все ответы здесь теперь содержат старое поведение карт. В Go 1.12+ вы можете просто напечатать значение карты, и оно будет автоматически отсортировано по ключу. Это было добавлено, потому что это позволяет легко тестировать значения карт.
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]
}
Карты теперь печатаются в порядке сортировки ключей, чтобы упростить тестирование. Правила заказа:
- Когда это применимо, ноль сравнивается с низким
- порядок чисел, чисел с плавающей точкой и строк по <
- NaN сравнивает меньше, чем не-NaN
- bool сравнивает false перед true
- Комплекс сравнивает реальное, то и воображаемое
- Указатели сравниваются по машинному адресу
- Значения каналов сравниваются по машинному адресу
- Структуры сравнивают каждое поле по очереди
- Массивы сравнивают каждый элемент по очереди
- Значения интерфейса сначала сравниваются по отражению. Тип, описывающий конкретный тип, а затем по конкретному значению, как описано в предыдущих правилах.
При печати карт значения неотражающих ключей, такие как NaN, ранее отображались как
<nil>, Начиная с этого выпуска, правильные значения печатаются.
Узнайте больше здесь.
В соответствии со спецификацией Go порядок итераций по карте не определен и может варьироваться между запусками программы. На практике он не только не определен, но и намеренно рандомизирован. Это потому, что раньше это было предсказуемо, и разработчики языка Go не хотели, чтобы люди полагались на неуказанное поведение, поэтому они намеренно сделали случайным образом, чтобы полагаться на это поведение было невозможно.
То, что вам нужно сделать, это вытащить ключи в срез, отсортировать их, а затем расположить их по диапазону следующим образом:
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
}
В ответ на ответ Джеймса Крейга Берли. Чтобы создать чистый и многократно используемый дизайн, можно выбрать более объектно-ориентированный подход. Таким образом, методы могут быть безопасно связаны с типами указанной карты. Для меня такой подход выглядит чище и организованнее.
Пример:
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])
}
}
Пример расширенной игровой площадки с несколькими типами карт.
Важная заметка
Во всех случаях карта и отсортированный фрагмент отделяются от момента for цикл по карте range закончен. Это означает, что, если карта модифицируется после логики сортировки, но перед ее использованием вы можете столкнуться с проблемами. (Не нить / Go рутина безопасна). При изменении доступа к записи параллельной карты вам нужно будет использовать мьютекс вокруг записей и отсортированных for петля.
mutex.Lock()
for _, k := range m.sort() {
fmt.Println(m[k])
}
mutex.Unlock()
Если, как и я, вы обнаружите, что вы хотите, по сути, один и тот же код сортировки в нескольких местах или просто хотите уменьшить сложность кода, вы можете абстрагировать саму сортировку в отдельную функцию, которой вы передаете функцию, которая выполняет фактическая работа, которую вы хотите (которая будет отличаться в каждом месте, конечно).
Дана карта с типом ключа K и тип значения Vв виде <K> а также <V> ниже общая функция сортировки может выглядеть примерно так:
/* 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)
}
}
Затем вызвать его с входной картой и функцией (принимая k <K> v <V> в качестве входных аргументов), который вызывается поверх элементов карты в порядке сортировки ключей.
Итак, версия кода в ответе, опубликованном Mingu, может выглядеть так:
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() функция может быть повторно использована для любого map[int]string (при условии, что требуется один и тот же порядок сортировки), сохраняя каждое использование только двумя строками кода.
Недостатки включают в себя:
- Труднее читать людям, не привыкшим использовать функции в качестве первого класса
- Это может быть медленнее (еще не проверял)
Другие языки имеют различные решения:
- Если использование
<K>а также<V>(для обозначения типов для ключа и значения) выглядит немного знакомым, этот шаблон кода не сильно отличается от шаблонов C++. - Clojure и другие языки поддерживают отсортированные карты как основные типы данных.
- Пока я не знаю, как Го делает
rangeпервоклассный тип такой, что он может быть заменен обычаемordered-range(на местеrangeв исходном коде), я думаю, что некоторые другие языки предоставляют итераторы, достаточно мощные, чтобы выполнить то же самое.
Похоже, вы без необходимости используете карту, когда хотите упорядочить результаты. Вместо этого вы можете использовать срез.
Вы хотите получить упорядоченные результаты с помощью этого кода:
func main() {
topic := tag("did. the quick, brown yet...")
for k, v := range topic {
fmt.Println("key:", k, "v:", v)
}
}
Вы делаете следующее в своем коде и, естественно, получаете неупорядоченный результат:
// +-- don't use a map
// v
func tag(text string) map[int]map[string]string{
// ...
toReturn := make(map[int]map[string]string)
for i, token := range matches {
// unnecessarily checking the map...
m, ok := toReturn[i]
if !ok{
m = make(map[string]string)
toReturn[i] = m
}
toReturn[i]["token"] = token
toReturn[i]["tag"] = "NN"
// ...
}
stopWords := [214]string{
"a",
"about",
// ...
}
isStopWord := map[string]bool{}
for _, sw := range stopWords{
isStopWord[sw] = true
}
for key, mapOne := range toReturn {
if isStopWord[mapOne["token"]] {
delete(toReturn, key)
}
}
return toReturn
}
Но вы можете получить упорядоченный результат, используя срез бесплатно, например :
// +-- use a slice.
// + ordering is free.
// v
func tag(text string) []map[string]string {
// ...
var toReturn []map[string]string
for i, token := range matches {
// append your map to the slice.
toReturn = append(toReturn, make(map[string]string))
// ...
}
// ...
for i := len(toReturn) - 1; i >= 0; i-- {
if m := toReturn[i]; isStopWord[m["token"]] {
toReturn[i] = toReturn[len(toReturn)-1]
toReturn = toReturn[:len(toReturn)-1]
}
}
return toReturn
}
Всегда используйте подходящий инструмент для работы.
Это дает вам пример кода на карте сортировки. В основном это то, что они предоставляют:
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
и вот что я бы предложил использовать вместо этого:
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
Полный код можно найти на этой игровой площадке Go.
Хотя большинство из этих ответов верны, я часто нахожу цикл for в стиле C наиболее простым решением (хотя только если ваши ключи представляют собой последовательность ints):
m := make(map[int]string)
m[1] = "a"
m[2] = "c"
m[0] = "b"
for i := 0; i < len(m); i++ {
fmt.Println("Key:", i, "Value:", m[i])
}
Выход:
Key: 0 Value: b
Key: 1 Value: a
Key: 2 Value: c