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

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

Цели

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

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

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

• Преобразуйте начальный массив в срез длиной L ^ 2, объединив строки по порядку, например. cdfpop[i L +j]=initialpopulation[i][j].
• Преобразуйте одномерный срез в cdf, запустив цикл for над cdfpop[i]+=cdfpop[i-1].
• Сгенерируйте два случайных числа, Rsite, диапазон которых составляет от 1 до наибольшего значения в cdf (это только последнее значение, cdfpop[L^2-1]), и Rhop, диапазон которого находится в диапазоне от 1 до 4. Первое случайное число выбирает взвешенный случайный сайт, а второе число - случайное направление для прыжка
• Используйте двоичный поиск, чтобы найти крайний левый индекс indexhop из cdfpop, который больше Rsite. Индекс, к которому осуществляется переход, равен либо 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 минуты в среднем с моими текущими настройками, и я могу компилировать данные о населении в gif каждые 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 без пересчета, очень хорошо подумав, когда я пытаюсь смоделировать проблемы возрастающей сложности, я не могу не задаться вопросом, есть ли универсальное решение с разумной эффективностью, которое мне не хватает это не требует специального кода для каждого случайного процесса.

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