为 IF 编写可变数量的参数

Question

我正在尝试编写一个函数来解决此问题的任何一般版本：

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

我解决这个问题的方法是：

multiples = Array(Int, 0)
[ (i % 3 == 0 || i % 5 == 0) && push!(multiples, i) for i in 1:1000 ]
sum(multiples)

我想编写一个函数，它将接受一个倍数数组（在本例中为 [3,5]）和最终数字（在本例中为 1000）。关键是数组可以包含任意多个数字，而不仅仅是两个（例如 [3,5,6]）。然后函数应该运行 i % N == 0 每个 N.

如何最有效地做到这一点？这会涉及元编程吗？（代码不必采用列表理解格式。）

谢谢！

Answer 1

首先出现在我脑海中的是以下内容，使用模除法和函数式风格：

v1(N,M) = sum(filter(k->any(j->k%j==0,M), 1:N))

但我想研究一些替代方案，因为这有两个问题：

两个级别的匿名函数，Julia 还没有优化好的地方。
根据范围创建一个临时数组，然后求和。

所以这是最明显的替代方案，单行代码的 C 风格版本：

function v2(N,M)
    sum_so_far = 0
    for k in 1:N
        for j in M
            if k%j==0
                sum_so_far += k
                break
            end
        end
    end
    return sum_so_far
end

但后来我又想了想，记得在某处读到模除法是一个缓慢的操作。我想看看 IntSets 是如何执行的——一个专门用于整数的集合。所以这是另一个单行，IntSets 没有使用任何模块划分，并且是函数式样式！

v3(N,M) = sum(union(map(j->IntSet(j:j:N), M)...))

将地图扩展为 for 循环并重复将 union! 应用于单个 IntSet 并没有好多少，所以我不会在此处包括它。分解一下：

IntSet(j:j:N)是j和N之间j的所有倍数
j->IntSet(j:j:N) 是一个匿名函数 returns 即 IntSet
map(j->IntSet(j:j:N), M) 将该函数应用于 M 中的每个 j，并且 returns a Vector{IntSet}.
... "splats" 向量输出为 union
union 创建一个 IntSet，它是其参数的并集 - 在本例中，是 M
然后我们求和就完成了

我用

对这些进行了基准测试

N,M = 10000000, [3,4,5]

这给了你

一行：2.857292874 seconds (826006352 bytes allocated, 10.49% gc time)
C 风格：0.190581908 seconds (176 bytes allocated)
IntSet 无模：0.121820101 seconds (16781040 bytes allocated)

所以你甚至可以用更高级别的对象击败 C 风格的代码 - 我猜模是那么昂贵！无模运算的巧妙之处在于它很容易并行化：

addprocs(3)
@everywhere worker(j,N) = IntSet(j:j:N)
v4(N,M) = sum(union(pmap(j->worker(j,N),M)...))
@show v4(1000, [3,5])
@time v3(1000000000,[3,4,5]);  # bigger N than before
@time v4(1000000000,[3,4,5]);

这给出了

elapsed time: 12.279323079 seconds (2147831540 bytes allocated, 0.94% gc time)
elapsed time: 10.322364457 seconds (1019935752 bytes allocated, 0.71% gc time)

并没有好多少，但我想是这样。

Answer 2

好的，这是我更新的答案。

根据@IainDunning 的回答中的基准，击败的方法是他的v2。我下面的方法似乎多快，但我不够聪明，无法将其推广到长度大于 2 的输入向量。一个好的数学家应该能够改进我的答案。

快速直觉：对于 length(M)=2 的情况，问题简化为 M[1] 到 N 的所有倍数的总和加上 [= 的所有倍数的总和16=] 到 N，其中，为了避免重复计算，我们需要减去 M[1]*M[2] 到 N 的所有倍数的总和。可以为 M > 2 实施类似的算法，但重复计算问题很快变得多复杂。我怀疑肯定存在一个通用算法（这是组合学领域一直出现的那种问题），但我不知道它是什么。

这是我的方法 (f1) 与 v2:

的测试代码

function f1(N, M)
  if length(M) > 2
    error("I'm not clever enough for this case")
  end
  runningSum = 0
  for c = 1:length(M)
    runningSum += sum(M[c]:M[c]:N)
  end
  for c1 = 1:length(M)
    for c2 = c1+1:length(M)
      temp1 = M[c1]*M[c2]
      runningSum -= sum(temp1:temp1:N)
    end
  end
  return(runningSum)
end    

function v2(N, M)
  sum_so_far = 0
  for k in 1:N
    for j in M
      if k%j==0
        sum_so_far += k
        break
      end
    end
  end
  return sum_so_far
end

f1(1000, [3,5])
v2(1000, [3,5])

N = 10000000
M = [3,5]

@time f1(N, M)
@time v2(N, M)

时间是：

elapsed time: 4.744e-6 seconds (96 bytes allocated)
elapsed time: 0.201480996 seconds (96 bytes allocated)

抱歉，这是一个有趣的问题，但恐怕我必须回去工作:-) 如果有机会，我会稍后再回来查看...

为 IF 编写可变数量的参数

Write a variable number of arguments for IF

julia