Как извлечь значения x top int из карты в Голанге?

Question

У меня есть map[string]int

Я хочу получить из него значения x top и сохранить их в другой структуре данных, другой карте или срезе.Из https://blog.golang.org/go-maps-in-action#TOC_7. я понял, что:

При итерации по карте с помощью цикла диапазона порядок итераций не указывается и не гарантируется, что он будет одинаковым от одной итерации к следующей..

, поэтому структура результата будет срезом.

Я посмотрел несколько связанных тем, но ни одна из них не подходит для моей проблемы:

relatedтема 1

связанная тема 2

связанная тема 3

Что было бы наиболее эффективным способом сделатьэто пожалуйста?

Спасибо,

Редактировать: Мое решение было бы превратить мою карту в слайс и отсортировать ее, а затем извлечь первые значения х.
Но есть ли лучший способ?

package main

import (
    "fmt"
    "sort"
)

func main() {

    // I want the x top values
    x := 3

    // Here is the map
    m := make(map[string]int)
    m["k1"] = 7
    m["k2"] = 31
    m["k3"] = 24
    m["k4"] = 13
    m["k5"] = 31
    m["k6"] = 12
    m["k7"] = 25
    m["k8"] = -8
    m["k9"] = -76
    m["k10"] = 22
    m["k11"] = 76

    // Turning the map into this structure
    type kv struct {
        Key   string
        Value int
    }

    var ss []kv
    for k, v := range m {
        ss = append(ss, kv{k, v})
    }

    // Then sorting the slice by value, higher first.
    sort.Slice(ss, func(i, j int) bool {
        return ss[i].Value > ss[j].Value
    })

    // Print the x top values
    for _, kv := range ss[:x] {
        fmt.Printf("%s, %d\n", kv.Key, kv.Value)
    }
}

Ссылка на пример игровой площадки golang

Если я хочу получить карту в конце со значениями x top, то с моим решением мне придетсяпревратить часть в карту снова.Это все еще будет самый эффективный способ сделать это?

Answer 1

Создание среза и сортировки - прекрасное решение;однако вы также можете использовать heap .Производительность Big O должна быть одинаковой для обеих реализаций (n log n), так что это жизнеспособная альтернатива с тем преимуществом, что если вы хотите добавить новые записи, вы все равно можете эффективно получить доступ к верхним N элементам без повторной сортировки всего набора.

Чтобы использовать кучу, вы должны реализовать heap.Interface для типа kv с помощью функции Less, которая сравнивает значения как больше (h[i].Value > h[j].Value), добавьте все записи с карты, а затем выделите количество элементов, которые вы хотите использовать.

Например ( Go Playground ):

func main() {
  m := getMap()

  // Create a heap from the map and print the top N values.
  h := getHeap(m)
  for i := 1; i <= 3; i++ {
    fmt.Printf("%d) %#v\n", i, heap.Pop(h))
  }
  // 1) main.kv{Key:"k11", Value:76}
  // 2) main.kv{Key:"k2", Value:31}
  // 3) main.kv{Key:"k5", Value:31}
}

func getHeap(m map[string]int) *KVHeap {
  h := &KVHeap{}
  heap.Init(h)
  for k, v := range m {
    heap.Push(h, kv{k, v})
  }
  return h
}

// See https://golang.org/pkg/container/heap/
type KVHeap []kv

// Note that "Less" is greater-than here so we can pop *larger* items.
func (h KVHeap) Less(i, j int) bool { return h[i].Value > h[j].Value }
func (h KVHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h KVHeap) Len() int           { return len(h) }

func (h *KVHeap) Push(x interface{}) {
  *h = append(*h, x.(kv))
}

func (h *KVHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}