优化Elixir中的斐波那契实现：代码效率咨询

原代码 #

def firstFibonacciElements(n) do
  fib([1,1],n)
end
def fib(list,n) do
  list = list ++ [Enum.slice(list,-2..-1) |> Enum.sum]
  case length(list) < n do
    true -> fib(list,n)
    false -> list
  end
end

效率问题分析 #

这段代码的时间复杂度为O(n²)，核心低效点如下：

• list ++ [新元素]操作：Elixir的列表是单向链表，++需要遍历整个左侧列表才能完成拼接，每次添加元素的时间成本随当前列表长度增长而增加，n次操作后总耗时呈平方级增长。
• Enum.slice(list, -2..-1)与length(list)：链表无随机访问能力，取最后两个元素、计算列表长度都需要从表头遍历到表尾，每次操作都是O(k)（k为当前列表长度），进一步放大了时间开销。

优化方案（利用Elixir特性） #

1. 尾递归优化+状态传递

通过递归时传递最后两个斐波那契数而非整个列表，避免遍历链表的开销，同时借助Elixir的尾递归优化（自动转为循环，无栈溢出风险）：

def first_fibonacci_elements(n) when n <= 0, do: []
def first_fibonacci_elements(1), do: [1]
def first_fibonacci_elements(n) do
  fib(1, 1, n - 1, [1])
end

defp fib(_, _, 0, acc), do: Enum.reverse(acc)
defp fib(a, b, remaining, acc) do
  fib(b, a + b, remaining - 1, [b | acc])
end

这里用[b | acc]在列表头部添加元素（O(1)操作），最后仅需一次反转（O(n)）即可得到正确顺序，比反复拼接列表高效得多。

2. 用Stream实现懒加载

如果不需要一次性生成所有元素（比如逐个处理），可以用Stream.unfold创建斐波那契流，按需生成元素以节省内存：

def fib_stream do
  Stream.unfold({1, 1}, fn {a, b} -> {a, {b, a + b}} end)
end

# 取前n个元素示例：fib_stream() |> Enum.take(n)

Stream的优势在于不会提前生成所有元素，适合处理超大n值或流式处理场景，内存占用极低。

优化效果对比 #

• 原代码：n=1000时会出现明显卡顿，时间开销随n平方增长。
• 尾递归版本：时间复杂度降至O(n)，n=10^6级别的数值也能快速处理。
• Stream版本：内存占用可控，适合无需一次性持有全量数据的场景。

内容的提问来源于stack exchange，提问作者IOEnthusiast