Сколько нужно увеличить буфер в модуле C, подобном StringBuilder?

Ответ 1

В С# стратегия, используемая для расширения внутреннего буфера, используемого StringBuilder, со временем изменилась.

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

Первая основная стратегия:

• Сделать массив символов
• Когда вы исчерпаете комнату, создайте новый массив с числом символов больше k, для некоторой константы k.
• Скопируйте старый массив в новый массив и заставьте старый массив.

В этой стратегии есть ряд проблем, наиболее очевидным из которых является то, что это O (n ²) во времени, если построенная строка чрезвычайно велика. Скажем, что k - тысяча символов, а окончательная строка - миллион символов. В итоге вы перераспределяете строку на 1000, 2000, 3000, 4000,... и, следовательно, копируете 1000 + 2000 + 3000 + 4000 +... + 999000 символов, сумма которых составляет порядка 500 миллиардов символов, скопированных!

Эта стратегия имеет приятное свойство, что количество "потерянной" памяти ограничено k.

На практике эта стратегия редко используется из-за этой n-квадратной проблемы.

Вторая основная стратегия -

• Сделать массив
• Когда вы закончите работу, создайте новый массив с k% более символов, для некоторой константы k.
• Скопируйте старый массив в новый массив и заставьте старый массив.

k% обычно составляет 100%; если это тогда, то это называется стратегией "double when full".

Эта стратегия обладает хорошим свойством, что ее амортизированная стоимость равна O (n). Предположим, что окончательная строка - миллион символов, и вы начинаете с тысячи. Вы делаете копии на 1000, 2000, 4000, 8000,... и копируете 1000 + 2000 + 4000 + 8000... + 512000 символов, сумма которых составляет около миллиона символов; намного лучше.

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

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

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

Эта стратегия обладает хорошим свойством, что никакая операция не является особенно дорогостоящей, общая потерянная память ограничена k, и вам не нужно будет регулярно размещать большие блоки в куче. У этого есть недостаток, который, наконец, превращает вещь в строку, может быть дорогим, поскольку массивы в связанном списке могут иметь плохую локальность.

Строковый построитель в .NET-инфраструктуре использовал для использования стратегии double-when-full; теперь он использует стратегию связанных списков блоков.

Ответ 2

Вы обычно хотите, чтобы фактор роста немного меньше, чем золотое среднее (~ 1.6). Когда он меньше золотого, отброшенные сегменты будут достаточно большими, чтобы удовлетворить более поздний запрос, если они смежны друг с другом. Если ваш фактор роста больше золотого среднего, этого не может быть.

Я обнаружил, что уменьшение коэффициента до 1,5 по-прежнему работает довольно хорошо и имеет то преимущество, что его легко реализовать в целочисленной математике (size = (size + (size << 1))>>1;), с достойным компилятором вы можете записать это как (size * 3)/2 и он все равно должен скомпилировать быстрый код).

Кажется, я несколько раз вспоминал разговор о Usenet, в котором PJ Plauger (или, возможно, это был Пит Беккер) из Dinkumware, заявив, что они проведут более обширные тесты, чем я когда-либо, и пришли к такому же выводу ( поэтому, например, реализация std::vector в их стандартной библиотеке С++ использует 1.5).

Ответ 3

При работе с расширяющимися и сжимающими буферами ключевое свойство, которое вы хотите, состоит в том, чтобы расти или сокращаться на несколько раз, а не постоянную разницу.

Рассмотрим случай, когда у вас есть 16-байтовый массив, увеличивая его размер на 128 байт, это избыток; однако, если вместо этого у вас был массив байтов 4096 и он увеличился всего на 128 байт, вы в конечном итоге много копировали.

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

Ответ 4

Кто-нибудь знает, что делает Java или С# под капотом?

Посмотрите следующую ссылку, чтобы узнать, как это делается в Java StringBuilder из JDK7, в частности, метод expandCapacity. http://hg.openjdk.java.net/build-infra/jdk7/jdk/file/0f8da27a3ea3/src/share/classes/java/lang/AbstractStringBuilder.java

Ответ 5

Это конкретная реализация, согласно документации, но начинается с 16:

По умолчанию для этой реализации используется значение 16, а значение по умолчанию максимальная емкость - Int32.MaxValue.

Объект StringBuilder может выделять больше памяти для хранения символов когда значение экземпляра увеличивается, а емкость - соответственно. Например, Append, AppendFormat, Методы EnsureCapacity, Insert и Replace могут увеличить значение экземпляр.

Объем выделенной памяти зависит от реализации и исключение (исключение ArgumentOutOfRangeException или OutOfMemoryException) если количество требуемой памяти больше максимального емкость.

Основываясь на некоторых других объектах .NET framework, я бы предложил умножить их на 1.1 каждый раз, когда будет достигнута текущая емкость. Если требуется дополнительное пространство, просто эквивалент EnsureCapacity, который будет вручную расширять его до необходимого размера.

Ответ 6

Перевести это на C.

Я, вероятно, буду mainain a List<List<string>>.

class StringBuilder
{
   private List<List<string>> list;

   public Append(List<string> listOfCharsToAppend)
   {

       list.Add(listOfCharsToAppend);
   }

}

Таким образом, вы просто сохраняете список списков и выделяете память по требованию, а не выделяете память вперед.

Ответ 7

Список в .NET Framework использует этот алгоритм: если указана начальная емкость, он создает буфер такого размера, иначе буфер не будет выделен до тех пор, пока не будет добавлен первый элемент (ы), который выделяет пространство, равное количеству элементов (ов) добавлено, но не менее 4. Когда требуется больше места, он выделяет новый буфер с 2x прежней емкостью и копирует все элементы из старого буфера в новый буфер. Ранее StringBuilder использовал аналогичный алгоритм.

В .NET 4 StringBuilder выделяет начальный буфер размера, указанного в конструкторе (размер по умолчанию - 16 символов). Когда выделенный буфер слишком мал, копирование не производится. Вместо этого он заполняет текущий буфер для обода, а затем создает новый экземпляр StringBuilder, который выделяет буфер размером * MAX (length_of_remaining_data_to_add, MIN (length_of_all_previous_buffers, 8000)) *, поэтому по крайней мере все остальные данные подходят для нового буфера и общего размера всех буферов по крайней мере, удваивается. Новый StringBuilder сохраняет ссылку на старый StringBuilder, и поэтому отдельные экземпляры создают связанный список буферов.