爲歐拉項目12優化簡單r代碼

歐拉項目問題12的想法是找到具有指定數量除數的最小三角形數（https://projecteuler.net/problem=12）。作爲一種嘗試，以解決這個問題，我寫了下面的代碼：爲歐拉項目12優化簡單r代碼

# This function finds the number of divisors of a number and returns it. 
FUN <- function(x) { 
    i = 1 
    lst = integer(0) 
    while(i<=x) 
    { 
     if(x %% i ==0) 
     { 
      lst = c(lst, i) 
     } 
     i = i +1 
    } 

    return(lst) 
}

和

n = 1 
i=1 
while (length(FUN(n))<500) 
{ 
    i = i + 1 
    n = n + i 
}

此代碼產生了一些較小的測試案例正確答案：length(FUN(n))<4會產生6和length(FUN(n))<6會產生28。

但是，這個簡單的代碼需要24小時才能運行（並且仍在運行）length(FUN(n))<500。我知道一個數字有500個因子，這個數字可能非常大，但我想知道爲什麼它需要很長時間才能運行因此。

來源

2017-08-31 user101998

您正逐漸增加向量元素，由於內存分配，這在R中本質上很慢。通過向量化操作來擺脫'FUN'中的'while'循環，以避免部分問題，儘管這仍然會留下外部循環。對於前10個三角形數字來說，速度要快，但速度並不快（而且整理一下）：'三角形< - data.frame（number = cumsum（1:10））; $ n_factors < - sapply（三角形$ number，function（x）{sum（x %% seq.int（x）== 0）}）;三角形' – alistaire

閱讀[這篇文章]（https://stackoverflow.com/questions/6424856/r-function-for-returning-all-factors） – Mist

@alistaire你的函數可能是'function（x）{sum （x %% seq.int（sqrt（x））== 0）* 2}）'。會快得多，但平方的數字會比實際應得的多一個因素。只有一個問題，如果你找到一個正好有500個因子的數字。 – Mist

您FUN是太低效了這項任務。作爲第一三角號與通過所有這些數字的75000000個FUN運行值第一萬二千以上...迭代執行的數量幾乎是

12000 * 75000000/2 = 450 * 10^9

這是除了R的相對慢的換顯然更循環可以在合理的時間範圍內完成。

取而代之，您可以應用號碼中的divisors函數，該函數使用素數因子分解。下面的代碼需要約5-6秒（在我的機器上）才能找到三角形數字。

library(numbers) 

t <- 0 
system.time(
    for (i in 1:100000) { 
     t <- t + i 
     d <- length(divisors(t)) 
     if (d > 500) { 
      cat(i, t, d, '\n') 
      break 
     } 
    } 
) 
## 12375 76576500 576 
## user system elapsed 
## 5.660 0.000 5.658

代替計算第i個三角形的數目，在這裏i被添加到最後一個三角形數量。節省的時間很少。

來源

2017-08-31 09:14:31

這太神奇了。我需要查看'divisors（）'和'primeFactors（）'和'gmp'包並瞭解詳細信息。 – user101998

哇！來自我的投票。 – Mist

這裏是我的嘗試：

library(gmp) 
library(plyr) 

get_all_factors <- function(n) 
{ 
    prime_factor_tables <- lapply(
    setNames(n, n), 
    function(i) 
    { 
     if(i == 1) return(data.frame(x = 1L, freq = 1L)) 
     plyr::count(as.integer(gmp::factorize(i))) 
    } 
) 
    lapply(
    prime_factor_tables, 
    function(pft) 
    { 
     powers <- plyr::alply(pft, 1, function(row) row$x^seq.int(0L, row$freq)) 
     power_grid <- do.call(expand.grid, powers) 
     sort(unique(apply(power_grid, 1, prod))) 
    } 
) 
} 

for (i in 99691200:100000) { 
    if (length(get_all_factors(i)[[1]])>500) print(paste(i, length(get_all_factors(i)[[1]]))) 
    if (i %% 100000 == 0) print(paste("-",i,"-")) 
}

讓它只要你可以不屑運行...

來源

2017-08-31 06:54:45 Mist

謝謝你的代碼！但我只能選擇一個答案.. – user101998

爲歐拉項目12優化簡單r代碼

回答

相關問題