В примере ACM мне пришлось создать большую таблицу для динамического программирования. Мне пришлось хранить два целых числа в каждой ячейке, поэтому я решил пойти на std::pair<int, int>. Однако выделение огромного массива из них заняло 1,5 секунды:
std::pair<int, int> table[1001][1001];
Впоследствии я изменил этот код на
struct Cell {
int first;
int second;
}
Cell table[1001][1001];
а выделение заняло 0 секунд.
Чем объясняется эта огромная разница во времени?
std::pair<int, int>::pair() инициализирует поля со значениями по умолчанию (ноль в случае int), а ваш struct Cell не работает (поскольку у вас есть только созданный автоматически конструктор по умолчанию, который ничего не делает).
Инициализация требует записи в каждое поле, которое требует большого количества обращений к памяти, которые относительно трудоемки. С помощью struct Cell ничего не делается, и ничего не делается немного быстрее.
Ответы до сих пор не объясняют полную величину проблемы.
Как указал sharptooth, парное решение инициализирует значения до нуля. Как отметил Лемурик, решение пары не просто инициализирует непрерывный блок памяти, а вызывает вызов конструктора пар для каждого элемента таблицы. Однако даже это не учитывает его, занимая 1,5 секунды. Что-то еще происходит.
Здесь моя логика:
Предполагая, что вы находились на старинной машине, скажем, бег на 1.33ghz, тогда 1,5 секунды - 2e9 тактов. У вас есть 2e6 пары для построения, так что каждый конструктор каждой пары принимает 1000 циклов. Не требуется 1000 циклов, чтобы вызвать конструктор, который просто устанавливает два целых числа в ноль. Я не вижу, как промахи прошивки будут затягиваться так долго. Я бы поверила, если число было меньше 100 циклов.
Я подумал, что было бы интересно посмотреть, куда еще идут все эти циклы процессора. Я использовал самый старый самый компилятор С++, который я смог найти, чтобы узнать, могу ли я достичь уровня потери. Этот компилятор был VС++ v6. В режиме отладки он делает то, что я не понимаю. Он имеет большой цикл, который вызывает конструктор пары для каждого элемента таблицы - достаточно справедливо. Этот конструктор устанавливает два значения в нуль - достаточно справедливо. Но перед этим он устанавливает все байты в 68-байтовой области до 0xcc. Этот регион находится непосредственно перед началом большого стола. Затем он перезаписывает последний элемент этого региона 0x28F61200. Каждый вызов конструктора пары повторяет это. Предположительно, это какой-то бухгалтерский учет компилятором, поэтому он знает, какие регионы инициализируются при проверке ошибок указателя во время выполнения. Я хотел бы точно знать, для чего это нужно.
В любом случае, это объясняет, куда идет дополнительное время. Очевидно, что другой компилятор, возможно, не так уж плох. И, конечно, оптимизированная версия релиза не будет.
Я предполагаю, что создается std:: pair. При вызове конструктора пары в 1001x1001 раз больше накладных расходов, чем при распределении диапазона памяти.
Все это очень хорошие догадки, но, как известно, догадки ненадежны.
Я бы сказал случайным образом приостановить его за 1,5 секунды, но вам нужно быть довольно быстрым. Если вы увеличили каждое измерение примерно в 3 раза, вы могли бы сделать его более похожим на 10 + секунды, поэтому было бы легче сделать паузу.
Или вы можете получить его под отладчиком, разбить его в коде конструктора пары, а затем сделать один шаг, чтобы увидеть, что он делает.
В любом случае, вы получите твердый ответ на вопрос, а не только предположение.
Это действительно хороший пример того, как следует писать С++ и тщательно использовать STL. любые мысли?
В моем проекте работает тестовый инструмент тестирования уровня кода C & С++, в котором мы будем делать много примеров кода, чтобы узнать, что такое "хороший" код и что такое "плохая" кодировка. см. http://effodevel.googlecode.com, чтобы узнать больше о C9B.M. планирование. если вы испытали много таких случаев, пожалуйста, любезно присоединитесь к проекту, чтобы помочь нам.