Рассмотрим следующие два случая инициализации массива в C или C++:Какова временная сложность инициализации массива?
Case 1:
int array[10000] = {0}; // All values = 0
Случай 2:
int array[10000];
for (int i = 0; i < 10000; i++) {
array[i] = 0;
}
ли они оба принимают то же самое время? Какова сложность случая 1? и, какой из них лучше?
В случае массив является статической продолжительности (глобальная переменная), я бы сказал, что первая из них предпочтительнее, так как она не требует никакого кода - она инициализируется средой выполнения.
Если переменная является автоматической продолжительностью (локальная переменная), какая из них лучше, если она лучше другой, зависит от компилятора. Скорее всего, оба будут очень похожи.
Совокупность переменной продолжительности хранения для хранения - O (n) для всех случаев. Первый случай - O (1) для переменной статической продолжительности хранения.
Конечно, если вы хотите заполнить массив значением 5, второй вариант намного лучше, потому что он не требует записи 10000 5 в исходный файл.
Вы также можете обнаружить, что использование memset(array, 0, sizeof(array)); лучше, чем оба - снова, в зависимости от компилятора. Это все еще O (n), но фактическое время, необходимое для заполнения массива, может быть короче, потому что memset может быть лучше оптимизирован, чем то, что генерирует компилятор для вашего случая цикла [и что он делает для инициализированных переменных]. memset не будет работать для заполнения массива 5.
Вы также можете использовать std::fill(array, &array[10000], 5);, чтобы установить значение 5 во всем массиве, и компилятор должен выполнить достойную работу по его оптимизации.
Наконец, я должен указать, что подобные вещи ДЕЙСТВИТЕЛЬНО имеют значение, если они делают в коде, который выполняется много. С тех пор, как заполнение 40 Кбайт данных прошло достаточно долго, чтобы действительно беспокоиться о себе. Как 20+ лет.
Хотя 'memset' не может обрабатывать параметр' 5', 'std :: fill' может сделать это красиво и по-прежнему можно оптимизировать, когда это необходимо компилятору. –
Хорошая точка .... Править. –
Развертка Loop может быть более эффективной, чем 'memcpy' или' std :: fill'. Идея разворачивания цикла состоит в том, чтобы выполнить столько операций присваивания, пока ветка не вернется к вершине цикла. Филиалы могут вызывать перезагрузку конвейера команд. –
Теоретически, обе имеют одинаковую сложность времени: O(N), где N - размер вашего массива.
Однако первый способ должен быть лучше, так как именно компилятор должен выбрать способ инициализации как можно быстрее (например, это можно сделать через memset). Для оптимизации компилятор очень часто лучше программиста.
BTW, если массив имеет статическую продолжительность хранения (если вы объявляете его в качестве глобальной переменной, например), то он будет автоматически инициализируется 0.
Является ли «массив» статической или автоматической продолжительности? –
Я искал обе ситуации. –