瓶颈在哪里？性能差距...（项目欧拉＃12）

Question

以下是我对项目欧拉问题＃12的解决方案：

def factor this_number, number=nil, *factors 
    number = this_number if number.nil? 
    m=2 
    loop do 
    break factors << m if number % m == 0 
    m+=1 
    end 
    arr = factors.flatten 
    arr.inject(:*) != this_number ? factor(this_number, (number/factors.last), factors) : arr.uniq.collect {|k| arr.count(k)+1 }.inject(:*) 
end 

def highly_divisible_triangular_number number 
    n = 2 
    loop do 
    num = (n*(n+1)/2) 
    r = factor(num) 
    break num if (r >= number) 
    n+=1 
    end 
end 

puts Benchmark.measure { p highly_divisible_triangular_number(n) } 

该解决方案是扎卡里丹顿的礼貌：

require 'mathn' 

class Integer 
    def divisors 
    return [1] if self == 1 
    primes, powers = self.prime_division.transpose 
    exponents = powers.map{|i| (0..i).to_a} 
    divisors = exponents.shift.product(*exponents).map do |powers| 
     primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) 
    end 
    divisors.sort.map{|div| [div, self/div]} 
    end 
end 

triangles = Enumerator.new do |yielder| 
    i = 1 
    loop do 
    yielder.yield i * (i + 1)/2 
    i += 1 
    end 
end 

puts Benchmark.measure { p triangles.detect { |t| t.divisors.count > n } } 

基准测试结果：

__projecteuler: ruby 'problem_12a.rb' 100 
73920 
    0.010000 0.000000 0.010000 ( 0.009514) [MINE] 
73920 
    0.020000 0.000000 0.020000 ( 0.028339) 

__projecteuler: ruby 'problem_12a.rb' 200 
2031120 
    0.120000 0.000000 0.120000 ( 0.123996) [MINE] 
2031120 
    0.250000 0.010000 0.260000 ( 0.251311) 

__projecteuler: ruby 'problem_12a.rb' 300 
2162160 
    0.120000 0.000000 0.120000 ( 0.122242) [MINE] 
2162160 
    0.260000 0.000000 0.260000 ( 0.259200) 

__projecteuler: ruby 'problem_12a.rb' 400 
17907120 
    0.730000 0.000000 0.730000 ( 0.725883) [MINE] 
17907120 
    1.050000 0.000000 1.050000 ( 1.057079) 

__projecteuler: ruby 'problem_12a.rb' 500 
76576500 
    2.650000 0.010000 2.660000 ( 2.657921) [MINE] 
76576500 
    2.790000 0.000000 2.790000 ( 2.795859) 

__projecteuler: ruby 'problem_12a.rb' 600 
103672800 
    3.470000 0.010000 3.480000 ( 3.484551) [MINE] 
103672800 
    3.420000 0.000000 3.420000 ( 3.419714) 

__projecteuler: ruby 'problem_12a.rb' 700 
236215980 
    7.430000 0.010000 7.440000 ( 7.438317) [MINE] 
236215980 
    6.020000 0.020000 6.040000 ( 6.046869) 

__projecteuler: ruby 'problem_12a.rb' 800 
842161320 
24.040000 0.020000 24.060000 (24.062911) [MINE] 
842161320 
14.780000 0.000000 14.780000 (14.781805) 

问题

你可以从基准看到的结果我的解决方案是快了N个500，但会随>ñ全军覆没。有人能帮我理解为什么吗？

更新 对于那些谁认为瓶颈是关系到递归，以及重试。 factor方法，无需递归和基准不不显示改进：

__projecteuler: ruby 'problem_12a.rb' 800 
842161320 
24.960000 0.020000 24.980000 (24.973017) [MINE (w/o recursion)] 
842161320 
14.780000 0.030000 14.810000 (14.807774) 


def factor this_number 
    number,arr=this_number,[] 

    done = false 
    until done 
    m=2 
    loop do 
     break arr << m if number % m == 0 
     m+=1 
    end 
    arr.inject(:*) != this_number ? number = number/arr.last : done = true 
    end 

    arr.uniq.collect {|k| arr.count(k)+1 }.inject(:*) 
