2016-05-05 1 views
0

Ich versuche eine Funktion zu erstellen, die einen Vektor erstellt, in dem ein beliebiges Element NICHT die Summe irgendeiner Kombination anderer Elemente in der Liste ist (ohne Duplizierung).r Vektor von Nicht-Summen von Self-Items

Diese Funktion macht den Job aber ist ziemlich langsam ... irgendwelche hellen Gedanken, wie man es verbessert?

sum_fun <- function(k) 
{ 
    out_list <- c(2,3,4) 
    new_num <- 4 

    while(length(out_list) < k) 
    { 
    new_num <- new_num + 1 
    #Check if new_num can be written as a sum of the terms in out_list 
    new_valid <- T 
    for (i in 2:(length(out_list) - 1)){ 
     if (new_num %in% (apply(combn(out_list,i), FUN = sum, MAR = 2))) 
     { 
     new_valid <- F 
     break 
     } 
    } 

    if (new_valid) 
    { 
     out_list <- c(out_list, new_num) 
    } 

    } 
    return(out_list) 
} 

Antwort

0

Das war eine gute Frage. Ich habe einige Änderungen an Ihrer ursprünglichen Funktion vorgenommen und meine Funktion etwas schneller ausgeführt. Nebenbei bemerkt, wie viele suchen Sie?

Die Hauptidee ist, dass wir mehr Dinge nicht öfter berechnen sollten als wir unbedingt müssen. Ich denke, die for-Schleife verlangsamt wahrscheinlich etwas, plus, wie viele Spaltensummen wurden wiederholt? Wenn wir die Liste "dedupfen" können, können wir sie vielleicht schneller durchsuchen [reduzieren, wiederverwenden, recyceln :)].

sum_fun2 <- function(k) 
{ 
    out_list <- c(2,3,4) #dummy list 
    new_num <- 4 #dummy number 
    calc_big_sum <- T #calculate big sum on the first go 
    while(length(out_list) < k) 
    { 
    new_num <- new_num + 1 #dummy number to add 

    #calculate big sum, and then find unique values 
    if(calc_big_sum){ 
     big_sum<- unique(unlist(lapply(lapply(2:(length(out_list) - 1), 
            FUN = function(x) combn(out_list, m = x)), 
            FUN = function(y) apply(y, 2, sum)))) 
    } 

     if(new_num %in% big_sum){ 
     calc_big_sum = F #don't make it calculate the sum again 
     }else{ 
     out_list <- c(out_list, new_num) #add number to list 
     calc_big_sum = T #make it calculate a new sum 
     } 
    } 
    return(out_list) 
} 

> system.time(sum_fun2(10)) 
    user system elapsed 
    0.03 0.00 0.03 
> system.time(sum_fun(10)) 
    user system elapsed 
    1.30 0.00 1.27 
> system.time(sum_fun2(14)) 
    user system elapsed 
    3.35 0.07 3.47 
> system.time(sum_fun(14)) 
## I ended it 
Timing stopped at: 39.86 0 40.02 
+1

Vielen Dank !! Viel viel schneller. Aber ich merke, dass mein Problem für große k (100 oder höher) fast unlösbar wird. –

Verwandte Themen