Объяснение «Потерять голову» в ленивых последовательностях - PullRequest
19 голосов
/ 18 апреля 2011

Почему на языке программирования Clojure этот код проходит с плавающими цветами?

(let [r (range 1e9)] [(first r) (last r)])

Пока этот провал:

(let [r (range 1e9)] [(last r) (first r)])

Я знаю, что это совет "Потеря головы", но не могли бы вы объяснить мне? Я пока не могу это переварить.

UPDATE:
Правильный ответ выбрать действительно сложно, два ответа удивительно информативны.
Примечание: фрагменты кода взяты из "Радости Clojure".

Ответы [ 4 ]

29 голосов
/ 18 апреля 2011

Чтобы уточнить ответы dfan и Rafał , я потратил время на запуск обоих выражений с помощью профилировщика YourKit .

Приятно видеть JVM на работе.Первая программа настолько удобна для GC, что JVM действительно хорошо справляется с управлением ее памятью.

Я нарисовал несколько диаграмм.

GC friendly: (let [r (range 1e9)] [(firstr) (последний r)])

enter image description here

Эта программа выполняет очень мало памяти;в целом менее 6 мегабайт.Как указывалось ранее, он очень дружественный к GC, он делает много коллекций, но использует для этого очень мало ЦП.

Держатель головки: (let [r (range 1e9)] [(last r) (firstr)])

enter image description here

Этот файл очень требователен к памяти.Он занимает до 300 МБ ОЗУ, но этого недостаточно, и программа не завершает работу (JVM умирает менее чем через минуту).GC отнимает до 90% процессорного времени, что указывает на то, что он отчаянно пытается освободить любую память, которую может, но не может ее найти (собранные объекты очень малы или отсутствуют).

Edit Вторая программа исчерпала память, что вызвало дамп кучи.Анализ этого дампа показывает, что 70% памяти составляют объекты java.lang.Integer, которые не могут быть собраны.Вот еще один скриншот:

enter image description here

25 голосов
/ 18 апреля 2011

range генерирует элементы по мере необходимости.

В случае (let [r (range 1e9)] [(first r) (last r)]) он захватывает первый элемент (0), затем генерирует миллиард - 2 элемента, выбрасывая их по ходу, изатем хватает последний элемент (999 999 999).Ему никогда не нужно хранить какую-либо часть последовательности.

В случае (let [r (range 1e9)] [(last r) (first r)]) он генерирует миллиард элементов, чтобы иметь возможность оценить (last r), но он также должен содержатьв начало списка, который он генерирует, чтобы потом оценить (first r).Так что он не может ничего выбросить, как это происходит, и (я полагаю) не хватает памяти.

11 голосов
/ 18 апреля 2011

Что действительно держит голову здесь, так это привязку последовательности к r (а не к уже оцененному (first r), поскольку вы не можете оценить всю последовательность по ее значению.)

В первомcase привязка больше не существует при оценке (last r), так как больше нет выражений с r для оценки.Во втором случае наличие еще не оцененного (first r) означает, что оценщику необходимо сохранить привязку к r.

Чтобы показать разницу, это оценивает ОК:

user> (let [r (range 1e8) a 7] [(last r) ((constantly 5) a)])

[99999999 5]

Хотя это не удается:

(let [r (range 1e8) a 7] [(last r) ((constantly 5) r)])

Даже если выражение, следующее за (last r), игнорирует r, оценщик не , что умный и сохраняет привязку к r, сохраняя при этом всю последовательность.

Редактировать: Я нашел пост, в котором Рич Хики объясняет детали механизма, ответственного за очистку ссылки на голову в вышеупомянутых случаях.Вот оно: Рич Хики на расчистке местных жителей

2 голосов
/ 19 апреля 2011

для технического описания, перейдите к http://clojure.org/lazy. совет , упомянутый в разделе Don't hang (onto) your head

...