Фильтр потока # Испускает память для 1 000 000 предметов

Question

Предположим, у меня есть Stream длины 1,000,000 со всеми 1.

scala> val million = Stream.fill(100000000)(1) 
million: scala.collection.immutable.Stream[Int] = Stream(1, ?) 

scala> million filter (x => x % 2 == 0) 
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded 

Я получаю исключение Out of Memory.

Затем я попробовал тот же filter позвонить с List.

scala> val y = List.fill(1000000)(1) 
y: List[Int] = List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ... 

scala> y.filter(x => x % 2 == 0) 
res2: List[Int] = List() 

Все еще это удается.

Почему у Stream#filter заканчивается память, но List#filter заканчивается просто отлично?

И наконец, с большим потоком, будет filter результат в ленивой оценке всего потока?

Answer 1

Накладные расходы List - отдельный объект (пример ::) с 2 полями (2 указателя) на элемент.

Накладных Stream - экземпляр Cons (с 3 указателей) плюс экземпляр Function (tl: => Stream[A]) для ленивой оценки Stream#tail на элемент.

Значит, вы потратите ~ 2 раза больше памяти на Stream.

Вы определили свой Stream как val. В качестве альтернативы вы можете определить million как def - в этом случае после filter GC удалит все созданные элементы, и вы вернете свою память.

Обратите внимание, что в Stream только tail лениво, head строго, поэтому filter оценивает строго, пока не получит первый элемент, который удовлетворяет заданный предикат, а так как там нет таких элементов в Streamfilter перебирает все ваш million потока и помещает все элементы в память.