Существует ли элегантный и эффективный способ реализации взвешенного случайного выбора в golang?Подробности о текущей реализации и проблемах внутри

Question

tl; dr: Я ищу методы для реализации взвешенного случайного выбора на основе относительной величины значений (или функций значений) в массиве в golang.Существуют ли стандартные алгоритмы или рекомендуемые пакеты для этого?Так как они масштабируются?

Цели

Я пытаюсь писать программы процесса Маркова 2D и 3D в golang.Простым 2D примером этого является следующее: представьте, что у каждого есть решетка, и на каждом сайте, помеченном индексом (i, j), есть n (i, j) частиц.На каждом временном шаге программа выбирает сайт и перемещает одну частицу с этого сайта на случайный соседний сайт.Вероятность выбора сайта пропорциональна его населению n (i, j) в то время.

Текущая реализация

Мой текущий алгоритм, например, для двумерного случая на решетке L x L, следующий:

• Преобразоватьначальный массив в срез длиной L ^ 2 путем объединения строк по порядку, например cdfpop[i L +j]=initialpopulation[i][j].
• Преобразование 1D среза в файл cdf, запустив цикл for cdfpop[i]+=cdfpop[i-1].
• Генерация двух случайных чисел, Rsite, чей диапазон от 1 до наибольшего значения в cdf (это только последнее значение, cdfpop[L^2-1]), и Rhop, чей диапазон от 1 до4. Первое случайное число выбирает взвешенный случайный узел, а второе - случайное направление для перехода в
• . Используйте двоичный поиск, чтобы найти самый левый индекс indexhop из cdfpop, который больше * 1031.*.Индекс, к которому выполняется переход, равен либо indexhop +-1 для прыжков в направлении x, либо indexhop +- L для прыжков в направлении y.
• Наконец, непосредственно измените значения cdfpop, чтобы отразить процесс перехода.Это означает вычитание одного из (добавление одного к) всех значений в cdfpop между индексом, по которому выполняется переход из (в), и индексом, по которому выполняется переход из (в), в зависимости от порядка.
• Промыть и повторить цикл.В конце переверните cdf, чтобы определить окончательную популяцию.

Редактировать: Запрошенный псевдокод выглядит следующим образом:

main(){

       //import population LxL array
       population:= import(population array)

       //turn array into slice
       for i number of rows{
          cdf[ith slice of length L] = population[ith row]
          }
       //compute cumulant array
       for i number of total sites{
          cdf[i] = cdf[i-1]+cdf[i]
          }

       for i timesteps{
          site = Randomhopsite(cdf)
          cdf = Dohop(cdf, site)
          } 

       Convertcdftoarrayandsave(cdf)
       }

Randomhopsite(cdf) site{

      //Choose random number in range of the cummulant
      randomnumber=RandomNumber(Range 1 to Max(cdf))


      site = binarysearch(cdf) // finds leftmost index such that                                           
                               // cdf[i] > random number

      return site
      }

Dohop(cdf,site) cdf{ 

      //choose random hop direction and calculate coordinate
      randomnumber=RandomNumber(Range 1 to 4)
      case{
            randomnumber=1 { finalsite= site +1}
            randomnumber=2 { finalsite= site -1}
            randomnumber=3 { finalsite= site + L}
            randomnumber=4 { finalsite= site - L}
           }

      //change the value of the cumulant distribution to reflect change
      if finalsite > site{
           for i between site and finalsite{
                        cdf[i]--
              }
      elseif finalsite < site{
           for i between finalsite and site{
                        cdf[i]++
              }
      else {error: something failed}


      return cdf
      }

Этот процесс очень хорошо работает для простых задач.Для этой конкретной проблемы я могу выполнить около 1 триллиона шагов на решетке 1000x1000 в среднем за 2 минуты с моими текущими настройками, и я могу скомпилировать данные о населении в гифки каждые 10000 или около того шагов, вращая процедуру go без огромныхпомедленнее.

Там, где эффективность снижается

Проблема возникает, когда я хочу добавить различные процессы с реальными коэффициентами, показатели которых не пропорциональны населению сайта.Так, скажем, у меня теперь есть скачкообразная скорость в k_hop * n (i, j) и уровень смертности (где я просто удаляю частицу) в k_death * (n (i, j)) ^ 2.В этом случае есть два замедления:

• Мой cdf будет в два раза больше (не такая уж большая проблема).Он будет реально оценен и создан cdfpop[i*L+j]= 4 *k_hop * pop[i][j] для i*L+j<L*L и cdfpop[i*L+j]= k_death*math. Power(pop[i][j],2) для L*L<=i*L+j<2*L*L, за которым следует cdfpop[i]+=cdfpop[i-1].Затем я выбрал бы случайное действительное число в диапазоне cdf.
• Из-за квадрата n мне придется динамически пересчитывать часть cdf, связанную с весами процесса смерти на каждом шаге.Это главное замедление, как и ожидалось.Время для этого составляет около 3 микросекунд по сравнению с оригинальным алгоритмом, который занимал менее наносекунды.

Эта проблема только усугубляется, если у меня есть показатели, рассчитанные в зависимости от численности населения на соседних участках - например, спонтанное образование частиц зависит от произведения населения на соседних участках.Несмотря на то, что я надеюсь найти способ просто изменить cdf без перерасчета, подумав очень серьезно, я пытаюсь смоделировать проблемы растущей сложности, но я не могу не задаться вопросом, есть ли универсальное решение с разумной эффективностью, которое я пропускаюэто не требует специализированного кода для каждого случайного процесса.

Спасибо за чтение!