Сортировать значения карты Go по ключам

Ответ 1

Go blog: Go maps in action имеет отличное объяснение.

При итерации по карте с циклом диапазона порядок итерации равен не указано и не гарантируется на одном и том же этапе к следующему. Начиная с Go 1, runtime рандомизирует порядок итерации карты, так как программисты полагались на стабильный порядок итераций предыдущего реализация. Если вам нужен стабильный порядок итераций, вы должны поддерживать отдельную структуру данных, которая определяет этот порядок.

Здесь моя измененная версия примера кода: 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

Ответ 2

В соответствии с Go spec порядок итераций по карте составляет undefined и может варьироваться между прогонами программы. На практике это не только undefined, но и преднамеренно рандомизировано. Это связано с тем, что он был предсказуемым, и разработчики языка 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
}

Ответ 3

Если, как и я, вы обнаружите, что хотите, по сути, один и тот же код сортировки в нескольких местах или просто хотите уменьшить сложность кода, вы можете абстрагировать саму сортировку в отдельную функцию, которой вы передаете функцию, которая выполняет фактическая работа, которую вы хотите (которая будет отличаться на каждом сайте вызова, конечно).

Учитывая карту с типом ключа 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 в исходном коде), но я думаю, что некоторые другие языки предоставляют мощные итераторы. достаточно, чтобы выполнить то же самое.

Ответ 4

Хотя большинство из этих ответов верны, я часто нахожу цикл for в стиле C как самое простое решение (хотя только если ваши ключи представляют собой последовательность int чисел):

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

Ответ 5

Вот мой подход:

• сначала мы создаем новую, инвертированную карту из исходной, что означает, что пары ключей будут инвертированы во вновь созданной карте:

  //Inverting maps
  invMap := make(map[int]string, len(values))
  for k,v := range values {
      invMap[v] = k
  }
  

• то мы определяем другое отображение, которое содержит только ключи, которые можно сортировать, используя для ex. алгоритм сортировки пузырьков.

  //Bubblesort
  func BubbleSort(arr[] int)[]int {
       for i:=1; i< len(arr); i++ {
          for j:=0; j < len(arr)-i; j++ {
              if (arr[j] > arr[j+1]) {
                  arr[j], arr[j+1] = arr[j+1], arr[j]
              }
          }
       }
       return arr
  }
  

И вот окончательный рабочий код:

package main

import (
    "fmt"
)

var (
    values = map[string]int{
    "alpha": 34, "bravo": 56, "charlie": 23,
    "delta": 87, "echo": 56, "foxtrot": 12, "golf": 34, "hotel": 16,
    "indio": 87, "juliet": 65, "kilo": 43, "lima": 98}
)
func main() {

    //Inverting maps
    invMap := make(map[int]string, len(values))
    for k,v := range values {
        invMap[v] = k
    }

    //Sorting
    sortedKeys := make([]int, len(invMap))
    var i int = 0
    for k := range invMap {
        sortedKeys[i] = k
        i++
    }
    fmt.Println("Sorted keys")
    bubbleSorted := BubbleSort(sortedKeys)
    fmt.Println(bubbleSorted)

    fmt.Println("Inverted map...")
    for _,k := range bubbleSorted {
        fmt.Printf("Key: %v, Value : %v\n", k, invMap[k])
    }
}

//Bubblesort
func BubbleSort(arr[] int)[]int {
    for i:=1; i< len(arr); i++ {
        for j:=0; j < len(arr)-i; j++ {
            if (arr[j] > arr[j+1]) {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

Ответ 6

Все ответы здесь теперь содержат старое поведение карт. В 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, ранее отображались как. Начиная с этого выпуска, правильные значения печатаются.

Узнайте больше здесь.