優化查找和計算紅寶石中的適當因子

Question

此代碼需要運行在7000ms以下或超時，我正在嘗試學習ruby，所以我在這裏看看是否有人有任何想法可以優化此代碼。或者，如果您可以讓我知道此代碼中的哪些功能花費最多的時間，那麼我可以專注於最能做到最好的部分。

要解決的問題是，你必須告訴任何棕褐色的除數是奇數還是偶數。

對於n = 12的除數[1,2,3,4,6,12] - '偶數'

對於n = 4的除數是[1,2,4] - '奇'

任何幫助，非常感謝，

謝謝。

def oddity(n) 
    div(n) % 2 == 0 ? (return 'even'): (return 'odd') 
end 

def div(num) 
    divs = [] 
    (1..num).each{|x| if (num % x == 0) then divs << x end} 
    return divs.length 
end 

Answer 1

這裏的關鍵發現是，你需要除數僅數量，而不是除數自己。因此，一個相當簡單的解決方案是將數字分解爲素數，並檢查我們可以形成多少種組合。

require 'mathn' 

def div(num) 
    num.prime_division.inject(1){ |prod, n| prod *= n[1] + 1 } 
end 

prime_division返回對，其中第一個是黃金，第二是它的指數的列表。例如：

12.prime_division 
=> [[2, 2], [3, 1]] 

我們只需乘以指數，每增加1，即可解釋未採用此素數的情況。

Answer 2

你可以通過優化你的算法來解決這個問題。

您不必檢查您正在檢查的號碼以下的所有號碼。把你的號碼分成它的主要組成部分就足夠了。那麼確定有多少可能的因子是組合的簡單問題。

一種方式來獲得所有主要成分可能是：

PRIME_SET = [2,3,5,7,11,13,17,19] 
def factorize(n) 
    cut_off = Math.sqrt(n) 
    parts = [] 
    PRIME_SET.each do |p| 
    return parts if p > cut_off 
    if n % p == 0 
     n = n/p 
     parts << p 
     redo 
    end 
    end 
    raise 'To large number for current PRIME_SET' 
end 

然後計算出可能的數量可以在許多不同的方式來完成，有可能這樣做，甚至沒有計算它們的方法。但這是一個天真的實現。

def count_possible_divisors(factors) 
    divisors = Set.new 
    (1..factors.length-1).each do |i| 
    factors.combination(i).each do |comb| 
     divisors.add(comb.reduce(1, :*)) 
    end 
    end 
    divisors.length + 2 # plus 2 for 1 and n 
end 

這應該會導致比您所做的更少的工作。但是對於大數量來說，這是一項艱鉅的任務。

Answer 3

如果你想堅持你的算法，這裏是一個優化。

def div(num) 
    oddity = false 
    (1..num).each{|x| if (num % x == 0) then oddity = !oddity end} 
    oddity ? "odd" : "even" 
end 

Answer 4

由於性能是一個問題，我們來比較一下OP的解決方案與@standelaune's和@dimid's。

require 'prime' 
require 'fruity' 

n = 100_000 
m = 20 
tst = m.times.map { rand(n) } 
    #=> [30505, 26103, 53968, 24108, 78302, 99141, 22816, 67504, 10149, 28406, 
    # 18294, 92203, 73157, 5444, 24928, 65154, 24850, 64219, 68310, 64951] 

def op(num) # Alex 
    divs = [] 
    (1..num).each { |x| if (num % x == 0) then divs << x end } 
    divs.length 
end 

def test_op(tst) # Alex 
    tst.each { |n| op(n) } 
end 

def pd(num) # divid 
    num.prime_division.inject(1){ |prod, n| prod *= n[1] + 1 } 
end 

def test_pd(tst) #divid 
    tst.each { |n| nfacs_even?(n) } 
end 

def div(num) # standelaune 
    oddity = false 
    (1..num).each{|x| if (num % x == 0) then oddity = !oddity end} 
    oddity ? "odd" : "even" 
end 

def test_div(tst) # standelaune 
    tst.each { |n| div(n) } 
end 

compare do 
    _test_op { test_op tst } 
    _test_div { test_div tst } 
    _test_pd { test_pd tst } 
end 

Running each test 16 times. Test will take about 56 seconds. 
_test_pd is faster than _test_div by 480x ± 100.0 
_test_div is similar to _test_op 

我不會感到驚訝的是divid的方法吸食他人，爲prime_division用途（實例）的默認主要發電機，Prime::Generator23，也就是說發生器在C語言編寫的，並相對於Prime子類中的其他發生器而言是快速的。