случайный выбор пустого элемента вектора, когда можно заранее узнать, какие из них заполнены - PullRequest
Новая
       15

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

0 голосов
/ 26 ноября 2011

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

Кроме того, я включил всю функцию в случае других недостатков, которые могут быть обнаружены. 

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++;
}

Ответы [ 3 ]

3 голосов
/ 26 ноября 2011

Передайте случайное число, k, в диапазоне от [0, size-n_syns) до Age_Increment. Пусть Age_Increment вернет k-й пустой слот.

3 голосов
/ 26 ноября 2011

Поскольку вы уже просматриваете весь список в Age_Increment, обновите эту функцию, чтобы она возвращала список индексов неактивных синапсов.

Затем вы можете выбрать случайный элемент из этого списка напрямую.

2 голосов
/ 26 ноября 2011

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

...