我正在处理的问题是:
查找在给定特定范围内平方和的平方和是否为理想平方. 因此,如果范围是(1..10),您将获得每个数字的因数(所有因数为1,所有因数为2,所有因数为3等等.)将那些因数平方,然后将它们加在一起.最后检查该和是否是一个完美的平方.
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.
由于解决方案太慢,我无法进行重构/优化.
I am stuck on refactoring/optimization because my solution is too slow.
这是我想出的:
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这是我将在方法中放入的示例:
This is an example of what I would put in the method:
list_squared(1, 250)然后,期望的输出将是一个数组数组,每个数组包含一个数字,该数字的平方和为平方和以及平方和:
And then the desired output would be an array of arrays with each array containing the number whose sum of squared factors was a perfect square and the sum of those squared factors:
[[1, 1], [42, 2500], [246, 84100]]推荐答案
我将首先介绍一些辅助方法(factors和square?),以使您的代码更具可读性.
I would start by introducing some helper methods (factors and square?) to make your code more readable.
此外,我将减少范围和数组的数量以提高内存使用率.
Furthermore, I would reduce the number of ranges and arrays to improve memory usage.
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| primesbination(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) endpact end list_squared(1, 250)范围较窄(最高为250)的基准测试仅显示了较小的改进:
A benchmark with a narrow range (up to 250) shows only a minor improvement:
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)的基准测试显示出比原始实现更好的性能:
But a benchmark with a wider range (up to 10000) shows a much better performance than the original implementation:
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越大,与原始实现相比,我的代码执行得越好...
tl;dr: The bigger the N the better my code performs compared to the original implementation...
更多推荐
寻找完美平方算法的优化
发布评论