Czy istnieje metoda bardziej wydajna niż podczas pętli dla czegoś, co wymaga sprawdzania warunkowego?

Question

Mam problem polegający na tym, że zawijam pętlę wokół kodu, który moim zdaniem może być wektoryzowany efektywnie. Jednak na każdym etapie mój stan zatrzymania zależy od wartości na tym etapie. Rozważmy ten przykład jako model reprezentacyjny mojego problemu:
Generuj zmienne losowe N (0,1) za pomocą rnorm(), dopóki nie pobierzesz próbki o wartości większej niż dowolna wartość, k.

EDYCJA: Ostrożność mojego problemu, omówiona w komentarzach, polega na tym, że nie mogę wiedzieć, a priori, dobrego przybliżenia liczby próbek, które należy wykonać przed moim stanem zatrzymania.

Jedno podejście:

1. Stosując while pętlą na próbki odpowiednie wielkości normalnej losowej wektorów (na przykład, rnorm(50) próbki 50 standardowych normalne w czasie, lub rnorm(1) jeśli k oznacza blisko do zera). Sprawdź ten wektor, aby sprawdzić, czy obserwacje są większe niż k.

2. Jeśli tak, zatrzymaj i zwróć wszystkie poprzednie wartości. W przeciwnym razie, połączyć wektor z etapu 1 z nowym wektorem można zrobić powtarzając Krok 1.

Inne podejście byłoby określić szereg całkowicie overkill losowych rysuje dla tej danej k. Może to oznaczać, że jeśli k = 2, próbuj 1000 normalnych zmiennych losowych za pomocą rnorm(1000).

Wykorzystanie wektorowania, które R oferuje w drugim przypadku, daje szybsze wyniki niż wersja z pętlą w przypadkach, w których liczba przeskoków nie jest zbyt duża, ale w moim problemie nie mam dobrej intuicji wiele biegów muszę zrobić, więc musiałbym być konserwatywny.

Pojawia się następujące pytanie: Czy istnieje sposób wykonania wysoce wektoryzowanej procedury, np. Metoda 2, ale przy użyciu sprawdzania warunkowego, jak w przypadku metody 1? Czy małe wektorowe operacje, takie jak rnorm(50), są "najszybsze", biorąc pod uwagę, że wysoce wektoryzowana metoda jest szybsza, ale bardziej nieefektywna?

Answer 1

Oto implementacja mojej wcześniejszej sugestii: użyj swojego pierwszego podejścia, ale zwiększ liczbę nowych próbek między każdą iteracją, np. Zamiast 50 nowych próbek w każdej iteracji, pomnóż tę liczbę przez dwa z każdej iteracji: 50, następnie 100, 200, 400 itp

ze swoimi wielkość próbki po rozbieżnego geometrycznym, masz gwarancję, aby wyjść w „kilku” iteracji.

sample.until.thresh <- function(FUN, exit.thresh, 
           sample.start = 50, 
           sample.growth = 2) { 

    sample.size <- sample.start 
    all.values  <- list() 
    num.iterations <- 0L 

    repeat { 
     num.iterations <- num.iterations + 1L 
     sample.values <- FUN(sample.size) 
     all.values[[num.iterations]] <- sample.values 

     above.thresh <- sample.values > exit.thresh 
     if (any(above.thresh)) { 
     first.above <- match(TRUE, above.thresh) 
     all.values[[num.iterations]] <- sample.values[1:first.above] 
     break 
     } 

     sample.size <- sample.size * sample.growth 
    } 

    all.values <- unlist(all.values) 

    return(list(num.iterations = num.iterations, 
       sample.size = length(all.values), 
       sample.values = all.values)) 
} 

set.seed(123456L) 
res <- sample.until.thresh(rnorm, 5) 
res$num.iterations 
# [1] 16 
res$sample.size 
# [1] 2747703