doushi9474 2018-09-26 09:50
浏览 31
已采纳

如何从Golang的地图中提取x top int值?

I have a map[string]int

I want to get the x top values from it and store them in another data structure, another map or a slice. From https://blog.golang.org/go-maps-in-action#TOC_7. I understood that:

When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next.

so the result structure will be a slice then.

I had a look at several related topics but none fits my problem:

related topic 1

related topic 2

related topic 3

What would be the most efficient way to do this please?

Thanks,

Edit: My solution would be to turn my map into a slice and sort it, then extract the first x values.
But is there a better way ?

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
", kv.Key, kv.Value)
    }
}

Link to golang playground example

If I want to have a map at the end with the x top values, then with my solution I would have to turn the slice into a map again. Would this still be the most efficient way to do it?

  • 写回答

1条回答 默认 最新

  • dongyiyu882684 2018-09-28 15:18
    关注

    Creating a slice and sorting is a fine solution; however, you could also use a heap. The Big O performance should be equal for both implementations (n log n) so this is a viable alternative with the advantage that if you want to add new entries you can still efficiently access the top N items without repeatedly sorting the entire set.

    To use a heap, you would implement the heap.Interface for the kv type with a Less function that compares Values as greater than (h[i].Value > h[j].Value), add all of the entries from the map, and then pop the number of items you want to use.

    For example (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
    ", 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
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)