Как оптимизировать работу со строкой в цикле

Как оптимизировать работу со строкой в цикле

Это классический вопрос о производительности. Покажу почему String конкатенация в цикле медленная и как оптимизировать.

1. Проблема: неоптимизированная работа со строками в цикле

public class BadStringLoopExample {
    public static void main(String[] args) {
        // ❌ НЕПРАВИЛЬНО: String конкатенация в цикле
        long start = System.currentTimeMillis();
        
        String result = "";
        for (int i = 0; i < 10000; i++) {
            result += "Item " + i + ", ";  // Очень медленно!
        }
        
        long end = System.currentTimeMillis();
        System.out.println("Time: " + (end - start) + "ms");  // ~500-1000ms
    }
}

Почему это медленно?

String в Java immutable (неизменяемый). Каждая операция `result += ...` создаёт новый String объект:

Итерация 1: result = "" + "Item 0, "
            → создаётся новый String (length=7)
            → старый String удаляется (garbage collection)

Итерация 2: result = "Item 0, " + "Item 1, "
            → создаётся новый String (length=14)
            → старый String (length=7) удаляется

Итерация 3: result = "Item 0, Item 1, " + "Item 2, "
            → создаётся новый String (length=21)
            → старый String (length=14) удаляется
            
...

Итерация 10000: создаётся String длиной ~70000
                → всего 10000 объектов String создано и удалено!
                → очень медленно из-за GC и копирования памяти

Сложность: O(n²) — квадратичная!

Операция += заключает:
1. Копирование старой строки в новый буфер: O(n)
2. Добавление новых символов: O(m)
3. Удаление старого объекта: O(n)

Для цикла из n итераций:
  Итерация 1: O(1)
  Итерация 2: O(2)
  Итерация 3: O(3)
  ...
  Итерация n: O(n)
  
  Всего: O(1+2+3+...+n) = O(n²)

2. Решение 1: StringBuilder (РЕКОМЕНДУЕТСЯ)

StringBuilder — это mutable (изменяемый) буфер для эффективного построения строк:

public class GoodStringLoopExample {
    public static void main(String[] args) {
        // ✅ ПРАВИЛЬНО: StringBuilder в цикле
        long start = System.currentTimeMillis();
        
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            result.append("Item ").append(i).append(", ");
        }
        
        String finalResult = result.toString();
        
        long end = System.currentTimeMillis();
        System.out.println("Time: " + (end - start) + "ms");  // ~1-5ms (в 100-500 раз быстрее!)
    }
}

Как работает StringBuilder:

StringBuilder внутри имеет growable char array:

Capacity = 16 (начальный размер)
┌─────────────────────────────────────────┐
│ 'I' 't' 'e' 'm' ' ' '0' ',' ' ' _ _ _ _ │
└─────────────────────────────────────────┘
Length = 8

При append("Item 1, "):
  Длина станет 16, capacity хватает → просто добавляем
┌─────────────────────────────────────────┐
│ 'I' 't' 'e' 'm' ' ' '0' ',' ' ' 'I' 't' 'e' 'm' ' ' '1' ',' ' ' │
└─────────────────────────────────────────┘
Length = 16

При append("Item 2, ") (нужно 8 символов, capacity=16):
  Length станет 24, capacity недостаточно → растягиваем буфер
  capacity *= 2 → новый capacity = 32
┌──────────────────────────────────────────────────────────────────┐
│ 'I' 't' 'e' 'm' ' ' '0' ',' ' ' 'I' 't' 'e' 'm' ' ' '1' ',' ' ' 'I' 't' 'e' 'm' ' ' '2' ',' ' ' _ _ _ _ _ _ │
└──────────────────────────────────────────────────────────────────┘
Length = 24, Capacity = 32

Сложность: O(n) — линейная!

StringBuilder.append() в среднем O(1) амортизированная сложность
(копирование буфера происходит редко, только при увеличении capacity)

Для цикла из n итераций:
  Всего: O(n)

3. StringBuilder vs StringBuffer

