title: Randomly selecting elements from slices produced by a map in restricted key range in golang. Is there an O(1) shortcut?
body: <p>In my program to simulate many-particle evolution, I have a map that takes a key value <code>pop</code> (the population size) and returns a slice containing the sites that have this population: <code>myMap[pop][]int</code>. These slices are generically quite large. </p>
  
  <p>At each evolution step I choose a random population size <code>RandomPop</code>. I would then like to randomly choose a site that has a population of at least <code>RandomPop</code>. The <code>sitechosen</code> is used to update my population structures and I utilize a second map to efficiently update myMap keys. My current (slow) implementation looks like </p>
  
  <pre><code>func Evolve( ..., myMap map[int][]int ,...){
  
      RandomPop = rand.Intn(rangeofpopulation)+1
  
      for i:=RandPop,; i&lt;rangeofpopulation;i++{
          preallocatedslice=append(preallocatedslice,myMap[i]...)
      }
  
      randomindex:= rand.Intn(len(preallocatedslice))
      sitechosen= preallocatedslice[randomindex]
  
      UpdateFunction(site)
  
      //reset preallocated slice 
      preallocatedslice=preallocatedslice[0:0]
  
  }
  </code></pre>
  
  <p>This code (obviously) hits a huge bottle-neck when copying values from the map to preallocatedslice, with runtime.memmove eating 87% of my CPU usage. I'm wondering if there is an O(1) way to randomly choose an entry contained in the union of slices indicated by myMap with key values between <code>0</code> and <code>RandomPop</code> ? I am open to packages that allow you to manipulate custom hashtables if anyone is aware of them. Suggestions don't need to be safe for concurrency  </p>
  
  <p>Other things tried: I previously had my maps record all sites with values of at least <code>pop</code> but that took up >10GB of memory and was stupid. I tried stashing pointers to the relevant slices to make a look-up slice, but go forbids this. I could sum up the lengths of each slice and generate a random number based on this and then iterate through the slices in myMap by length, but this is going to be much slower than just keeping an updated cdf of my population and doing a binary search on it. The binary search is fast, but updating the cdf, even if done manually, is O(n). I was really hoping to abuse hashtables to speed up random selection and update if possible</p>
  
  <p>A vague thought I have is concocting some sort of nested structure of maps pointing to their contents and also to the map with a key one less than theirs or something.  </p>