Итерация C массива char размером 100000 занимает огромное время - PullRequest
Новая
       72

Итерация C массива char размером 100000 занимает огромное время

0 голосов
/ 10 апреля 2020

Просто попробуйте выполнить итерацию массива символов размером 100000, но это займет 8-9 c. Но для int это занимает несколько миллисекунд. 

    int i;
    char str[100005];
    str[0] = '\0';
    for(i=1;i<10000;i++){
        strcat(str, "HelloWorld");
    }
    for(i=1;i<strlen(str);i++){
        str[i]=str[i-1];
    }

Ответы [ 2 ]

3 голосов
/ 10 апреля 2020

Давайте посмотрим на этот код: 

for(i = 1; i < 10000; i++){
    strcat(str, "HelloWorld");
}

Подумайте, как работает этот вызов strcat. Функция strcat работает, просматривая строку вперед, пока не найдет нулевой символ-терминатор, а затем записывает второй аргумент. Это довольно быстро, если ваша строка довольно короткая - скажем, длиной около 10-20 символов - но если строка, к которой вы добавляете, длинна (скажем, 10000 символов), то strcat потратит много времени на простое сканирование до конца строки, чтобы найти место, в котором можно добавить строку. Это означает, что каждый вызов strcat в этой функции займет больше времени, чем предыдущий, и в конечном итоге последний вызов будет довольно медленным.

Так как же вы можете ускорить это? Один из вариантов - сохранить указатель на нулевой терминатор в массиве str, чтобы вы могли указать strcat, с чего начать поиск. Вот как это может выглядеть: 

size_t length = strlen("HelloWorld");
char* nextSpot = str;
for(i = 1; i < 10000; i++){
    strcat(nextSpot, "HelloWorld");
    nextSpot += length;
}

Это означает, что вызов strcat всегда будет начинаться с того места, где остановился последний, ускоряя процесс.

Надеюсь, это поможет!

2 голосов
/ 10 апреля 2020

Есть некоторые проблемы с вашим кодом. Во-первых, вы вызываете strcat для целевого массива, который не был инициализирован. Сначала нужно установить str[0] = '\0';.

Другие проблемы - алгоритми c. Чтобы знать, куда вставить целевую строку, strcat должен делать strlen или эквивалентный каждый раз, когда вы вызываете ее. Это означает, что он каждый раз перебирает O(n) символов. Это делает ваш алгоритм ~O(n^2). Затем вы go и снова вызываете strlen для каждого персонажа, с тем же штрафом. И имейте в виду, что второй l oop просто устанавливает для всего массива значение 'H'.

Если вы хотите скопировать строку 10000 раз, вам лучше предварительно вычислить ее длину и просто шагая вдоль буфера: 

char str[100005];
const char *template = "HelloWorld";
int n = strlen(template);
char *p = str;
for(int i = 0; i < 10000; i++) {
    strncpy(p, template, n);
    p += n;
}
*p = '\0';

Я использую strncpy здесь, потому что он позволяет избежать копирования завершающего '\0' из template для каждой копии, которую вы делаете.

Альтернативный подход было бы использовать деление по модулю (что, вероятно, было бы медленнее) для размещения символов: 

char str[100005];
const char *template = "HelloWorld";
int n = strlen(template);
int end = n * 10000;
for(int i = i; i < end; i++) {
    str[i] = template[i % n];
}

Оба подхода занимают на мою машину на пару порядков меньше времени, чем ваш исходный l oop, потому что они проходят через массив ровно один раз.

Последний l oop копирует предыдущий символ снова и снова в оставшуюся часть буфера. Поскольку ваш буфер заполнен HelloWorld, l oop копирует 'H' в каждое место. Вы можете использовать memset, чтобы сделать то же самое для вас: 

memset(str, 'H', 10000 * n);

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

...