寻找完美平方算法的优化

一尘不染

寻找完美平方算法的优化

algorithm

我正在研究的问题是：

在给定特定范围内，找出哪些平方因子的和是理想平方。因此，如果范围是（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]]

阅读 228

2020-07-28

共1个答案

一尘不染

我将从介绍一些辅助方法（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与原始实现相比，代码越大性能越好…

2020-07-28