在我的模拟多粒子进化的程序中，我有一个地图，它取一个键值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 的内存并且很愚蠢。我尝试将指针指向相关切片以制作查找切片，但禁止这样做。我可以汇总每个切片的长度并基于此生成一个随机数，然后按长度遍历 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循环外。 因此，这个想法是在循环内测试候选人是否是 siteSelected ，并避免将候选人复制到此预选池中。