question我正在研究的是:
Find which sum of squared factors are a perfect square given a specific range. So if the range was (1..10) you would get each number's factors (all factors for 1, all factors for 2, all factors for 3 ect..) Square those factors, then add them together. Finally check if that sum is a perfect square.
我坚持重构/优化,因为我的解决方案太慢了。
这是我想出的:
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 - 寻找完美平方算法的优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37492901/