我有一个一维整数数组,在某些索引处具有非零值,其余为零。非零值等于索引。例如:
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。
这取决于您要优化的内容:代码的速度,空间或可读性?
如果有空格,您可以计算零的数目并从数组的长度中减去零(仅占用一个整数),然后生成介于1和n之间的随机索引n,然后找到第n个非零数组中的数字。这大约是O(2n)。
[如果是速度,则可能应该遍历数组,复制非零值,然后从结果数组中随机选择(它必须与原始数组大小相同,以容纳所有值)-这是O( n),但与原始阵列的内存量相同。
是否实际上更快取决于复制操作与仅是读取操作的实现速度。 “大哦”仅告诉您算法的顺序,您必须进行测试才能知道所使用的操作是否真正赋予了您期望的收益。