Конкатенация строк

Довыделение памяти реаллоком у тебя конечно же не приводит к повторному двойному пробегу.

А ты удваивай память, тогда число реаллоков будет расти как log₂, т.е. ОЧЕНЬ медленно.

#include <stdlib.h>
#include <stdio.h>

int
main(int argc, char *argv[])
{
    size_t size = 1, psize = 1, totalmoved = 0;
    void *p = NULL;
    void *q;

    // продырявим кучу
    void *m[2000] = { 0 };
    for (int i = 0; i < 2000; i++)
        m[i] = malloc(rand() % 500);
    for (int i = 0; i < 2000; i++)
        if (rand() % 2) free(m[i]);

    for (int i = 0; i < 200; i++) {
        if (size + 22 >= psize) {
            q = realloc(p, psize *= 2);
            if (p != q) {
                printf("%d %u: moved!\n", i, (unsigned)size);
                totalmoved += size;
                p = q;
            }
        }
        size += 22;
    }
    printf("total moved: %u\n", (unsigned)totalmoved);
    printf("total bytes: %d\n", 200 * 22);
    return 0;
}

0 1: moved!
4 89: moved!
5 111: moved!
6 133: moved!
7 155: moved!
11 243: moved!
23 507: moved!
46 1013: moved!
93 2047: moved!
186 4093: moved!
total moved: 8392
total bytes: 4400

Убедительно?

И не забываем скрытые затраты на поиск нового места.

если задача произвольное число с-строк заданое == как аргумент main слить в одну . то я бы наверно печатал бы в выходной_файл(буферный-самоудаляемый после закрытия :) ) а затем выпечатывал бы файл в строку.

т.е решение с допечаткой строк через sprintf - вполне.

Убедительно?

IRL строчки короче 50 байт, т.ч. реаллок вообще не нужен. Если в твоей задаче много больших строк, то просто выделяй сразу побольше байт. Обычно IRL 95% строк вообще не требуют реаллока, а из оставшихся 5% требуют одного. Т.ч. не убедил.

Убедишь, если покажешь задачу, с каким-то хитрым распределением длин строк, но я даже не представляю, каким оно должно быть.

И не забываем скрытые затраты на поиск нового места.

в смысле?

Мы же не будем разводить тут детсад и придумывать какие-то странные примеры, чтобы потом на них строить странные метафоры? IRL бывает и строка, и абзац, и война и мир. Естественно, зная, что максимальный предел сравнительно небольшой, стоит выделить псевдостатический буфер. Я лишь показал, что независимо от размера дырок в куче ты имеешь немалые шансы попасть на пару реаллоков вместо одного, и что рандомно-статистически это дороже, чем сразу посчитать длину. И все это на фоне рандомной производительности. Скрытые затраты реаллока вообще неочевидны без знания деталей реализации стандартной библиотеки.

нафига тут вообще памятью и её микро-менеджерством обмазываться?

Я и говорю — посчитай, выдели раз, скопируй. Кому неинтересно, проходите к следующему треду, товарищи, не задерживайте культурное общение.

зачем считать вообще считать - «операционнка» под капотом нужные стратегии держит.

челу нужно сливать строки - строки сливаются.

замапить файлы и недумай про малоки лично.

Вообще речь о том, что посчитал-выделил это все равно O(n), зачем при этом обмазываться всякими O(n*log2(random()) — непонятно. Да ну вас.

конечно при подсчёте сохраняется O(n) константа в два раза из за на проход больше чем читаем-пишем , и зачем самому выделять? если операционка для этого в том числе и написана.

Я лишь показал, что независимо от размера дырок в куче ты имеешь немалые шансы попасть на пару реаллоков вместо одного, и что рандомно-статистически это дороже, чем сразу посчитать длину.

проблема в том, что IRL длинна может измениться. Т.е. ты выделил 3+10+4 байта, но тут ВНЕЗАПНО надо ещё 7. Можно сразу выделить 32(2⁵) байта, а не 17, да и вообще всегда выделять 2^N памяти, а если её недостаточно - удваивать. Эта стратегия иногда лучше(а иногда хуже), чем выделять точно столько, сколько нужно.

Вообще речь о том, что посчитал-выделил это все равно O(n), зачем при этом обмазываться всякими O(n*log2(random()) — непонятно.

можно сделать функцию append, которая работает как strcat, только ещё и выделяет память (или делает realloc). Но если делать realloc скажем на 1 байт, то это очень долго.

IRL длинна может измениться. Т.е. ты выделил 3+10+4 байта, но тут ВНЕЗАПНО надо ещё 7
Эта стратегия иногда лучше(а иногда хуже), чем выделять точно столько, сколько нужно.

Да, такое сплошь и рядом. То malloc() меньше чем нужно выделит, то strcpy() больше скопирует, чем strlen() вернул. Настало время увлекательных историй от доктора?

То malloc() меньше чем нужно выделит, то strcpy() больше скопирует, чем strlen() вернул. Настало время увлекательных историй от доктора?

нет. просто анонимус опять нажрался.

Что, если ты склеил 10 строчек, то приклейка к ним одиннадцатой - невозможное событие? Если прочитал из файла /dev/stdin 123 байта, то 124й уже никогда не прочитаешь?

Все события в твоей реальности допускают применения strlen(), и после этого никогда не растут?

Внутри одной моей фнукции — только по царскому велению, т.е. по моему хотению.

Зачем делать в два этапа (10, потом 11-я), если можно сделать в один? Если буферизация естественный процесс, данные надо оставлять в разобранном виде, пока не станет видна граница пакета, и только потом собирать, оставив хвост следующему пакету.

Зачем делать в два этапа (10, потом 11-я), если можно сделать в один?

потому-что очень часто нельзя сделать в один, а нужно в два и более. Простой пример - чтение строки из файла. Вот не знаешь ты, когда тебе встретится \n.

Если буферизация естественный процесс, данные надо оставлять в разобранном виде, пока не станет видна граница пакета, и только потом собирать, оставив хвост следующему пакету.

т.е. ты предлагаешь наделать Over9000 кусков скажем по 50 байт, а потом сливать их в один? Вариант возможный, но я не думаю, что он экономичнее 7..8 realloc'ов. (50*2⁸ == 12800)