Какова оптимальная начальная емкость StringBuffer для входов с резко изменяющимися длинами?

Question

Добрый день всем, я использую java.lang.StringBuilder для хранения некоторых символов. Я понятия не имею, сколько символов я собираюсь хранить заранее, за исключением того, что:

1. 60% времени, это только (точно) 7 символов
2. 39% времени, это (примерно) 3500 символов
3. 1% времени, это примерно 20 000 символов

Как нам рассчитать оптимальную начальную длину буфера, которую следует использовать?

_{В настоящее время я использую new java.lang.StringBuilder(4000), но это только потому, что я был слишком ленив, чтобы думать раньше.}

Answer 1

Здесь есть два фактора: время и потребление памяти. Время в основном зависит от количества вызовов java.lang.AbstractStringBuilder.expandCapacity(). Конечно, стоимость каждого вызова является линейной по отношению к текущему размеру буфера, но я упрощаю здесь и просто подсчитываю их:

Количество expandCapacity() (время)

Конфигурация по умолчанию (16 символов)

• В 60% случаев StringBuilder увеличится в 0 раз
• В 39% случаев StringBuilder увеличится в 8 раз
• В 1% случаев StringBuilder увеличится в 11 раз

Ожидаемое число expandCapacity составляет 3,23.

Начальная емкость 4096 символов

• В 99% случаев StringBuilder увеличится в 0 раз
• В 1% случаев StringBuilder увеличится в 3 раза

Ожидаемое число expandCapacity составляет 0,03.

Как вы можете видеть, второй сценарий выглядит намного быстрее, поскольку очень редко приходится расширять StringBuilder (три раза на каждые 100 входов). Однако обратите внимание, что первые расширения менее значительны (копирование небольшого объема памяти); также, если вы добавляете строки в конструктор большими порциями, он будет расширяться быстрее за меньшее количество итераций.

С другой стороны, увеличивается потребление памяти:

Потребление памяти

Конфигурация по умолчанию (16 символов)

• В 60% случаев StringBuilder будет занимать 16 символов
• В 39% случаев StringBuilder будет занимать 4K символов
• В 1% случаев StringBuilder будет занимать 32K символов

Ожидаемое среднее потребление памяти: 1935 символов.

Начальная емкость 4096 символов

• В 99% случаев StringBuilder будет занимать 4K символов
• В 1% случаев StringBuilder будет занимать 32K символов

Ожидаемое среднее потребление памяти: 4383 символов.

---

TL; DR

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

Суть: попробуйте! Нетрудно написать тест, который будет обрабатывать миллионы строк различной длины с разной начальной емкостью. Но я считаю, что больший буфер может быть хорошим выбором.