public class StringBuilderVsBuffer {
    // StringBuilder — НЕ потокобезопасен (но быстрее)
    StringBuilder sb = new StringBuilder();
    
    // StringBuffer — потокобезопасен (все методы synchronized)
    StringBuffer sf = new StringBuffer();
}

Сравнение:

┌──────────────────┬────────────┬──────────┬──────────────┐
│ Класс            │ Потокобезо │ Скорость │ Использование│
├──────────────────┼────────────┼──────────┼──────────────┤
│ String           │ ДА         │ ~1ms     │ Readonly     │
│ StringBuilder     │ НЕТ        │ ~3ms     │ Single-thread│
│ StringBuffer      │ ДА         │ ~10ms    │ Multi-thread │
└──────────────────┴────────────┴──────────┴──────────────┘

Для цикла: ВСЕГДА используй StringBuilder (выполняется в одном потоке)

4. Практические примеры оптимизации

Пример 1: CSV построение

public class CsvBuilderExample {
    // ❌ НЕПРАВИЛЬНО
    public String buildCsvBad(List<String> items) {
        String csv = "";
        for (String item : items) {
            csv += item + ",";
        }
        return csv;
    }
    
    // ✅ ПРАВИЛЬНО: StringBuilder
    public String buildCsvGood(List<String> items) {
        StringBuilder csv = new StringBuilder();
        for (int i = 0; i < items.size(); i++) {
            csv.append(items.get(i));
            if (i < items.size() - 1) {
                csv.append(",");
            }
        }
        return csv.toString();
    }
    
    // ✅ ИЛИ с помощью String.join (Java 8+)
    public String buildCsvBest(List<String> items) {
        return String.join(",", items);
    }
}

Пример 2: SQL query построение

public class SqlQueryBuilder {
    // ❌ НЕПРАВИЛЬНО
    public String buildQueryBad(List<Long> ids) {
        String query = "SELECT * FROM users WHERE id IN (";
        for (int i = 0; i < ids.size(); i++) {
            query += ids.get(i);
            if (i < ids.size() - 1) {
                query += ",";
            }
        }
        query += ")";
        return query;
    }
    
    // ✅ ПРАВИЛЬНО: StringBuilder
    public String buildQueryGood(List<Long> ids) {
        StringBuilder query = new StringBuilder("SELECT * FROM users WHERE id IN (");
        for (int i = 0; i < ids.size(); i++) {
            query.append(ids.get(i));
            if (i < ids.size() - 1) {
                query.append(",");
            }
        }
        query.append(")");
        return query.toString();
    }
    
    // ✅ ИЛИ с помощью stream (Java 8+)
    public String buildQueryBest(List<Long> ids) {
        return "SELECT * FROM users WHERE id IN (" +
               ids.stream()
                  .map(String::valueOf)
                  .collect(java.util.stream.Collectors.joining(",")) +
               ")";
    }
}

Пример 3: JSON построение

public class JsonBuilder {
    // ❌ НЕПРАВИЛЬНО
    public String buildJsonBad(List<User> users) {
        String json = "[";
        for (int i = 0; i < users.size(); i++) {
            User user = users.get(i);
            json += "{\"id\":" + user.getId() + ",\"name\":\"" + user.getName() + "\"}";
            if (i < users.size() - 1) {
                json += ",";
            }
        }
        json += "]";
        return json;
    }
    
    // ✅ ПРАВИЛЬНО: StringBuilder
    public String buildJsonGood(List<User> users) {
        StringBuilder json = new StringBuilder("[");
        for (int i = 0; i < users.size(); i++) {
            User user = users.get(i);
            json.append("{\"id\":")
                .append(user.getId())
                .append(",\"name\":\"")
                .append(user.getName())
                .append("\"}");
            if (i < users.size() - 1) {
                json.append(",");
            }
        }
        json.append("]");
        return json.toString();
    }
    
    // ✅ ИЛИ используй JSON library (Jackson, Gson)
    public String buildJsonBest(List<User> users) {
        com.fasterxml.jackson.databind.ObjectMapper mapper = 
            new com.fasterxml.jackson.databind.ObjectMapper();
        return mapper.writeValueAsString(users);
    }
}

