루프 제거에 대한 조언

Question

3n + 1 문제 (일명 '놀라운 번호'및 다양한 다른 것들)와 함께 작동하는 프로그램을 작성했습니다. 하지만 이중 루프가 있습니다. 어떻게 벡터화 할 수 있을까요?

코드는

count <- vector("numeric", 100000) 
L <- length(count) 

for (i in 1:L) 
{ 
x <- i 
    while (x > 1) 
    { 
    if (round(x/2) == x/2) 
    { 
    x <- x/2 
    count[i] <- count[i] + 1 
    } else 
    { 
    x <- 3*x + 1 
    count[i] <- count[i] + 1 
    } 
    } 
} 

감사합니다!

Answer 1

x의 값을 반복해야하므로 실제로 이것을 벡터화 할 수 없습니다. 어떤 점에서, R은 x의 각 값을 차례로 처리해야합니다. 동일한 이름의 패키지에서 아마도 foreach을 사용하여 개별 CPU 코어에서 계산을 실행하여 작업 속도를 향상시킬 수 있습니다.

그렇지 않으면

, (이 당신의 루프를 숨기고), 예를 들어 함수로 루프의 본체를 포장 :

wonderous <- function(n) { 
    count <- 0 
    while(n > 1) { 
     if(isTRUE(all.equal(n %% 2, 0))) { 
      n <- n/2 
     } else { 
      n <- (3*n) + 1 
     } 
     count <- count + 1 
    } 
    return(count) 
} 

을하고 당신이의 기능을 실행하는 데 sapply()을 사용할 수 있습니다

> sapply(1:50, wonderous) 
[1] 0 1 7 2 5 8 16 3 19 6 14 9 9 17 17 
[16] 4 12 20 20 7 7 15 15 10 23 10 111 18 18 18 
[31] 106 5 26 13 13 21 21 21 34 8 109 8 29 16 16 
[46] 16 104 11 24 24 

또는 자체가 당신에게서이의 더를 숨기는 기능이다 wonderous의 벡터화 된 버전을 반환 Vectorize를 사용할 수 있습니다 : 숫자 집합

> wonderousV <- Vectorize(wonderous) 
> wonderousV(1:50) 
[1] 0 1 7 2 5 8 16 3 19 6 14 9 9 17 17 
[16] 4 12 20 20 7 7 15 15 10 23 10 111 18 18 18 
[31] 106 5 26 13 13 21 21 21 34 8 109 8 29 16 16 
[46] 16 104 11 24 24 

나는 지금까지 표준 R 도구를 사용할 수 있다고 생각합니다. @Martin Morgan은 이에 R의 벡터화 된 능력을 사용하는 문제를 해결하는 독창적 인 방법으로 이보다 훨씬 더 잘할 수 있음을 보여줍니다.

Answer 2

나는 알고리즘을 반복 할 때마다 i 번째 요소가 값이되는 벡터 x를 만들어 이것을 'inside-out'으로 바꾸었다. 그 결과

f1 <- function(L) { 
    x <- seq_len(L) 
    count <- integer(L) 
    while (any(i <- x > 1)) { 
     count[i] <- count[i] + 1L 
     x <- ifelse(round(x/2) == x/2, x/2, 3 * x + 1) * i 
    } 
    count 
} 

이것은 (a) 추적 (IDX 통해) 재생에 여전히 그 값 (B)의 불필요한 동작을 방지 등을 최적화 할 수

비교적 알기이다 ifelse는 모든 값에 대한 모든 인수를 평가 x, x/2는 두 번 평가됩니다. F0으로

f2 <- function(L) { 
    idx <- x <- seq_len(L) 
    count <- integer(L) 
    while (length(x)) { 
     ix <- x > 1 
     x <- x[ix] 
     idx <- idx[ix] 
     count[idx] <- count[idx] + 1L 
     i <- as.logical(x %% 2) 
     x[i] <- 3 * x[i] + 1 
     i <- !i 
     x[i] <- x[i]/2 
    } 
    count 
} 

는 비틀기 3 홀수 값을 업데이트

> L <- 10000 
> system.time(ans0 <- f0(L)) 
    user system elapsed 
    7.785 0.000 7.812 
> system.time(ans1 <- f1(L)) 
    user system elapsed 
    1.738 0.000 1.741 
> identical(ans0, ans1) 
[1] TRUE 
> system.time(ans2 <- f2(L)) 
    user system elapsed 
    0.301 0.000 0.301 
> identical(ans1, ans2) 
[1] TRUE 

원문 함수 I 가지고 * X [I] + 1 후 수행 두 무조건

x[i] <- 3 * x[i] + 1 
count[idx[i]] <- count[idx[i]] + 1L 
x <- x/2 
count[idx] <- count[idx] + 1 

으로 나누기 F3로이 (F2 오늘 아침에 느린 이유는 확실하지!) 나는

> system.time(ans2 <- f2(L)) 
    user system elapsed 
    0.36 0.00 0.36 
> system.time(ans3 <- f3(L)) 
    user system elapsed 
    0.201 0.003 0.206 
> identical(ans2, ans3) 
[1] TRUE 

,369를 얻을 수와

2 단계 나누기 단계에서 더 큰 단계를 수행 할 수있는 것처럼 보입니다. 예를 들어, 8은 2^3이므로 3 단계 (계산에 3을 더함)를 완료하고 20을 완료 할 수 있습니다. 2^2 * 5 그래서 우리는 두 단계를 취하여 다음 반복을 5 단계로 진행할 수 있습니다. 구현?

Answer 3

다른 접근법은 빈번히 낮은 숫자를 다시 인식하므로 기억하지 않고 재 계산 비용을 절약하십시오.

> L <- 100 
> vals <- seq_len(L) 
> system.time({ f <- memo_f(); memo1 <- sapply(vals, f) }) 
    user system elapsed 
    0.018 0.000 0.019 
> system.time(won <- sapply(vals, wonderous)) 
    user system elapsed 
    0.921 0.005 0.930 
> all.equal(memo1, won) ## integer vs. numeric 
[1] TRUE 

이 잘 병렬화하지 않을 수도 있습니다,하지만 어쩌면 그게 50 배 속도 향상과 필요는 없습니다 다음

memo_f <- function() { 
    e <- new.env(parent=emptyenv()) 
    e[["1"]] <- 0L 
    f <- function(x) { 
     k <- as.character(x) 
     if (!exists(k, envir=e)) 
      e[[k]] <- 1L + if (x %% 2) f(3L * x + 1L) else f(x/2L) 
     e[[k]] 
    } 
    f 
} 

? 또한 재귀가 너무 깊어 질 수도 있지만 재귀는 루프로 작성 될 수 있습니다 (어쨌든 더 빠름).