当前位置：首页 > 文章列表 > Golang > Go问答 > 提取 Golang 地图中的前 x 个最大值

提取 Golang 地图中的前 x 个最大值

来源：stackoverflow 2024-03-25 18:54:34 0浏览收藏

本文讨论了如何从 Go 语言中一个键值映射中提取最大的 x 个值。作者尝试使用切片和排序来实现，但提出了一种使用堆数据结构的替代方案。使用堆的方法具有与排序相同的时间复杂度（n log n），并且在需要不断更新前 n 个最大值的情况下更加高效。

问题内容

我有一个 map[string]int

我想从中获取 x 个最高值并将它们存储在另一个数据结构、另一个映射或切片中。来自 https://blog.golang.org/go-maps-in-action#toc_7。我的理解是：

当使用范围循环迭代映射时，迭代顺序为未指定且不保证在一次迭代中相同到下一个。

所以结果结构将是一个切片。

我查看了几个相关主题，但没有一个适合我的问题：

解决方案

创建切片并排序是一个很好的解决方案；但是，您也可以使用 heap。两种实现的 big o 性能应该相同 (n log n)，因此这是一个可行的替代方案，其优点是如果您想添加新条目，您仍然可以有效地访问前 n 项无需重复对整个集合进行排序。

要使用堆，您可以使用 less 函数为 kv 类型实现 heap.Interface，该函数比较值大于 (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
}

以上就是《提取 Golang 地图中的前 x 个最大值》的详细内容，更多关于的资料请关注golang学习网公众号！

版本声明

本文转载于：stackoverflow 如有侵犯，请联系study_golang@163.com删除