5. Инициализация StringBuilder с нужным capacity

public class StringBuilderCapacity {
    public static void main(String[] args) {
        // ❌ ПЛОХО: StringBuilder растёт несколько раз
        StringBuilder sb1 = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            sb1.append("Item ").append(i).append(", ");
        }
        // Рост буфера: 16 → 32 → 64 → 128 → 256 → 512 → 1024 → 2048 → 4096 → 8192 → 16384
        
        // ✅ ХОРОШО: указываем начальный capacity
        StringBuilder sb2 = new StringBuilder(100000);
        for (int i = 0; i < 10000; i++) {
            sb2.append("Item ").append(i).append(", ");
        }
        // Буфер не растёт → быстрее
        
        System.out.println("sb1 length: " + sb1.length());
        System.out.println("sb1 capacity: " + sb1.capacity());
        System.out.println("sb2 capacity: " + sb2.capacity());
    }
}

6. Есть ещё методы для специальных случаев

// Повторение строки
String repeated = "a".repeat(1000); // Java 11+

// Join для коллекций
String csv = String.join(",", "a", "b", "c"); // "a,b,c"

// Stream collectors
String result = items.stream()
    .map(Object::toString)
    .collect(java.util.stream.Collectors.joining(","));

// Formatting (только если нужна гибкость)
String formatted = String.format("%s, %d, %.2f", "Item", 10, 3.14);

7. Benchmark: сравнение производительности

public class StringPerformanceBenchmark {
    public static void main(String[] args) {
        int iterations = 10000;
        
        // Test 1: String конкатенация
        long start = System.nanoTime();
        String result1 = "";
        for (int i = 0; i < iterations; i++) {
            result1 += "Item " + i + ", ";
        }
        long time1 = System.nanoTime() - start;
        
        // Test 2: StringBuilder
        start = System.nanoTime();
        StringBuilder result2 = new StringBuilder();
        for (int i = 0; i < iterations; i++) {
            result2.append("Item ").append(i).append(", ");
        }
        long time2 = System.nanoTime() - start;
        
        // Test 3: StringBuilder с capacity
        start = System.nanoTime();
        StringBuilder result3 = new StringBuilder(100000);
        for (int i = 0; i < iterations; i++) {
            result3.append("Item ").append(i).append(", ");
        }
        long time3 = System.nanoTime() - start;
        
        System.out.println("String concatenation: " + (time1 / 1_000_000) + "ms");
        System.out.println("StringBuilder: " + (time2 / 1_000_000) + "ms");
        System.out.println("StringBuilder with capacity: " + (time3 / 1_000_000) + "ms");
        System.out.println("Speedup (1 vs 2): " + (double) time1 / time2 + "x");
        System.out.println("Speedup (1 vs 3): " + (double) time1 / time3 + "x");
    }
}

// Типичный вывод:
// String concatenation: 850ms
// StringBuilder: 2ms
// StringBuilder with capacity: 1ms
// Speedup (1 vs 2): 425x
// Speedup (1 vs 3): 850x

Best Practices

// ✅ ПРАВИЛЬНО
1. StringBuilder для построения строк в цикле
2. String.join() для простых случаев (Java 8+)
3. Инициализируй capacity если знаешь размер
4. Используй append() вместо конкатенации
5. Вызови toString() один раз в конце

// ❌ НЕПРАВИЛЬНО
1. String += в цикле (квадратичная сложность)
2. StringBuffer в single-thread коде (медленнее)
3. Не инициализируй capacity → дополнительные копирования
4. Не используй String.format() в тайтных циклах

Вывод

Для оптимизации работы со строками в цикле:

1. Никогда не используй String конкатенацию (+=) в цикле → O(n²) сложность
2. Всегда используй StringBuilder → O(n) сложность
3. Инициализируй capacity если знаешь примерный размер
4. Вызови toString() один раз в конце

Это даёт ускорение в 100-1000 раз для больших объёмов данных.