Блог

Я пишу программу для генерации графика и проверки, подключен он или нет. Ниже приведен код. Вот некоторое объяснение: я генерирую несколько точек на плоскости в случайных местах. Затем я соединяю узлы НЕ только на основе близости. Под этим я подразумеваю, что узел с большей вероятностью будет подключен к узлам, которые находятся ближе, и это определяется случайной величиной, которую я использую в коде (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() amp;amp; 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;
}
  

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

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

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

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

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

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

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

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

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

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

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