Как оптимизировать программу в которой заполняется миллиард объектов в коллекцию и потом сортируются

«Как оптимизировать программу в которой заполняется миллиард объектов в коллекцию и потом сортируются» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Используйте ArrayList для хранения, т.к. он обеспечивает быстрый доступ и эффективное заполнение. Для сортировки примените Collections.sort() или List.sort(), которые используют TimSort (гибридный алгоритм с O(n log n)).

Оптимизации:

  1. Предварительный размер:
List<Item> list = new ArrayList<>(1_000_000_000); // избегаем реаллокаций
  1. Примитивы: Если возможно, используйте Trove или Eclipse Collections для примитивов.
  2. Параллельная сортировка:
list.parallelStream().sorted().collect(Collectors.toList());
  1. Офф-хип: Для уменьшения нагрузки на GC храните данные в byte[] или MemoryMappedFile.

Для очень больших данных рассмотрите внешнюю сортировку (разбивка на чанки + слияние).