当可以事先知道哪些是满的时，随机选择一个空向量元素

Question

我最终确定这个函数是造成我大部分瓶颈问题的原因。我认为这是因为当大多数突触已经处于活动状态时会发生大量过度的随机访问。基本上，正如标题所说，我需要以某种方式优化算法，这样我就不会在找到剩下的少数元素之一之前随机检查大量活动元素。

另外，我还包含了整个功能，以防发现其他缺陷。

void NetClass::Explore(vector <synapse> & synapses, int & n_syns)   //add new synapses
{
    int size = synapses.size();
    assert(n_syns <= size );

    //Increase the age of each active synapse by 1
    Age_Increment(synapses);

    //make sure there is at least one inactive vector left
    if(n_syns == size)
        return;

        //stochastically decide whether a new connection is added
        if((rand_r(seedp) %1000) < ( x / (1 +(n_syns * ( y / 100)))))  
        {
            n_syns++; //a new synapse has been created

            //main inefficiency here
            while(1)
            {
                int syn = rand_r(seedp) % (size);
                if (!synapses[syn].active)
                {
                    synapses[syn].active = true;
                    synapses[syn].weight = .04 + (float (rand_r(seedp) % 17) / 100);     
                    break;
                }
            }
        }  
}

void NetClass::Age_Increment(vector <synapse> & synapses)  
{
    for(int q=0, int size = synapses.size(); q < size; q++)
        if(synapses[q].active)
            synapses[q].age++;
}

Answer 1

传递一个范围为 [0, size-n_syns) 到 Age_Increment 的随机数 k。让 Age_Increment 返回第 k 个空槽。

Answer 2

由于您已经遍历了 Age_Increment 中的整个列表，因此请更新该函数以返回非活动突触的索引列表。

然后，您可以直接从该列表中随机选择一个项目。

Answer 3

这类似于在内存管理中查找空闲块的问题，因此我会看看该域中使用的算法，特别是 空闲列表，这是空闲位置列表。 （这些通常作为链表实现，以便能够有效地从一端弹出元素。链表中的随机访问仍然是 O(n) - n 较小，但仍然不是您的用例的最佳选择。）