寻找完全平方算法的优化
我正在研究的问题是：
在给定特定范围的情况下，找出哪个平方因子总和是一个完美的平方。 因此，如果范围为（1..10），您将得到每个数字的因子（所有因子为1，所有因子为2，所有因子为3等）。将这些因子平方，然后将它们加在一起。 最后检查这笔金额是否是一个完美的正方形。
我坚持重构/优化，因为我的解决方案太慢了。
这是我想出的：
def list_squared(m, n) ans = [] range = (m..n) range.each do |i| factors = (1..i).select { |j| i % j == 0 } squares = factors.map { |k| k ** 2 } sum = squares.inject { |sum,x| sum + x } if sum == Math.sqrt(sum).floor ** 2 all = [] all += [i, sum] ans << all end end ans end 这是我将在方法中添加的示例：
list_squared(1, 250)
然后所需的输出将是一个数组数组，每个数组包含的数字，其平方因子的总和是一个完美的平方和这些平方因子的总和：
[[1, 1], [42, 2500], [246, 84100]]
我首先介绍一些辅助方法（ factors和square? ），以使您的代码更具可读性。
此外，我会减少范围和数组的数量，以提高内存使用率。
require 'prime' def factors(number) [1].tap do |factors| primes = number.prime_division.flat_map { |p, e| Array.new(e, p) } (1..primes.size).each do |i| primes.combination(i).each do |combination| factor = combination.inject(:*) factors << factor unless factors.include?(factor) end end end end def square?(number) square = Math.sqrt(number) square == square.floor end def list_squared(m, n) (m..n).map do |number| sum = factors(number).inject { |sum, x| sum + x ** 2 } [number, sum] if square?(sum) end.compact end list_squared(1, 250)
窄范围（最高250 ）的基准显示只有一个小的改进：
require 'benchmark' n = 1_000 Benchmark.bmbm(15) do |x| x.report("original_list_squared :") { n.times do; original_list_squared(1, 250); end } x.report("improved_list_squared :") { n.times do; improved_list_squared(1, 250); end } end # Rehearsal ----------------------------------------------------------- # original_list_squared : 2.720000 0.010000 2.730000 ( 2.741434) # improved_list_squared : 2.590000 0.000000 2.590000 ( 2.604415) # -------------------------------------------------- total: 5.320000sec # user system total real # original_list_squared : 2.710000 0.000000 2.710000 ( 2.721530) # improved_list_squared : 2.620000 0.010000 2.630000 ( 2.638833)
但是，具有更宽范围（高达10000 ）的基准显示出比原始实现更好的性能：
require 'benchmark' n = 10 Benchmark.bmbm(15) do |x| x.report("original_list_squared :") { n.times do; original_list_squared(1, 10000); end } x.report("improved_list_squared :") { n.times do; improved_list_squared(1, 10000); end } end # Rehearsal ----------------------------------------------------------- # original_list_squared : 36.400000 0.160000 36.560000 ( 36.860889) # improved_list_squared : 2.530000 0.000000 2.530000 ( 2.540743) # ------------------------------------------------- total: 39.090000sec # user system total real # original_list_squared : 36.370000 0.120000 36.490000 ( 36.594130) # improved_list_squared : 2.560000 0.010000 2.570000 ( 2.581622)
tl; dr： N越大，我的代码与原始实现相比表现越好......
提高效率的一种方法是使用Ruby的内置方法Prime :: prime_division 。
对于任何数字n ，如果prime_division返回包含单个元素的数组，则该元素将为[n,1]并且n将显示为prime。 该素数具有因子n和1 ，因此必须与不是素数的数字区别对待。
require 'prime' def list_squared(range) range.each_with_object({}) do |i,h| facs = Prime.prime_division(i) ssq = case facs.size when 1 then facs.first.first**2 + 1 else facs.inject(0) { |tot,(a,b)| tot + b*(a**2) } end h[i] = facs if (Math.sqrt(ssq).to_i)**2 == ssq end end list_squared(1..10_000) #=> { 1=>[], 48=>[[2, 4], [3, 1]], 320=>[[2, 6], [5, 1]], 351=>[[3, 3], [13, 1]], # 486=>[[2, 1], [3, 5]], 1080=>[[2, 3], [3, 3], [5, 1]], # 1260=>[[2, 2], [3, 2], [5, 1], [7, 1]], 1350=>[[2, 1], [3, 3], [5, 2]], # 1375=>[[5, 3], [11, 1]], 1792=>[[2, 8], [7, 1]], 1836=>[[2, 2], [3, 3], [17, 1]], # 2070=>[[2, 1], [3, 2], [5, 1], [23, 1]], 2145=>[[3, 1], [5, 1], [11, 1], [13, 1]], # 2175=>[[3, 1], [5, 2], [29, 1]], 2730=>[[2, 1], [3, 1], [5, 1], [7, 1], [13, 1]], # 2772=>[[2, 2], [3, 2], [7, 1], [11, 1]], 3072=>[[2, 10], [3, 1]], # 3150=>[[2, 1], [3, 2], [5, 2], [7, 1]], 3510=>[[2, 1], [3, 3], [5, 1], [13, 1]], # 4104=>[[2, 3], [3, 3], [19, 1]], 4305=>[[3, 1], [5, 1], [7, 1], [41, 1]], # 4625=>[[5, 3], [37, 1]], 4650=>[[2, 1], [3, 1], [5, 2], [31, 1]], # 4655=>[[5, 1], [7, 2], [19, 1]], 4998=>[[2, 1], [3, 1], [7, 2], [17, 1]], # 5880=>[[2, 3], [3, 1], [5, 1], [7, 2]], 6000=>[[2, 4], [3, 1], [5, 3]], # 6174=>[[2, 1], [3, 2], [7, 3]], 6545=>[[5, 1], [7, 1], [11, 1], [17, 1]], # 7098=>[[2, 1], [3, 1], [7, 1], [13, 2]], 7128=>[[2, 3], [3, 4], [11, 1]], # 7182=>[[2, 1], [3, 3], [7, 1], [19, 1]], 7650=>[[2, 1], [3, 2], [5, 2], [17, 1]], # 7791=>[[3, 1], [7, 2], [53, 1]], 7889=>[[7, 3], [23, 1]], # 7956=>[[2, 2], [3, 2], [13, 1], [17, 1]], # 9030=>[[2, 1], [3, 1], [5, 1], [7, 1], [43, 1]], # 9108=>[[2, 2], [3, 2], [11, 1], [23, 1]], 9295=>[[5, 1], [11, 1], [13, 2]], # 9324=>[[2, 2], [3, 2], [7, 1], [37, 1]]}
该计算花费大约0.15秒。
因为i = 6174
(2**1) * (3**2) * (7**3) #=> 6174
和
1*(2**2) + 2*(3**2) + 3*(7**2) #=> 169 == 13*13
经常解决这样的问题的诀窍是从试验分部换成筛子 。 在Python中（抱歉）：
def list_squared(m, n): factor_squared_sum = {i: 0 for i in range(m, n + 1)} for factor in range(1, n + 1): i = n - n % factor # greatest multiple of factor less than or equal to n while i >= m: factor_squared_sum[i] += factor ** 2 i -= factor return {i for (i, fss) in factor_squared_sum.items() if isqrt(fss) ** 2 == fss} def isqrt(n): # from http://stackoverflow.com/a/15391420 x = n y = (x + 1) // 2 while y < x: x = y y = (x + n // x) // 2 return x
下一个优化是仅将factor步长到isqrt(n) ，成对地添加因子平方（例如， 2和i // 2 ）。