Преимущество вычисления map.end() вне цикла

Недавно я натолкнулся на следующий код.Преимущество вычисления map.end() вне цикла

std::map<int, int> m; 

// insert into the map 

std::map<int, int>::iterator endOfMap = m.end(); 
for(std::map<int, int>::iterator itr = m.begin(); itr != endOfMap; ++itr) { 

}

Есть ли какое-либо преимущество в вычислении endOfMap заранее на нижнем уровне?

for(std::map<int, int>::iterator itr = m.begin(); itr != m.end(); ++itr)

Примечание:
код я увидел отображение строки для пользовательского объекта, с миллионами элементов.

источник

2017-01-30 Thirupathi Thangavel

Ну, они, вероятно, будут так близки к скорости вычислений, но давайте возьмем первый пример, первый из которых уже вычисляет вызов функции и делает все, что ему нужно, до endOfMap. 2-й пример в условии завершения, он будет вызывать функцию m.end() несколько раз, а затем проверить, являются ли они равными или нет. Вместо того, чтобы просто проверить, не равны ли они и не вызывать функцию несколько раз. –

Вы говорите об O (конец()) + O (проверка равенства) по сравнению с O (проверка равенства) в итерациях цикла for. –

Снижение производительности при распределении памяти данных карты перевешивает любое улучшение от вызывающего конца() вне цикла! – user997112

Поскольку вы не знаете реализации map, вы можете предположить, что выполнение задания перед циклом сохраняет накладные расходы при вызове end() каждый раз через цикл.

Но насколько это накладные расходы? Мы уже знаем, что end() неявно встроен, поскольку это функция шаблона; если код достаточно прост, компилятор с большой вероятностью удалит служебные данные вызова функции. Стандарт C++ гарантирует, что end() является функцией O (1), что означает, что она, вероятно, не слишком сложна. Если end() просто возвращает член объекта без каких-либо других вычислений, не может быть абсолютно никакой экономии для копирования его на локальную переменную!

С другой стороны, это яркий пример оптимизации, которая не стоит вам ничего. Если у вас есть привычка делать это за каждый цикл for, который вы пишете, это не повредит и один раз в большой момент, когда это может помочь. Я даже видел назначение, сделанное в первом сегменте цикла for, а не на отдельной строке.

источник

2017-01-30 03:38:03

Спасибо :). Из комментария @ Alejandro ниже, я думаю, что компилятор все равно оптимизирует это? –

Но все ли функции шаблона встроены? –

@ThirupathiThangavel Да, они есть, потому что они определены в объявлении класса. Вы заметите, что весь код для функции шаблона является частью файла заголовка; если есть какие-либо функции, которые находятся в файле .cpp, они должны быть в базовом классе. –

Есть ли какое-либо преимущество в вычислении endOfMap заранее ниже?

Единственное преимущество, , что я могу видеть, будет снижена стоимость вызова std::map::end() в каждой итерации цикла. Разница, скорее всего, будет очень маленькой. Вы можете узнать это только путем повторения по map, в котором есть ОГРОМНОЕ количество элементов. Несмотря на то, что стоимость звонка std::map::end() гарантируется стандартом O(1), призывая его миллионы раз, вы можете добавить заметную стоимость функции/программе.

источник

2017-01-30 02:48:44

@songyuanyao это не всегда O (n) постоянное время. В базовой реализации может быть указатель, который постоянно отслеживает последний элемент. Если вы не знаете, что он не отслеживает это и просто ждет до конца и проходит. –

@RSahu Хорошо, я неправильно понял вашу точку зрения. – songyuanyao

@OmidCompSCI Я имел в виду 'std :: map :: end()' всегда стоит постоянное время; это требуется стандартом. – songyuanyao

Это экономит вызов функции на каждой итерации, но учитывая, что map.end() довольно легкий метод, вы не увидите разницы, если вы не вызываете эту функцию миллион раз в секунду.

источник

2017-01-30 02:51:17

Преимущество вычисления map.end() вне цикла

ответ

Смежные вопросы