为什么Elixir的Enum.any？慢？

Question

我跑到命令之下

MIX_ENV=prod  mix profile.fprof --no-start -e "Math.prime_seq 501"

对于以下代码

  def prime_seq(n) do
    prime_seq(n, 1, 3, [2,3,5,7,11,13,17,19,23])
  end

  def prime_seq(n, c, p, cache) when c < n do
    is_it = cache |> Enum.any?(fn n -> rem(p, n) == 0 end)
    if not is_it do
      prime_seq(n, c+1, p+2, cache ++ [p])
    else
      if(is_prime(p)) do
        prime_seq(n, c+1, p+2, cache ++ [p])
      else
        prime_seq(n, c, p+2, cache)
      end
    end
  end

  def prime_seq(n, c, p, _) when c == n do
    p-2
  end

结果如下:

为什么Enum.do_any?要花太多时间？

是的,这是一个找到第n个素数的愚蠢算法,并且有更好的算法.但重点是,Enum.any?使用专用函数迭代列表的速度要慢一些.

我相信anom func是rem(p,n),CMIIW

更新: 我删除了Enum.any?我的,叫divisible?

 def divisible?(n, [h|t]) do
    if rem(n, h) == 0 do
      true
    else
      divisible?(n, t)
    end
  end

  def divisible?(n, []) do
    false
  end
  ..... 
  def prime_seq(n, c, p, cache) when c < n do
    #is_it = cache |> Enum.any?(fn n -> rem(p, n) == 0 end)
    is_it = divisible?(p, cache)
    if not is_it do
      prime_seq(n, c+1, p+2, cache ++ [p])
    else
      if(is_prime(p)) do
        prime_seq(n, c+1, p+2, cache ++ [p])
      else
        prime_seq(n, c, p+2, cache)
      end
    end
  end
  .....

结果:

所以..通过简单的修改,我可以使它快3倍,迭代次数也相同.

注意:当我学习灵药时,这是一个玩具项目.请多多包涵.

is_prime函数:

def is_prime(n, i) when i < n do
    if rem(n, i) == 0 do
      false
    else
      is_prime(n, i+1)
    end
  end
  def is_prime(n, i) when i >= n do
    true
  end
  def is_prime(n) do
    cond do
    n <= 1 -> false
    n <= 3 -> true
    rem(n, 2) == 0 or rem(n, 3) == 0 -> false
    true -> is_prime(n, 3)
    end
  end

Answer 1

自从我被问及,我会把它作为答案而不是评论.

问题不在于匿名函数是"昂贵的",而是代码几乎没有做任何事情,只是在列表上进行迭代.

BEAM调度程序使用缩减来执行功能切片.这个稍微复杂一点,但每个函数调用都算作一次减少.当您使用匿名函数时,您正在增加减少的时间成本(即,将实际函数的查找添加到减少的时间成本中.)通常,这个额外成本可以忽略不计,但是当您执行数百万次时,它加起来.

BEAM调度程序为每个进程2000减少,然后在新进程中提供时间片.

您已经创建了一个病态边缘案例,将零值与另一个值进行比较.如果您将零与任何看起来"昂贵"的东西进行比较,那么无论绝对比例的值有多大或多小都无关紧要.

正确的结论是,比O(n)更快扩展的递归算法对每次递归中完成的工作量非常敏感.你应该感到惊讶的是,这根本不起作用,而不是它很慢.

如果我今天有时间,我会尝试使用以下各种情况获得一些减少计数:erlang.statistics(:exact_reductions).

我使用此代码来获取一些基本指标.

defmodule Counter do

 def count(function,arg) do
  {_ , count } = :erlang.process_info(self,:reductions)
  function.(arg)
  {_ , new_count } = :erlang.process_info(self,:reductions)
  new_count - count
 end

end

这个代码计算减少的方式并不完美,它应该真正运行在它自己的进程中.

这些是我得到的结果,首先是Enum.any？版.

iex(4)> Counter.count(&Math.prime_seq/1, 10)
283
iex(5)> Counter.count(&Math.prime_seq/1, 100)
14086
iex(6)> Counter.count(&Math.prime_seq/1, 1000)
1105114
iex(7)> Counter.count(&Math.prime_seq/1, 10000)
103654258
iex(8)> Counter.count(&Math.prime_seq/1, 100000)
10068833898

请注意,所有这些减少都发生在一个调度线程中,我的8核笔记本电脑在此测试期间几乎没有忙.很明显,这是一种减少O(n**2)算法.现在具有可分割的功能

iex(1)> Counter.count(&Math.prime_seq_div/1, 10)
283
iex(2)> Counter.count(&Math.prime_seq_div/1, 100)
14062
iex(3)> Counter.count(&Math.prime_seq_div/1, 1000)
1105485
iex(4)> Counter.count(&Math.prime_seq_div/1, 10000)
103655170
iex(5)> Counter.count(&Math.prime_seq_div/1, 100000)
10068870615

说实话,我预计这些数字会更小.事实上,他们并没有让我得出关于正在发生的事情的另一个结论,这不是减少,而是减少更多的时间.