如何避免在爲行（n-1）添加行（n）進行隨機遊動時出現循環

Question

我模擬從座標（0,0）開始的隨機遊動。當我與一個循環做效果很好：

require(ggplot2) 
n <- 1000 #number of walks 

# first solution, w/ loop... works but is SLOOOW 
coord <- data.frame (x=0, y=0, step=0) #origin 
for (i in 1:n){ 
    dir <- sample(c("w", "e", "n", "s"), 1) #random direction 
    step <- sample(1:4, 1) #how far to go in each walk 
    startx <- coord[nrow(coord), 1] 
    starty <- coord[nrow(coord), 2] 
    endx <- ifelse (dir=="w", startx-step, ifelse(dir=="e", startx+step, startx)) 
    endy <- ifelse (dir=="n", starty+step, ifelse(dir=="s", starty-step, starty)) 
    newcoord <- data.frame (x=endx, y=endy, step=step) 
    coord <- rbind(coord, newcoord) 
} 
rw <- ggplot(coord, aes(x=x, y=y)) 
rw + geom_path() + 
    ggtitle(paste(n, "walks")) + 
    geom_point(aes(x=0, y =0), color="green", size=I(5)) + 
    geom_point(aes(x=endx, y =endy), color="red", size=I(5)) 

然而，其中n> 10,000它會非常慢，所以想避免循環和使用某種形式的「申請」，但不能弄清楚如何添加第n行和第n-1行的座標值。請幫忙，謝謝。

# second solution 
d <- data.frame(dir=sample(c("w", "e", "n", "s"), n, replace=T), step=sample(1:4, n, replace=T)) 
xy <- data.frame(x=0, y=0) 
x. <- data.frame(x=with(d, ifelse (dir=="w", -step, ifelse(dir=="e", step, 0)))) 
y. <- data.frame(y=with(d, ifelse (dir=="s", -step, ifelse(dir=="n", step, 0)))) 
x.y. <- cbind(x.,y.) 
xy <- rbind(xy, x.y.) 
head(xy) 
# ... stuck here 

Answer 1

我覺得你越來越接近了。如果您閱讀已發佈的評論，可以使其更快。因此，我建議不要看這個：

n=10000 
x.=sample(-4:4,n,rep=T) 
y.=sample(-4:4,n,rep=T) 
x=cumsum(x.) 
y=cumsum(y.) 

coord=data.frame(x,y) 

然後畫出你到底是怎麼做：

rw <- ggplot(coord, aes(x=x, y=y)) 
rw + geom_path() + 
    ggtitle(paste(n, "walks")) + 
    geom_point(aes(x=0, y =0), color="green", size=I(5)) + 
    geom_point(aes(x=startx, y =starty), color="red", size=I(5)) 

更新：繪圖速度很慢對於n大於10^5大。也許基礎圖形會更快。

update2：這幾乎和喬蘭的回答一樣慢/快。

Answer 2

嘎！希望這會進一步壓制出愚蠢的「for循環本來就很慢」的目標，這是對你的第一個版本的重新編譯，仍然使用for循環，這個循環比以前快了40倍以上。

我甚至沒有考慮過你的隨機遊走是否有意義。我的要點就是指出如何在保持原始代碼的結果的同時仍然使用「慢」循環來實現原始代碼的結果。

#My version 
foo <- function(n){ 
    coord <- matrix(NA,nrow = n,ncol = 3) #origin 
    coord[1,] <- c(0,0,0) 
    dir <- sample(c("w", "e", "n", "s"), n,replace = TRUE) #random direction 
    step <- sample(1:4, n,replace = TRUE) #how far to go in each walk 
    for (i in 2:n){ 
     startx <- coord[i-1, 1] 
     starty <- coord[i-1, 2] 
     endx <- ifelse (dir[i]=="w", startx-step[i], ifelse(dir[i]=="e", startx+step[i], startx)) 
     endy <- ifelse (dir[i]=="n", starty+step[i], ifelse(dir[i]=="s", starty-step[i], starty)) 
     coord[i,] <- c(endx,endy,step[i]) 
    } 
} 

#Your version  
foo2 <- function(n){ 
    coord <- data.frame (x=0, y=0, step=0) #origin 
    for (i in 1:n){ 
     dir <- sample(c("w", "e", "n", "s"), 1) #random direction 
     step <- sample(1:4, 1) #how far to go in each walk 
     startx <- coord[nrow(coord), 1] 
     starty <- coord[nrow(coord), 2] 
     endx <- ifelse (dir=="w", startx-step, ifelse(dir=="e", startx+step, startx)) 
     endy <- ifelse (dir=="n", starty+step, ifelse(dir=="s", starty-step, starty)) 
     newcoord <- data.frame (x=endx, y=endy, step=step) 
     coord <- rbind(coord, newcoord) 
    } 
} 


system.time(foo(10000)) 
    user system elapsed 
    0.353 0.001 0.353 
> system.time(foo2(10000)) 
    user system elapsed 
11.374 2.061 13.308 

所有我所做的是：

1. STOP。使用。 RBIND。並預先分配。
2. 切換到矩陣。
3. 移動sample呼叫超出循環。

Answer 3

data.table是快此類問題...

walk.dt.f<-function(n=10000L, stepsize=1L:4L) { 
    # lookup table with direction vector info 
    dir.dt<-data.table(dir=c("w", "e", "n", "s"), xdir=c(-1L,1L,0L,0L), ydir=c(0L,0L,1L,-1L), key="dir") 

    # initial position for random walk table 
    walk.ini.dt<-data.table(rowid=0L,dir="n",step=0L) 

    # generate table with random walk info 
    walk.dt<-rbindlist(list(data.table(rowid=1L:n, dir=sample(dir.dt[,dir],n,replace=T), step=sample(stepsize,n,replace=T)), walk.ini.dt)) 

    # join the two tables, and multiply the step info by the direction vectors 
    setkey(walk.dt,dir) 
    walk.dt[dir.dt,c("xstep","ystep"):=list(step*xdir,step*ydir)] 

    # update the key and reorder the rows 
    setkey(walk.dt,rowid) 

    # update the walk info table with the cumulative position 
    walk.dt[,c("x","y"):=list(cumsum(xstep),cumsum(ystep))] 

} 

system.time(walk.dt.f(10000L)) 
## user system elapsed 
## 0  0  0 

system.time(walk.dt.f(1e6L)) 
## user system elapsed 
## 0.25 0.00 0.25 

編輯：在（0,0）

Answer 4

設置起始位置既然你正在嘗試2 d隨機遊走，有4x4可能的位移。你可以用1到16的數字對它們進行編碼。但是爲了減少計算量並將這些編碼數字映射到方向和位移量，我玩了一個小技巧，我沒有用1:16編碼這些步驟，而是用c(-7:0,4:11)

d <- sample(c(-7:0,4:11),n,replace=T) 
delta <- d%%4+1 
dir <- d%/%4 
xd <- dir 
xd[xd%%2 ==0]=0 
yd <- dir 
yd[xd%%2 ==1]=0 
yd <- yd/2 
x=c(0,xd*delta) 
y=c(0,yd*delta) 
x=cumsum(x) 
y=cumsum(y) 

coords<-data.frame(x,y) 

該版本只使用矢量化操作，只有一點開銷。我認爲它接近於基於data.table的解決方案。