dregvw1801
dregvw1801
2018-10-01 22:44

如何分配内存以映射指向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.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • douya1974 douya1974 3年前

    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 dthh5038 3年前

    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]]
    
    点赞 评论 复制链接分享

相关推荐