Котлин: Почему Sequence более производительна в этом примере?

Question

В настоящее время я изучаю Kotlin и у меня есть вопрос о последовательности против коллекций .

Я прочитал сообщение в блоге об этой теме, и там вы можете найти этот фрагмент кода:

Список реализации:

val list = generateSequence(1) { it + 1 }
    .take(50_000_000)
    .toList()

measure {
    list
        .filter { it % 3 == 0 }
        .average()
}
// 8644 ms

Последовательность реализации:

val sequence = generateSequence(1) { it + 1 }
    .take(50_000_000)

measure {
    sequence
        .filter { it % 3 == 0 }
        .average()
}
// 822 ms

Дело в том, что реализация Sequence примерно в 10 раз быстрее.

Однако я не очень понимаю, ПОЧЕМУ это так. Я знаю, что с Sequence вы выполняете "ленивую оценку", но я не могу найти причину, почему это помогает сократить обработку в этом примере.

Однако здесь я знаю, почему последовательность обычно быстрее:

val result = sequenceOf("a", "b", "c")
    .map {
        println("map: $it")
        it.toUpperCase()
    }
    .any {
        println("any: $it")
        it.startsWith("B")
    }

Поскольку с помощью Sequence вы обрабатываете данные «по вертикали», когда первый элемент начинается с «B», вам не нужно отображать остальные элементы. Здесь есть смысл.

Итак, почему это также быстрее в первом примере?

Answer 1

Давайте посмотрим, что на самом деле делают эти две реализации:

1. Реализация List сначала создает List в памяти с 50 миллионами элементов. Это займет минимум 200 МБ, так как целое число занимает 4 байта.

   (На самом деле это, вероятно, намного больше, чем это. Как отметил Алексей Романов, поскольку это общая реализация List, а не IntList, она не будет хранить целые числа напрямую. , но будет «упаковывать» их - сохраняя ссылки на объекты * 1012. * В JVM каждая ссылка может составлять 8 или 16 байтов, а каждая Int может занимать 16, давая 1–2 ГБ. Кроме того, в зависимости от того, как List создается, он может начинаться с небольшого массива и продолжать создавать все больше и больше по мере увеличения списка, копируя все значения за раз, используя все еще больше памяти.)

   Затем он должен прочитать все значения обратно из списка, отфильтровать их и создать другой список в памяти.

   Наконец, он должен снова прочитать все эти значения, чтобы вычислить среднее.

2. С другой стороны, реализация Sequence не должна ничего хранить! Он просто генерирует значения по порядку, а , как и каждое из них, проверяет, делится ли он на 3 и, если это так, включает его в среднее значение.

   (Это в значительной степени так, как если бы вы реализовывали это «вручную».)

Вы можете видеть, что в дополнение к проверке делимости и вычислению среднего значения, реализация List делает огромный доступ к памяти, что займет много времени. Это основная причина, по которой он намного медленнее чем версия Sequence, которая не!

Видя это, вы можете спросить, почему мы не используем последовательности везде ... Но это довольно экстремальный пример. Настройка и последующая итерация последовательности имеют некоторые собственные издержки и для небольших списков, которые могут перевесить накладные расходы памяти. Таким образом, последовательности имеют явное преимущество только в тех случаях, когда списки очень велики, обрабатываются строго по порядку, имеется несколько промежуточных этапов и / или многие элементы отфильтрованы по пути (особенно, если последовательность бесконечна!).

По моему опыту, такие условия встречаются не очень часто. Но этот вопрос показывает, как важно их узнавать, когда они это делают!

Answer 2

Использование ленивых вычислений позволяет избежать создания промежуточных объектов, которые не имеют значения с точки зрения конечной цели.

Кроме того, метод сравнительного анализа, используемый в упомянутой статье, не является супер точным. Попробуйте повторить эксперимент с JMH .

Исходный код создает список, содержащий 50_000_000 объектов:

 val list = generateSequence(1) { it + 1 }
  .take(50_000_000)
  .toList()

затем перебирает его и создает другой список , содержащий подмножество его элементов:

.filter { it % 3 == 0 }

... а затем приступает к вычислению среднего:

.average()

---

Использование последовательностей позволяет избежать выполнения всех этих промежуточных шагов. Приведенный ниже код не производит 50_000_000 элементов, это просто представление последовательности 1 ... 50_000_000:

val sequence = generateSequence(1) { it + 1 }
  .take(50_000_000)

добавление к нему фильтрации не запускает и сам расчет, а выводит новую последовательность из существующей (3, 6, 9 ...):

.filter { it % 3 == 0 }

и, в конце концов, вызывается терминальная операция, которая запускает оценку последовательности и фактический расчет:

.average()

---

Некоторые соответствующие чтения:

Котлин: Остерегайтесь привычек API Java Stream

Производительность API Kotlin Collections Antipatterns