Как лучше всего в Фортране выбрать случайный ненулевой элемент из массива?

Question

У меня есть одномерный массив целых чисел с ненулевым значением по некоторым индексам, остальные равны нулю. Ненулевое значение равно индексу. Например:

CHOOSEARRAY = (/0,0,0,4,0,6,7/)

Я хочу выбрать случайным образом любой ненулевой элемент из этого массива. В этом случае я хочу, чтобы на выходе было либо 4,6, либо 7.

Мой текущий подход немного запутан и работает следующим образом:

Подсчитайте количество доступных вариантов

NCHOICE = COUNT(CHOOSEARRAY.NE.0)

Создайте массив и заполните его ненулевыми значениями

ALLOCATE(CHOICES(NCHOICE))
CHOICES = PACK(CHOOSEARRAY,CHOOSEARRAY.NE.0)

Выберите случайный элемент из этого нового массива

CHOSENVAL = CHOICES(FLOOR(1+GRND()*NCHOICE))

Здесь GRND () - это функция генерации случайных чисел, которая выводит действительное число, равномерно распределенное между 0 и 1.

Этот кодовый блок должен повторяться несколько раз, что требует нескольких операций выделения и освобождения, что может занять много времени. Есть ли лучший способ решить эту проблему?

В качестве альтернативы, есть ли способ вернуть индекс случайно выбранного ненулевого элемента? Например, (/ 0,1,1,0,0,1 /) с равной вероятностью должно дать либо 2,3, либо 6.

Answer 1

Если вы не боитесь нескольких делений на ноль, это может понравиться. Во-первых, давайте получим несколько случайных чисел ...

REAL, DIMENSION(SIZE(choosearray)) :: rands
CALL RANDOM_NUMBER(rands)

, тогда мы можем получить местоположение случайного ненулевого элемента из choosearray с выражением

MAXLOC(rands * choosearray/choosearray)

, а затем получить его значение с помощью

choosearray(MAXLOC(rands * choosearray/choosearray))

Я оставлю это вам, чтобы проверить скорость этого.

Answer 2

Это зависит от того, для чего вы оптимизируете: скорость, пространство или удобочитаемость вашего кода?

Если пробел, вы можете подсчитать количество нулей и вычесть его из длины массива (занимает только одно целое число), затем сгенерировать случайный индекс n между 1 и n, а затем найти n- -е ненулевое число в массиве. Это примерно O (2n).

Если скорость, вам, вероятно, следует l oop по массиву, копируя ненулевые значения, как вы go, а затем произвольно выбирать из результирующего массива (который должен быть того же размера, что и оригинал, чтобы вместить все значения) - это O (n), но стоит столько же памяти, сколько и исходный массив.

Будет ли это быстрее, зависит от скорости выполнения операции копирования или просто операции чтения. «Большое о» сообщает вам только порядок алгоритма, вам нужно будет проверить, действительно ли используемые вами операции приносят ожидаемую пользу.