Утечка пространства обычно определяется выполнением программы, которая занимает больше места, чем необходимо.Совместимо ли такое определение с алгоритмами, которые требуют ленивых вычислений для амортизированной эффективности времени?Например, тривиальная утечка пространства может выглядеть так:
1 + (2 + 3 + ...)
Было бы нормально для ленивого алгоритма, такого как поиск по дереву, генерировать структуры с одинаковыми размерами?
У меня есть подозрение, что правильные ленивые шаблоны оценки будут иметь тенденцию выглядеть по-разному, что облегчает выявление фактических утечек.Например, структура может выглядеть следующим образом:
[...] : a : b : c
Где [...]
part - это префикс, который не имеет ссылок и мог быть уже собран сборщиком мусора.В таком случае ленивый алгоритм вполне может работать в O(1)
пространстве, и не может быть утечки в пространстве, что делает различие очень ясным.
Интересно, распространено ли это или существует более широкий спектр компромиссов?сделать между пространством и временем эффективность в ленивых языках.
РЕДАКТИРОВАТЬ: Возможный контрпример - постоянные структуры.Их легко отличить от космических утечек?