Доступ к элементу Specifi c из списка пар в C ++

Question

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

void Graph::addEdge(long long int u, long long int v, long long int weight){

    list<pair<long long int,long long int> >::iterator i;

    int flag = 0;
    for(i = adj[u].begin(); i!= adj[u].end(); ++i){
        if((*i).first == v && weight>(*i).second){
            flag = 1;
            break;
        }
    }
    if(flag == 1){
        return;
    }

    adj[u].push_back(make_pair(v, weight));
    adj[v].push_back(make_pair(u, weight));
}

Answer 1

Я могу предложить некоторые оптимизации для этого кода:

1. Используйте std :: vector или std :: array вместо std :: list. список реализован в виде связанного списка, а обход равен медленно . вектор и массив также удобнее для кэша, так как данные хранятся последовательно, и, таким образом, более одного элемента будут загружены в кэш одновременно.
2. Использование массива / вектора unordered_map вместо каждой пары, так что adj[u] будет соответствовать карте ha sh с узлом v в качестве ключа и минимальным весом в качестве значения. Чтобы еще больше повысить производительность этой карты ha sh, вы можете предоставить собственную функцию ha sh и собственный метод разрешения столкновений после прохождения стандартного поведения и, если это подходит для вашего случая. В противном случае std :: unordered_map достаточно эффективен. Обратите внимание, что использование unordered_map выгоднее только в случае вставки / запросов Для обхода это печально.