当前位置： > > > > 从 golang 中受限键范围内的映射生成的切片中随机选择元素。有 O(1) 的捷径吗？

从 golang 中受限键范围内的映射生成的切片中随机选择元素。有 O(1) 的捷径吗？

来源：stackoverflow
2024-04-26 11:39:37
0浏览
收藏

珍惜时间，勤奋学习！今天给大家带来《从 golang 中受限键范围内的映射生成的切片中随机选择元素。有 O(1) 的捷径吗？》，正文内容主要涉及到等等，如果你正在学习Golang，或者是对Golang有疑问，欢迎大家关注我！后面我会持续更新相关内容的，希望都能帮到正在学习的大家！

问题内容

在我的模拟多粒子进化的程序中，我有一个地图，它采用键值 pop （种群大小）并返回包含具有此种群的站点的切片：mymap[pop][]int。这些切片通常都很大。

在每个进化步骤中，我选择随机群体大小 randompop。然后，我想随机选择一个人口至少为 randompop 的站点。 sitechosen 用于更新我的人口结构，我利用第二个地图来有效更新 mymap 键。我当前（缓慢）的实现看起来像

func Evolve( ..., myMap map[int][]int ,...){

    RandomPop = rand.Intn(rangeofpopulation)+1

    for i:=RandPop,; i<rangeofpopulation;i++{
        preallocatedslice=append(preallocatedslice,myMap[i]...)
    }

    randomindex:= rand.Intn(len(preallocatedslice))
    sitechosen= preallocatedslice[randomindex]

    UpdateFunction(site)

    //reset preallocated slice 
    preallocatedslice=preallocatedslice[0:0]

}

这段代码（显然）在将值从映射复制到预分配切片时遇到了巨大的瓶颈，runtime.memmove 占用了我 87% 的 cpu 使用率。我想知道是否有一种 o(1) 方法可以随机选择 mymap 指示的切片并集中包含的条目，其键值介于 0 和 randompop 之间？如果有人知道的话，我对允许您操作自定义哈希表的软件包持开放态度。建议不需要保证并发安全

尝试过的其他事情：我之前让我的地图记录了所有值至少为 pop 的站点，但这占用了 >10gb 的内存，而且很愚蠢。我尝试将指针隐藏到相关切片以创建查找切片，但 go 禁止这样做。我可以总结每个切片的长度并基于此生成一个随机数，然后按长度迭代 mymap 中的切片，但这比仅保留人口的更新 cdf 并进行二分搜索要慢得多在上面。二分查找速度很快，但更新 cdf（即使手动完成）也是 o(n)。我真的希望滥用哈希表来加速随机选择和更新（如果可能的话）

我的一个模糊的想法是编造某种地图的嵌套结构，指向其内容，并且还指向具有比他们的键少的键或其他东西的地图。

解决方案

我正在查看您的代码，我有一个问题。 为什么必须将值从地图复制到切片？我的意思是，我认为我正在遵循背后的逻辑……但我想知道是否有办法跳过这一步。

所以我们有：

func evolve( ..., mymap map[int][]int ,...){

    randompop = rand.intn(rangeofpopulation)+1

    for i:=randpop,; i<rangeofpopulation;i++{
        // slice of preselected `sites`. one of this will be 'sitechosen'
        // we expect to have `n sites` on `preallocatedslice`
        // where `n` is the amount of iterations, 
        // ie; n = rangeofpopulation - randpop
        preallocatedslice=append(preallocatedslice,mymap[i]...) 
    }

    // once we have a list of sites, we select `one`
    // under a normal distribution every site ha a chance of 1/n to be selected.
    randomindex:= rand.intn(len(preallocatedslice))
    sitechosen= preallocatedslice[randomindex]

    updatefunction(site)
    ...

}

但是如果我们将其更改为：

func Evolve( ..., myMap map[int][]int ,...){

    if len(myMap) == 0 {
        // Nothing to do, print a log! 
        return
    }

    // This variable will hold our site chosen!
    var siteChosen []int

    // Our random population size is a value from 1 to rangeOfPopulation 
    randPopSize := rand.Intn(rangeOfPopulation) + 1

    for i := randPopSize; i < rangeOfPopulation; i++ {
        // We are going to pretend that the current candidate is the siteChosen 
        siteChosen = myMap[i]

        // Now, instead of copying `myMap[i]` to preAllocatedSlice
        // We will test if the current candidate is actually the 'siteChosen` here:

        // We know that the chances for an specific site to be the chosen is 1/n,
        // where n = rangeOfPopulation - randPopSize
        n := float64(rangeOfPopulation - randPopSize)
        // we roll the dice...
        isTheChosenOne := rand.Float64() > 1/n

        if isTheChosenOne {
            // If the candidate is the Chosen site, 
            // then we don't need to iterate over all the other elements.
            break
        }

    }

    // here we know that `siteChosen` is a.- a selected candidate, or 
    // b.- the last element assigned in the loop 
    // (in the case that `isTheChosenOne` was always false [which is a probable scenario])
    UpdateFunction(siteChosen)
    ...
}

此外，如果您想可以在循环外计算 n 或 1/n 。 因此，我们的想法是在循环内测试候选者是否是 sitechosen，并避免将候选者复制到此预选池中。

今天关于《从 golang 中受限键范围内的映射生成的切片中随机选择元素。有 O(1) 的捷径吗？》的内容介绍就到此结束，如果有什么疑问或者建议，可以在米云公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！