Использование потока для генерации суммы первых 100000/1 млн. Терминов Фибоначчи в эликсире - PullRequest
Новая
       3

Использование потока для генерации суммы первых 100000/1 млн. Терминов Фибоначчи в эликсире

0 голосов
/ 19 сентября 2019

Обновление: это не об использовании Фибоначчи.Этот вопрос о том, как правильно понять поток.

Для генерации серии / суммы Фибоначчи: 

defmodule Fib do
    def dofib(0), do: []
    def dofib(n) when is_integer(n), do: dofib(0, 1, n-1)
    def dofib(cur, _, 0), do: [cur]
    def dofib(cur, next, count), do: [cur] ++ dofib(next, cur+next, count-1)
end

# 10000 |> Fib.dofib |> List.foldl(0, &(&1 + &2))

Это может работать <100K. </p>

Какие оптимизации или дездесь возможен беспорядок?: 

Stream.unfold([1, 0], fn([h|t]=acc)-> {h, [h + List.first(t)|acc]} end) 
|> Stream.take(100000) 
|> Flow.from_enumerable 
|> Flow.partition(stages: 100) 
|> Flow.reduce(fn -> 0 end, fn(n, acc)-> n + acc end) 
|> Flow.departition(fn -> 0 end, &(&1 + &2), &(&1)) 
|> Stream.into(File.stream!("output.txt", [:delayed_write, encoding: :utf8])) 
|> Stream.run

Сбой при 200K.

Ответы [ 3 ]

4 голосов
/ 19 сентября 2019

Проблема в том, что вы слишком усложняете задачу, взрывая память.Что спрашивают?Чтобы получить сумму.Он попросил получить список номеров?Нет.Пока все хорошо.

Тебе не нужны рекурсии, потоки, потоки, свертывание и все такое дерьмо :) Обычная старая хорошая Enum.reduce/3 подойдет.Просто сохраняйте текущее значение суммы рядом с текущими волокнами на каждой итерации. 

1..1_000_000
|> Enum.reduce({{0, 1}, 0}, fn _, {{prev, fib}, sum} ->
  {{fib, prev + fib}, sum + fib}
end)
|> elem(1)
|> to_string()
|> String.length()

Так что примерно через 5 секунд вы узнаете, что число имеет 208988 цифр.Удалите две последние строки, чтобы получить значение.

0 голосов
/ 25 сентября 2019

Если вы действительно хотите использовать Stream s, Stream.resource/3 ваш друг: 

iex(1)> fib = Stream.resource(fn -> {1, 1} end, fn {a, b} -> {[a], {b, a + b}} end, fn _ -> nil end)
#Function<55.117072283/2 in Stream.resource/3>
iex(2)> fib |> Stream.drop(1_000_000) |> Enum.take(1) |> hd

Чтобы получить миллионное число Фибоначчи, запустите fib |> Stream.drop(1_000_000) |> Enum.take(1) |> hd().Это займет ~ 5 секунд и будет длиной 200К + цифр, но это выполнимо за конечное время.

Суммирование первых 100_000 так же просто, как fib |> Stream.take(100_000) |> Enum.sum().

Оба результата могутздесь можно увидеть, потому что они слишком велики для комментария SO: https://gist.github.com/DoggettCK/7f7eb906e455179af400b739b84e8960

Вы также можете сделать версию математического уравнения, используя phi, но :math.pow Эрланга умирает при удивительно низких значениях. 

iex(11)> fib = fn(n) ->
...(11)> phi = (1 + :math.sqrt(5))/2
...(11)> (:math.pow(phi, n) - :math.pow(-1/phi, n))/:math.sqrt(5) |> round
...(11)> end
#Function<6.128620087/1 in :erl_eval.expr/5>
iex(12)> fib.(10)
55
iex(13)> fib.(10000)
** (ArithmeticError) bad argument in arithmetic expression
    (stdlib) :math.pow(1.618033988749895, 10000)
0 голосов
/ 19 сентября 2019

Перед тем, как начать изучать параллелизм, было бы лучше исправить некоторые ключевые проблемы с помощью исходного алгоритма.Особенно эта строка: 

[cur] ++ dofib(next, cur+next, count-1)

У этого есть две проблемы.

  1. Он хранит весь список в памяти и создает его в стеке вызовов.
  2. Он не использует хвостовую рекурсию.Это приведет к тому, что стек вызовов выйдет из-под контроля.

Вот альтернатива, которая использует хвостовую рекурсию и не поддерживает список в стеке: 

def sumfib(0), do: 0
def sumfib(n), do: sumfib(0, 1, 1, n)
defp sumfib(_first, _second, sum, 1), do: sum

defp sumfib(first, second, sum, dec) do
  new_second = first + second
  sumfib(second, new_second, sum + new_second, dec - 1)
end

Этоотлично работает на 200К.Он замедляется на 1M, но все равно возвращает результат через несколько секунд на моей машине.

...