1

Здравствуйте!

Имеется следующий агрегат:

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;

int n,m;
int d;
vector<char> used;

long long cnt = 0;

void dfs(int v){
    if (used[v]) return;
    used[v] = true;
    cnt++;
    for (int to: G[v])
        dfs(to);
 }


int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> d;
    G.resize(n);
    for (int i = 0; i<m; ++i){
        int x, y; cin >> x >> y;
        G[x].push_back(y);
    }



    for (int i = 0; i<n; ++i)
        sort(G[i].begin(), G[i].end());

    int start = clock();    
    used.resize(n,0);
    for (int i = 0; i<d; ++i){
        fill(used.begin(), used.end(), 0);
        for (int v = 0; v<n; ++v)
            dfs(v);
    }
    printf("cnt = %lld\n%.4fsec\n",cnt, (float)(clock() - start)/CLOCKS_PER_SEC);

    return 0;
}

Запускаю его на большом графе(n,m > 10^5) при d = 1000, подавая на вход дуги вперемешку, получаю 8sec. Запускаю на том же графе, подавая дуги в отсортированном порядке, получаю 1.2 сек.

Когда на вход дуги подаются в таком порядке, что сначала полностью заполняется G[0], затем G[1], G[2], ..., G[n-1], все отрабатывает намного быстрее, чем, если дуги подаются вперемешку.

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

Хотя, возможно, это связано с чем-то другим, тогда вопрос: из-за чего еще такое может происходить?

3
  • Непонятно, о чем вы говорите. Подготовьте компилируемый пример, который демонстрирует проблему. 4 ноя 2015 в 17:34
  • 1
    push_back добавляет элементы в конец вектора и при необходимости, переписывает весь вектор в новую область памяти, если для нового элемента нет места в текущей выделенной памяти. 4 ноя 2015 в 17:41
  • Не надо давать ссылки. Приведите здесь минимально компилируемую программу, которая наглядно демонстрирует проблему. 4 ноя 2015 в 18:22

2 ответа 2

1

При большом количестве дуг имеем два случая вот для этой части кода:

for (int i = 0; i<n; ++i)
    sort(G[i].begin(), G[i].end());
  1. Дуги отсортированы: время выполнения ничтожно мало.
  2. Дуги не отсортированы: время выполнения много больше.

Вместо того чтобы угадывать разбейте код на независимые части - ввод, сортировка и тд и замерьте время каждой.

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

Оформил отдельным ответом, так как предоставленный код вкорне меняет ситуацию по сравнению с изначальной.

2
  • Этот кусок кода так же участвует в подсчете времени. Тем не менее, основное время тратится на вызовы и исполнение dfs. Во всех случаях, элементы векторов уже отсортированы, но, из-за перемешанности во входных даннных, время сильно разнится.
    – Nekrolm
    4 ноя 2015 в 19:52
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещен в чат. 5 ноя 2015 в 5:37
0

Скорее всего в противовес предоставленному коду, где данные вводятся вручную, проблемный код получает данные из более быстрого источника. Также допускаю что измеряется в том числе и само заполнение векторов данными.

Описывать все недостатки предоставленного выше способа заполнения векторов лень. Ниже предоставлен максимально быстрый способ наполнения векторов при условии что до вставки данных известен их объем.

Внутреннее устройство vector таково, что данные идут одним непрерывным блоком памяти. Поэтому перед вставкой элементов в vector лучше заранее зарезервировать место под все элементы посредством std::vector::reserve. В таком случае будет максимум одно перераспределение памяти в момент вызова этой функции. В противном случае если добавляемых элементов много то будет многократно перевыделятся память с полным копированием ранее добавленных данных.

Перед кодом

for (int i = 0; i<m; ++i){
    int x, y; cin >> x >> y;
    G[x].push_back(y);
}

зарезервируйте место

for (int i = 0; i<n; ++i){
    G[i].reserve(m);
}
6
  • Проблема в том, что размеры векторов заранее неизвестны. Это первое. А второе - именно проблема в очень существенной разнице в быстродействии при одних и тех же входных данных, но сортированных и не сортированных
    – Nekrolm
    4 ноя 2015 в 18:51
  • Резервировать память здесь нельзя. Т.к n*m >= 10^10
    – Nekrolm
    4 ноя 2015 в 18:54
  • Вам уже написали - предоставьте минимальный воспроизводимый пример. Чтобы написать ответ мне пришлось сделать кучу допущений. Отчего же размеры векторов неизвестны? Сразу после получения значений n и m тайное становится явным и можно смело резервировать место и только потом уже заполнять вектора данными.
    – sba
    4 ноя 2015 в 18:55
  • Да, известны максимальные размеры, но резервировать столько места нельзя. Его просто нет. Ограничения на значения n и m таковы, что придется выделять более 4х Гбайт, чего не дозволено условиями. Пример входных данных, на которых будет заметна разница, очень большой, чтоб его прикладывать. Пример кода сейчас уже представлен.
    – Nekrolm
    4 ноя 2015 в 19:00
  • Прочитайте внимательно мой ответ, сделайте выводы и определите четко границы кода время выполнения которого Вы измеряете и сравниваете. Например, сейчас видно что вы измеряете в том числе и ввод с клавиатуры, а я, например, одно число ввожу секунд 5, другое примерно 42, как при таком разбросе можно что-то измерять непонятно.
    – sba
    4 ноя 2015 в 19:03

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.