为什么方法"div"比"div2"快？

Question

我试图破译为什么div方法比div2方法快，我找不到原因。

def div2(num)
[*1..num].select do |n|
n if num % n == 0
end
end
p div2(58463982)

def div(num)
result = []
(1..num).each do |n|
break if result.include?(num / n)
result.concat([n, num / n]).uniq! if num % n == 0
end
result.sort!
end
p div(58463982)

Answer 1

我将让其他人解释为什么div比div2快。我想展示如何以一种相当快的方式计算给定自然数的因子。

每个整数都可以表示为一组素数的乘积，每个素数取一个或多个的幂。我们可以使用Prime::prime_division方法来求这些素数及其幂。例如,

require 'prime'

arr = Prime.prime_division(58463982)
#=> [[2, 1], [3, 2], [53, 1], [61283, 1]]

这意味着:

(2**1) * (3**2) * (53**1) * (61283**1)
#=> 58463982

58463982的一个因数等于，例如:

(2**1) * (3**2) * (53**0) * (61283**1)
#=> 2 * 9 * 1 * 61283
#=> 1103094 

确认:

58463982 % 1103094
#=> 0

另一个是

(2**0) * (3**1) * (53**1) * (61283**0)
#=> 1 * 3 * 53 * 1
#=> 159

我们发现给定数的所有因子都可以使用array# product和Enumerable#reduce(又名inject)方法按如下方式(组合)计算。

def all_factors(n)
primes, exponents = Prime.prime_division(n).transpose
first_exp_range, *rest_exp_range = exponents.map { |e| [*0..e] }
first_exp_range.product(*rest_exp_range).map do |exps| 
primes.zip(exps).reduce(1) { |t,(p,e)| t*(p**e) }
end.sort
end

根据需要，末尾的.sort可能不需要。

---

我们可以测试:

require 'time'

t = Time.now
p all_factors(58463982)
p Time.now - t
#=> [1, 2, 3, 6, 9, 18, 53, 106, 159, 318, 477, 954, 61283, 122566,
#    183849, 367698, 551547, 1103094, 3247999, 6495998, 9743997,
#    19487994, 29231991, 58463982]
#
#=> 0.001405 (seconds)

相比之下，div2和div计算58463982的因子分别需要4.467112和0.021103秒。

这显然比那些方法快得多。

---

我们可以逐步遍历示例以查看正在执行的计算。

n = 58463982

然后

primes, exponents = Prime.prime_division(n).transpose
#=> [[2, 3, 53, 61283], [1, 2, 1, 1]]

primes
#=> [2, 3, 53, 61283]
exponents
#=> [1, 2, 1, 1]

,

first_exp_range, *rest_exp_range = exponents.map { |e| [*0..e] }
#=> [[0, 1], [0, 1, 2], [0, 1], [0, 1]]

first_exp_range
#=> [0, 1]
rest_exp_range
#=> [0, 1, 2], [0, 1], [0, 1]

然后

a = first_exp_range.product(*res_exp_range)
#=> [[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1],
#    [0, 1, 0, 0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1],
#    [0, 2, 0, 0], [0, 2, 0, 1], [0, 2, 1, 0], [0, 2, 1, 1],
#    [1, 0, 0, 0], [1, 0, 0, 1], [1, 0, 1, 0], [1, 0, 1, 1],
#    [1, 1, 0, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 1],
#    [1, 2, 0, 0], [1, 2, 0, 1], [1, 2, 1, 0], [1, 2, 1, 1]]

,

b = a.map { |exps| primes.zip(exps).reduce(1) { |t,(p,e)| t*(p**e) } }
#=> [1, 61283, 53, 3247999, 3, 183849, 159, 9743997, 9, 551547,
#    477, 29231991, 2, 122566, 106, 6495998, 6, 367698, 318,
#    19487994, 18, 1103094, 954, 58463982]

查看排序结果，

b.sort
#=> [1, 2, 3, 6, 9, 18, 53, 106, 159, 318, 477, 954, 61283, 122566,
#    183849, 367698, 551547, 1103094, 3247999, 6495998, 9743997,
#    19487994, 29231991, 58463982]

Answer 2

div2方法创建一个从1到num的列表，然后遍历其中的所有元素。

div方法可以提前中断，因此不需要迭代那么多次。