end 

Answer 1

您的瓶颈在于您的分解方法。 （您highly_divisible_triangular_number环和他的triangles.detect环基本相同。）

当你分解可以计算更快

（对不起，我不得不重构你的代码。一切都还在计算相同）。

def num_factors(number, dividend=nil, prime_factors_found=[]) 
    dividend = number if dividend.nil? 

    smallest_prime_factor = (2..dividend).find { |divisor| dividend % divisor == 0 } # 1. 
    prime_factors_found << smallest_prime_factor 

    all_prime_factors_found = prime_factors_found.inject(:*) == number 
    if !all_prime_factors_found 
    return num_factors(number, dividend/prime_factors_found.last, prime_factors_found) 
    end 

    prime_factor_powerset_size = prime_factors_found.uniq.map do |prime_factor| 
    prime_factors_found.count(prime_factor) + 1         # 2. 
    end.inject(:*) 

    return prime_factor_powerset_size 
end 

1. 您不需要检查每个数字。您可以检查2次，然后开始跳过偶数。之后你可以检查3次，每6个数字只检查2个。
   你也在这里重新计算大量的数字。例如，每当divisor是一个11（一个素数）时，您将通过完整循环来再次发现11确实是一个素数。最糟糕的是，对于n素数，您将计数到n^2来验证所有这些数据。
2. map是一个完整的通过素数因子阵列。但是每次传递，count操作也需要通过该阵列。这意味着对于10个项目的数组（O(n)），您可以在数组中查找100次值（O(n^2)）。相反，检查发生的事件可以在一次传递中完成。

他的因式分解节省计算（和在它不）

你可能会奇怪，为什么他的代码是那么快，因为它包含以下嵌套循环：

divisors = exponents.shift.product(*exponents).map do |powers| 
    primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) 
end 

与＃2相同，他为另一个线性通道内的每个元素完成线性通过工作，即这部分计算也是O(n^2)。当所需要的只是最终的总数时，他通过实际计算所有除数来浪费计算。但无论如何最终，看起来这个部分在渐近表现上是平等的。

事实证明，你的版本之间的差异，让他最终打破未来是＃1 - 主要测试器/发电机。虽然你有一个自定义的循环，一遍又一遍地检查每一个数字，他使用a prime tester/generator in the Ruby library。如果你想看看它是如何实现的，你可以在计算机上找到源代码，其中红宝石的安装位置为<ruby root>/lib/ruby/<version>/prime.rb。

这里是一个版本的代码，它使用了prime_division method：

require 'prime' 
def num_factors2(number, dividend=nil, prime_factors_found=[]) 
    dividend = number if dividend.nil? 

    smallest_prime_factor = dividend.prime_division.first.first # this is the only change 
    prime_factors_found << smallest_prime_factor 

    all_prime_factors_found = prime_factors_found.inject(:*) == number 
    if !all_prime_factors_found 
    return num_factors2(number, dividend/prime_factors_found.last, prime_factors_found) 
    end 

    prime_factor_powerset_size = prime_factors_found.uniq.map do |prime_factor| 
    prime_factors_found.count(prime_factor) + 1 
    end.inject(:*) 

    return prime_factor_powerset_size 
end 

而且在我的系统基准测试：

Benchmark.measure { (2..50000).map { |i| num_factors(i) } } 
=> 17.050000 0.020000 17.070000 (17.079428) 
Benchmark.measure { (2..50000).map { |i| num_factors2(i) } } 
=> 2.630000 0.010000 2.640000 ( 2.672317) 

额外

使用你的两个的组合方法，我发现了一种很酷的方式来将问题表达为红宝石中的一行代码！ （这也是真快！）

n = (2..(1.0/0)).find { |i| (i*(i+1)/2).prime_division.inject(1) { |p,i| p*i[1]+p } > 500 } 

哪里n是n个三角形数量，即triangle(n) = n * (n + 1)/2。

Answer 2

Ruby是臭名昭著的执行与递归坏。你也许可以阅读this post来获得关于如何解决它的一些指导。