Сортировка значений карты 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
    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])
    }
}

Выход:

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

Согласно спецификации 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
}

Все ответы здесь теперь содержат старое поведение карт. В 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 сравнивает ложь перед истиной
• Комплекс сравнивает реальное, а затем воображаемое
• Указатели сравниваются по машинному адресу
• Значения каналов сравниваются по машинному адресу
• Структуры сравнивают каждое поле по очереди
• Массивы по очереди сравнивают каждый элемент
• Значения интерфейса сравниваются сначала с помощью параметра «Отражение. Тип», описывающего конкретный тип, а затем по конкретному значению, как описано в предыдущих правилах.

При печати карт нерефлексивные ключевые значения, такие как NaN, ранее отображались как <nil>. Начиная с этого выпуска печатаются правильные значения.

Подробнее читайте здесь .

В ответ на Джеймса Крэйга Берли ответ . Чтобы создать чистый и повторно используемый дизайн, можно выбрать более объектно-ориентированный подход. Таким образом можно безопасно привязать методы к типам указанной карты. Мне такой подход кажется чище и организованнее.

Пример:

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-кода (который Go версии 1 не поддерживает как есть):

/* 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 и другие языки поддерживают отсортированные карты как фундаментальные типы данных.
• Хотя я не знаю, каким образом Go создает rangeпервоклассный тип, чтобы его можно было заменить обычным ordered-range(вместо rangeисходного кода), я думаю, что некоторые другие языки предоставляют итераторы, достаточно мощные, чтобы выполнять то же самое. вещь.

Это дает вам пример кода на карте сортировки. В основном это то, что они предоставляют:

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 .