dregvw1801
2018-10-01 22:44
浏览 70
已采纳

如何分配内存以映射指向golang中的切片

Is there a way to allocate the memory of a map, which has at most Nmax keys, that points to a slice of maximum length Nmax?

I'm currently just specifying the max number of keys via make(map[int][]int,Nmax), but I'm not sure how to tell Go that each slice will be of maximum length Nmax because I don't know what the keys will be apriori.

I essentially have a bunch of sites with an integer population. I use the map to keep track of how many sites have a given population N. The bottleneck in my program appears to be runtime.memmove, which I'm guessing comes from constant resizing of the slice the map points to.

图片转代码服务由CSDN问答提供 功能建议

是否有一种方法来分配地图的内存,该内存最多具有 Nmax 键,指向最大长度为 Nmax 的切片?

我目前只是通过 make(map [int] [] int,Nmax)指定最大键数,但是我不确定如何 告诉Go,每个切片的最大长度为 Nmax ,因为我不知道键是先验的。

我基本上有很多站点 具有整数人口。 我使用地图跟踪给定人口 N 的站点数。 我程序中的瓶颈似乎是runtime.memmove,我猜想这是由于不断调整地图所指向切片的大小而引起的。

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • douya1974 2018-10-02 13:31
    已采纳

    So given that your description of the problem is really rather vague, I'll just start by saying how I'd go about "managing" the map. To keep things simple, I'm going to wrap all the logic up in receiver functions, so wrapping the map up in a custom type:

    type dataMap struct {
        data map[int][]int
        nmax int
    }
    
    func New(Nmax int) *dataMap {
        return &dataMap{
            data: make(map[int][]int, Nmax),
            nmax: Nmax,
        }
    }
    
    // Get - return slice for given key
    func (d dataMap) Get(k int) []int {
        s, ok := d.data[k]
        if !ok {
            return nil // optionally return error
        }
        return s
    }
    
    // Set - set/append values to a given key - this is not safe for concurrent use
    // if that's needed, add a RWMutex to the type
    func (d *dataMap) Set(k int, vals ...int) error {
        s, ok := d.data[k]
        if !ok {
            s = make([]int, 0, d.nmax) // allocate slice of given length
        }
        // optionally check for nil-values + ensure we're not exceeding the nmax
        checked := make([]int, 0, len(vals))
        for i := range vals {
            if vals[i] != 0 {
                checked = append(checked, vals[i])
            }
        }
        if len(s) + len(checked) > d.nmax {
            return errors.New("max capacity exceeded")
        }
        s = append(s, checked...) // append values
        d.data[k] = s // update map
        return nil
    }
    

    This cuts down on needless memory (re-)allocation calls. It also ensures that I can get the length of any slice in the map in an O(1) operation, without having to worry about nil values:

    myData := New(10)
    fmt.Println(myData.Set(4, 1, 2, 3, 4))
    fmt.Println(len(myData.Get(4))) // 4
    fmt.Println(cap(myData.Get(4))) // 10
    // nil-values are filtered out
    myData.Set(4, 5, 6, 7, 0, 0, 0, 0)
    fmt.Println(len(myData.Get(4))) // 7
    fmt.Println(cap(myData.Get(4))) // 10
    // exceeding capacity of 10
    fmt.Println(myData.Set(4, 8, 9, 10, 11)) // max capacity exceeded
    

    working demo


    You could manage the capacity by using an array instead of a slice, but that does require you to manually keep track of the index/offset at which you want to start appending values. Generally speaking, you don't use arrays in golang lest in very, very specific cases. In this case, I'd just opt for a slice with a set cap. The advantage of this is that you could, for example have slices of different lengths. The result is very easy to test, too, because a type like this lends itself quite well to replacing it with an interface type

    type DataContainer interface {
        Get(k int) []int
        Set(k int, vals ...int) error
        Declare(k, capacity int) error // error if k is already in use?
    }
    
    已采纳该答案
    打赏 评论
  • dthh5038 2018-10-02 06:28

    Your description of your problen is vague and you have not provided code to illustrate your problem.

    If the map slice capacity is equal to zero then set it to Nmax. For example,

    package main
    
    import "fmt"
    
    func main() {
        Nmax := 42
    
        m := make(map[int][]int, Nmax)
    
        k, e := 7, 11
        v := m[k]
        if cap(v) == 0 {
            v = make([]int, 0, Nmax)
        }
        m[k] = append(v, e)
    
        v = m[k]
        fmt.Println(k, len(v), cap(v), v)
    
        fmt.Println(m)
    }
    

    Playground: https://play.golang.org/p/csoUCUvVDAp

    Output:

    7 1 42 [11]
    map[7:[11]]
    
    打赏 评论

相关推荐 更多相似问题