Optimierung für die Suche nach perfekten-Square-Algorithmus

Question

Die question Ich arbeite an ist:

Finden die Summe der quadratischen Faktoren sind ein perfektes Quadrat einen bestimmten Bereich gegeben. Also, wenn der Bereich (1..10) war, würden Sie die Faktoren jeder Zahl erhalten (alle Faktoren für 1, alle Faktoren für 2, alle Faktoren für 3 usw.). Quadrieren Sie diese Faktoren und fügen Sie sie dann zusammen. Prüfen Sie abschließend, ob diese Summe ein perfektes Quadrat ist.

Ich bin auf Refactoring/Optimierung stecken, weil meine Lösung zu langsam ist. Hier

ist, was ich kam mit:

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 

Dies ist ein Beispiel dessen, was ich in der Methode setzen würde:

list_squared(1, 250) 

Und dann der gewünschte Ausgang würde ein Array von Arrays sein mit jedem Feld, das die Zahl enthält, deren Summe der quadrierten Faktoren ein perfektes Quadrat war, und die Summe dieser quadrierten Faktoren:

[[1, 1], [42, 2500], [246, 84100]] 

Answer 1

Ich würde damit beginnen, einige Hilfsmethoden (factors und square?) einzuführen, um Ihren Code lesbarer zu machen.

Außerdem würde ich die Anzahl der Bereiche und Arrays reduzieren, um die Speichernutzung zu verbessern.

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) 

Ein Benchmark mit einem engen Bereich (bis zu 250) zeigt nur eine geringfügige Verbesserung:

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) 

Aber ein Benchmark mit einem breiteren Spektrum (bis zu 10000) zeigt eine viel bessere Leistung als die Original-Implementierung:

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: Je größer die N desto besser führt meinen Code im Vergleich zum ursprünglichen Umset mentation ...

Answer 2

Eine Möglichkeit, es effizienter zu machen, ist die integrierte Ruby-Methode Prime::prime_division.

für eine beliebige Anzahl n, wenn prime_division ein Array gibt ein einzelnes Element enthält, wird dieses Element [n,1] und n wird sein prime gezeigt worden sind. Diese Primzahl hat die Faktoren n und 1, also muss anders behandelt werden als Zahlen, die nicht prim sind.

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]]} 

Diese Berechnung dauerte ungefähr 0,15 Sekunden.

Für i = 6174

(2**1) * (3**2) * (7**3) #=> 6174 

und

1*(2**2) + 2*(3**2) + 3*(7**2) #=> 169 == 13*13 

Answer 3

Der Trick, die Fragen häufig löst wie diese von Probedivision zu einem sieve wechseln ist. In Python (traurig):

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 

nächsten Optimierungs ist factor nur isqrt(n) zu Schritt Addieren der Quadrate Faktor in Paaren (z.B. 2 und i // 2).