Проблемы с производительностью в C ++ (с использованием VC ++ 2010): во время выполнения моя программа, кажется, случайным образом некоторое время ждет

Question

В настоящее время я пытаюсь закодировать определенный подход динамического программирования для проблемы с маршрутизацией транспортного средства.В определенный момент у меня есть частичный маршрут, который я хочу добавить к minmaxheap, чтобы сохранить 100 лучших частичных маршрутов на одном этапе.Большая часть программы работает гладко, но когда я на самом деле хочу вставить частичный маршрут в кучу, все идет немного медленнее.Этот конкретный код показан ниже:

 clock_t insert_start, insert_finish, check1_finish, check2_finish;

insert_start = clock();
check2_finish = clock();

if(heap.get_vector_size() < 100) {
    check1_finish= clock();
    heap.insert(expansion);
    cout << "node added" << endl;
}
else {
    check1_finish = clock();
    if(expansion.get_cost() < heap.find_max().get_cost() ) {
        check2_finish = clock();
        heap.delete_max();
        heap.insert(expansion);
        cout<< "worst node deleted and better one added"   <<endl;
    }
    else {
        check2_finish = clock();
        cout << "cost too high check"<<endl;
    }
}

number_expansions++;

cout << "check 1 takes " << check1_finish - insert_start << " ms" << endl;
cout << "check 2 takes " << check2_finish - check1_finish << "ms " << endl;

insert_finish = clock();

cout << "Inserting an expanded state into the heap takes " << insert_finish - insert_start << " clocks" << endl;

Типичный вывод такой:

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 0 clocks

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 16 clocks

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 0 clocks

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

Мое единственное предположение, что что-то происходит с вектором в классе кучи, в котором хранятся все эти состояния, но я резервирую место для 100 элементов в конструкторе, используя vector :: reserve, поэтому я не понимаю, как это могловсе еще проблема.

Спасибо!

Answer 1

упреждение. Ваша программа может быть прервана операционной системой, поэтому некоторые другие программы могут работать немного.

Кроме того, это не 16 мс. Это 16 тактов: http://www.cplusplus.com/reference/clibrary/ctime/clock/

Если вы хотите MS, вам нужно сделать:

cout << "Inserting an expanded state into the heap takes "
     << (insert_finish - insert_start) * 1000 / CLOCKS_PER_SEC
     << " ms " << endl;

Наконец, вы устанавливаете insert_finish после распечатки других результатов. Попробуйте установить его сразу после блока if / else. Команда cout - хорошее время для вытеснения другим процессом.

Answer 2

Попробуйте измерить время с помощью QueryPerformanceCounter, потому что я думаю, что функция часов не может быть очень точной. Вероятно, часы имеют ту же точность, что и планировщик windows - 10 мс для одного процессора и 15 или 16 мс для многоядерного процессора. QueryPerformanceCounter вместе с QueryPerformanceFreq может предоставить вам наносекундное разрешение.

Answer 3

Мое единственное предположение, что что-то происходит с вектором в куче класс, который хранит все эти состояния, но Я резервирую место для 100 предметов в конструктор, используя вектор :: резерв, поэтому я не понимаю, как это все еще может быть проблема.

Используете ли вы std :: vector для его реализации? Вставка занимает линейное время для std :: vector. Также можно удалить максимум, если вы не используете отсортированный контейнер.

Я предлагаю вам использовать std :: set или std :: multiset. Вставить, удалить и найти дубль всегда ln (n).

Answer 4

Похоже, вы измеряете "время стены", а не время процессора.Сама Windows не является операционной системой реального времени .Иногда случаются большие сбои в работе таких высокоприоритетных вещей, как драйверы устройств.

В Windows, если я пытаюсь вручную искать узкие места в коде, я использую RDTSC .Еще лучше было бы не делать это вручную, а использовать профилировщик.