Потоки против хвостовой рекурсии для итерационных процессов

Question

Это продолжение моего предыдущего вопроса .

Я понимаю, что мы можем использовать streams для генерации приближения 'pi' (и других чисел), n-го Фибоначчи и т. Д. Однако я сомневаюсь, что streamsподход вправо для этого.

Основным недостатком (как я его вижу) является потребление памяти: например, stream сохранит все числа Фибоначчи для i drop, но это усложняет решение.tail recursion выглядит как более подходящий подход к таким задачам.

Что вы думаете?

Answer 1

Использовать Итератор .Не сохраняет промежуточные значения.

Answer 2

Если вы хотите n-е число Фибоначчи и использовать поток просто как временную структуру данных (если вы не храните ссылки на ранее вычисленные элементы потока), тогда ваш алгоритм будет работать в постоянном пространстве.Ранее вычисленные элементы потока (которые больше не используются) собираются для сбора мусора.И поскольку они были выделены в самом молодом поколении и сразу же собраны, почти все выделения могут находиться в кеше.

Обновление:

Кажется, что текущая реализация Stream не так эффективна, какэто может быть связано главным образом с тем, что он наследует реализацию метода apply от черты LinearSeqOptimized, где он определен как

<code>
def apply(n: Int): A = {
   val rest = drop(n)
   if (n < 0 || rest.isEmpty) throw new IndexOutOfBoundsException("" + n)
   rest.head
}

Ссылка на заголовок потока удерживается здесь thisи предотвращает поток от gc'ed.Таким образом, комбинация методов drop и head (как в f.drop(100).head) может быть лучше для ситуаций, когда выпадение промежуточных результатов возможно.(спасибо Себастьяну Боку за объяснение этого материала на scala-user).

Answer 3

Если нужно ехать быстро, путешествуй налегке.Это означает;Избегайте выделения ненужной памяти.Если вам нужна память, используйте доступные быстрые коллекции.Если вы знаете, сколько памяти вам нужно;предварительно выделить.Распределение является абсолютным убийцей производительности ... для расчета.Ваш код может выглядеть не очень хорошо, но он будет работать быстро.

Однако, если вы работаете с IO (диском, сетью) или с любым взаимодействием с пользователем, распределение уменьшаетсяТогда лучше сместить приоритет с производительности кода на удобство обслуживания.