Эффективный по времени и памяти способ выделить память для строки

Question

Я читаю файл в память на C, копируя байты в динамический массив.В настоящее время я выполняю realloc () на один байт каждый раз, когда поступает новый байт. Это кажется неэффективным.

Некоторые полагают (я не могу вспомнить, где), что удвоение памяти каждый раз, когда требуется больше, хорошо, потому что этоO (log n) время выделения, с единственной потерей в худшем случае, когда не используется почти половина памяти.

Какие-либо рекомендации по распределению памяти?

Answer 1

Если вы загружаете весь файл в строку, вы, вероятно, можете использовать метод, описанный в этом вопросе .Таким образом, вы можете получить размер файла в байтах и ​​выделить свою строку для его хранения (не забудьте дополнительный байт для нулевого символа).

Однако, если вы динамически увеличиваете строку, лучше увеличить ее размер на некоторый коэффициент, превышающий один байт (перераспределение строки для каждого байта будет очень медленным, особенно если строка должнабыть выделены в новой области памяти, а затем скопированы).Поскольку вы читаете удвоение файла, это, вероятно, очень разумно.Я видел, как люди используют и другие методы, например:

1. Я видел, как люди округляются до следующей степени 2, например, 2, 4, 8,затем 16 байтов.(который, по сути, удваивает размер файла каждый раз).

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

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

Answer 2

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

Answer 3

Я не имею в виду этого, и это, вероятно, деталь, специфичная для реализации, но я считаю, что указатели с изменяемым размером 2 - это то, что используется для изменения размера C ++ STL string. объекты, как символы постоянно добавляются. (Это должно быть легко проверить, вызвав метод string::capacity при добавлении символов.)