Как написать String Builder?

Реализация StringBuilder в Go

Концепция и необходимость

В Go строка (string) является неизменяемым (immutable) типом данных. Это означает, что каждая операция конкатенации (сложения строк) с помощью оператора + создает новую строку в памяти, копируя содержимое исходных строк. Для небольших операций это не критично, но при интенсивной конкатенации в циклах это приводит к квадратичной сложности O(n²) и значительным накладным расходам на аллокацию памяти и копирование данных.

StringBuilder — это оптимизированная структура для построения строк с линейной сложностью O(n). Основная идея:

• Использовать срез байт ([]byte) как изменяемый буфер
• Накопить все данные в буфере
• Преобразовать результат в строку одним преобразованием

Базовая реализация

package main

import (
    "fmt"
    "strings"
)

// StringBuilder - простая реализация построителя строк
type StringBuilder struct {
    buffer []byte
}

// NewStringBuilder создает новый StringBuilder с начальной емкостью
func NewStringBuilder(initialCapacity int) *StringBuilder {
    return &StringBuilder{
        buffer: make([]byte, 0, initialCapacity),
    }
}

// Write добавляет строку в буфер
func (sb *StringBuilder) Write(s string) *StringBuilder {
    sb.buffer = append(sb.buffer, s...)
    return sb
}

// WriteByte добавляет байт в буфер
func (sb *StringBuilder) WriteByte(b byte) *StringBuilder {
    sb.buffer = append(sb.buffer, b)
    return sb
}

// WriteRune добавляет руну (Unicode символ) в буфер
func (sb *StringBuilder) WriteRune(r rune) *StringBuilder {
    sb.buffer = append(sb.buffer, string(r)...)
    return sb
}

// String возвращает собранную строку
func (sb *StringBuilder) String() string {
    return string(sb.buffer)
}

// Len возвращает текущую длину буфера
func (sb *StringBuilder) Len() int {
    return len(sb.buffer)
}

// Cap возвращает емкость буфера
func (sb *StringBuilder) Cap() int {
    return cap(sb.buffer)
}

// Reset очищает буфер
func (sb *StringBuilder) Reset() {
    sb.buffer = sb.buffer[:0]
}

func main() {
    // Использование собственной реализации
    sb := NewStringBuilder(100)
    sb.Write("Hello, ").
        Write("World!").
        WriteByte(' ').
        WriteRune('🎉')
    
    result := sb.String()
    fmt.Println(result) // Hello, World! 🎉
    fmt.Printf("Length: %d, Capacity: %d\n", sb.Len(), sb.Cap())
}

Продвинутая оптимизированная реализация

package main

import (
    "io"
    "unsafe"
)

// OptimizedStringBuilder - оптимизированная версия с поддержкой io.Writer
type OptimizedStringBuilder struct {
    buffer []byte
}

// NewOptimizedStringBuilder создает оптимизированный StringBuilder
func NewOptimizedStringBuilder() *OptimizedStringBuilder {
    return &OptimizedStringBuilder{}
}

// Grow увеличивает емкость буфера минимум до n байт
func (osb *OptimizedStringBuilder) Grow(n int) {
    if n > cap(osb.buffer)-len(osb.buffer) {
        newBuffer := make([]byte, len(osb.buffer), 2*cap(osb.buffer)+n)
        copy(newBuffer, osb.buffer)
        osb.buffer = newBuffer
    }
}

// Write реализует io.Writer интерфейс
func (osb *OptimizedStringBuilder) Write(p []byte) (int, error) {
    osb.buffer = append(osb.buffer, p...)
    return len(p), nil
}

// WriteString оптимизированная запись строки (без лишних преобразований)
func (osb *OptimizedStringBuilder) WriteString(s string) (int, error) {
    osb.buffer = append(osb.buffer, s...)
    return len(s), nil
}

// String возвращает строку без копирования данных
func (osb *OptimizedStringBuilder) String() string {
    // Используем unsafe для избежания копирования
    return *(*string)(unsafe.Pointer(&osb.buffer))
}

// Bytes возвращает срез байт
func (osb *OptimizedStringBuilder) Bytes() []byte {
    b := make([]byte, len(osb.buffer))
    copy(b, osb.buffer)
    return b
}

// WriteStrings эффективно записывает несколько строк
func (osb *OptimizedStringBuilder) WriteStrings(strings ...string) {
    // Вычисляем общий размер для оптимального выделения памяти
    totalLen := 0
    for _, s := range strings {
        totalLen += len(s)
    }
    
    osb.Grow(totalLen)
    for _, s := range strings {
        osb.buffer = append(osb.buffer, s...)
    }
}

Использование встроенного strings.Builder

Go с версии 1.10 имеет встроенный strings.Builder в стандартной библиотеке, который рекомендуется использовать в production-коде:

package main

import (
    "fmt"
    "strings"
)

func main() {
    // Использование стандартного strings.Builder
    var builder strings.Builder
    
    // Резервируем память заранее для оптимизации
    builder.Grow(100)
    
    // Эффективная конкатенация
    builder.WriteString("Hello")
    builder.WriteString(", ")
    builder.WriteString("World!")
    builder.WriteByte('\n')
    
    // Поддержка fmt интерфейсов
    fmt.Fprintf(&builder, "Count: %d\n", 42)
    
    result := builder.String()
    fmt.Print(result)
    
    // Доступ к данным как к байтам
    bytes := builder.String() // Получаем строку
    _ = []byte(bytes)         // При необходимости конвертируем
}

Ключевые преимущества StringBuilder

1. Эффективность памяти: Минимизация аллокаций за счет предварительного резервирования (Grow())
2. Производительность: Линейная сложность O(n) вместо O(n²)
3. Гибкость: Поддержка интерфейсов io.Writer, io.ByteWriter
4. Безопасность: Корректная работа с Unicode (рунами)
5. Методы оптимизации:
   • Предварительное выделение емкости
   • Пакетная обработка строк
   • Избегание промежуточных преобразований

Практические рекомендации

// Шаблон использования
func buildString(elements []string) string {
    var sb strings.Builder
    sb.Grow(totalLength(elements)) // Важно: заранее оценить размер
    
    for _, elem := range elements {
        sb.WriteString(elem)
    }
    
    return sb.String()
}

// Опасность: НЕ используйте так (медленно!)
func slowBuild(elements []string) string {
    result := ""
    for _, elem := range elements { // Каждая итерация создает новую строку!
        result += elem
    }
    return result
}

Сравнение производительности

• Конкатенация через + в цикле: O(n²), много аллокаций
• strings.Join(): Оптимален для объединения с разделителем
• strings.Builder: Оптимален для постепенного построения
• bytes.Buffer: Аналогичен Builder, но возвращает []byte

Заключение

Реализация StringBuilder в Go демонстрирует важный принцип работы со строками: для эффективного построения строк из множества частей необходимо использовать буфер байт с последующим преобразованием в строку. В реальных проектах всегда используйте встроенный strings.Builder из стандартной библиотеки, так как он протестирован, оптимизирован и безопасен. Для особых случаев можно создать расширенную версию, добавляющую специфичную для приложения логику.