повышение производительности для вычисления связности графа - PullRequest
Новая
       14

повышение производительности для вычисления связности графа

1 голос
/ 15 апреля 2011


Я пишу программу для генерации графика и проверки, подключен он или нет. Ниже приведен код. Вот некоторые объяснения: я генерирую количество точек на плоскости в случайных местах. Затем я соединяю узлы, НЕ основываясь только на близости. Под этим я имею в виду, что более вероятно, что узел будет связан с узлами, которые находятся ближе, и это определяется случайной величиной, которую я использую в коде (h_sq), и расстоянием. Следовательно, я генерирую все ссылки (симметричные, то есть, если я могу говорить с j, наоборот) также и проверяю с BFS, чтобы видеть, связан ли граф.
Моя проблема в том, что код, кажется, работает правильно. Однако, когда число узлов становится больше ~ 2000, это ужасно медленно, и мне нужно много раз запускать эту функцию для целей моделирования. Я даже пытался использовать другие библиотеки для графиков, но производительность такая же. Кто-нибудь знает, как я мог все ускорить?

Спасибо 

int Graph::gen_links() {
    if( save == true ) { // in case I want to store the structure of the graph
        links.clear();
        links.resize(xy.size());
    }

    double h_sq, d;
    vector< vector<luint> > neighbors(xy.size());

    // generate links
    double tmp = snr_lin / gamma_0_lin;
    // xy is a std vector of pairs containing the nodes' locations
    for(luint i = 0; i < xy.size(); i++) {
        for(luint j = i+1; j < xy.size(); j++) {
            // generate |h|^2
            d = distance(i, j);
            if( d < d_crit ) // for sim purposes
                d = 1.0;
            h_sq = pow(mrand.randNorm(0, 1), 2.0) + pow(mrand.randNorm(0, 1), 2.0);
            if( h_sq * tmp  >= pow(d, alpha) ) {
                // there exists a link between i and j
                neighbors[i].push_back(j);
                neighbors[j].push_back(i);
                // options
                if( save == true )
                    links.push_back( make_pair(i, j) );
            }
        }
        if( neighbors[i].empty() && save == false  ) {
        // graph not connected. since save=false i dont need to store the structure, 
        // hence I exit
            connected = 0; 
            return 1;  
        }
    }

    // here I do BFS to check whether the graph is connected or not, using neighbors
    // BFS code...
    return 1;
}

UPDATE: кажется, что основная проблема заключается в вызовах push_back во внутренних циклах for. Это та часть, которая занимает большую часть времени в этом случае. Должен ли я использовать Reserve () для повышения эффективности?

Ответы [ 2 ]

0 голосов
/ 10 апреля 2012

В качестве первого шага вы должны попытаться использовать резерв как для внутреннего, так и для внешнего векторов.

Если это не повышает производительность в соответствии с вашими ожиданиями, я считаю, что это происходит из-за выделения памяти, которое все еще происходит.

Есть удобный класс, который я использовал в подобных ситуациях, llvm :: SmallVector (найдите его в Google).Он предоставляет вектор с несколькими предварительно выделенными элементами, так что вы можете уменьшить количество распределений по одному на вектор.Он по-прежнему может расти, когда у него заканчиваются элементы в заранее выделенном пространстве.

Итак: 1) Изучите количество элементов, которые у вас есть в векторах в среднем во время пробегов (я говорю как о внутренних, так ивнешние векторы) 2) Поместите в llvm :: SmallVector с предварительным выделением такого размера (поскольку вектор выделяется в стеке, вам может потребоваться увеличить размер стека или уменьшить предварительное выделение, если вы ограничены в доступной памяти стека).

Еще одна хорошая вещь о SmallVector - это то, что он имеет почти тот же интерфейс, что и std :: vector (его можно легко поставить вместо него)

0 голосов
/ 15 апреля 2011

Вы уверены, что медлительность вызвана генерацией, а не алгоритмом поиска?

Генерация графа O (n ^ 2), и вы не можете сделать с этим слишком много. Однако вы, очевидно, можете использовать память взамен некоторого времени, если места точек фиксированы хотя бы для некоторых экспериментов.

Во-первых, расстояния всех пар узлов и pow (d, alpha) можно предварительно вычислить и сохранить в памяти, чтобы вам не приходилось вычислять их снова и снова. Стоимость дополнительной памяти для 10000 узлов составит около 800 МБ для двойного и 400 МБ для флотации.

Кроме того, сумма квадрата нормальной переменной является распределением хи-квадрат, если я правильно помню .. Возможно, у вас может быть какой-то предварительно вычисленный поиск в таблице, если допустимая точность?

Наконец, если вероятность того, что два узла будут соединены, настолько мала, если расстояние превышает некоторое значение, тогда вам не нужно O (n ^ 2) и, вероятно, вы можете рассчитать только те пары узлов, которые имеют расстояние меньше чем некоторые пределы?

...