R의 스택 클래스 - 좀 더 간결한

Question

R에는 자신을 코딩 할 필요가없는 스택이 있습니까?

는 말 그대로, 난 그냥 아래의 코드를 쓴 바로 CS (102)

에서 뭔가를 원하고, 그것을 잘 작동합니다. 그러나 나는 차라리 보편적이고 입증 된 다른 것을 가지고 싶습니다.

언어에 뭔가가 있습니까? 또는 대기열, 나무 등과 같은 모든 일반적인 알고리즘의 일부 패키지는 무엇입니까?

#################################################################################################### 
# Stack.R - Implments a generalized stack. Uses Reference Classes since we need mutability. 
#################################################################################################### 

Stack <- setRefClass("Stack", 
    fields = list(
     vStack = "vector", 
     nTop = "numeric" 
    ), 
    methods = list(
     initialize = function() { 
      nTop <<- 1 
     }, 
     push = function(nItem) { 
      vStack <<- c(vStack, nItem) 
      nTop <<- nTop + 1 
      vStack[nTop-1] 
     }, 
     pop = function() { 
      if (nTop == 1) return(NULL) 
      nItem <- vStack[nTop-1] 
      nTop <<- nTop - 1 
      vStack <<- vStack[1:nTop-1] 
      nItem 
     }, 
     top = function() { 
      vStack[nTop-1] 
     } 
    ) 
) 

# StackTest <- function() { 
#  
#  say("Starting...") 
#  s <- Stack() 
#  say(s$push(1), " {push}") 
#  say(s$push("Hello"), " {push}") 
#  say(s$push(2), " {push}") 
#  say(s$push("World"), " {push}") 
#  say(s$push(3), " {push}") 
#  say(s$top(), " {top}") 
#  say(s$top(), " {top}") 
#  say(s$pop(), " {pop}") 
#  say(s$pop(), " {pop}") 
#  say(s$pop(), " {pop}") 
#  say(s$pop(), " {pop}") 
#  say("Finished.") 
#  
# } 
# 
# StackTest() 

Answer 1

이 이런 일을 구현 크랑에 '컨테이너'패키지로 사용하지만, 몇 년 전 사망 한 것으로 보인다

ftp://www.r-project.org/pub/R/web/packages/Containers/index.html

당신은 기존의 소스를 확인할 수 있습니다 어쩌면 그것을 부활시키고 그것을 유지 자로 삼을 것인가? 그것의 큰 덩어리가 명백한 소스가없는 자바 jar 파일이라는 점을 감안하면 재미있을 지 모르지만. 왜 그것이 뽑혔는지 설명합니다. 아마 당신 자신의 것을 시작하는 것이 더 쉽습니다.

그렇지 않으면 구현을 찾는 데 어려움이 있습니다. 나는 몇 년 전 스택 클래스를 썼다는 것을 안다.

Answer 2

(a) 참조 클래스는 메모리 관리를 변경하여 복사가 적어 지지만 다른 참조 기반 구현에 비해 성능이 반드시 좋은 것은 아닙니다. (b) vStack <<- c(vStack, nItem)에있는 "복사 및 추가"패러다임은 매우 저조합니다. 여기에 약간의 시세 기능 처리량

ticker = function(s) { 
    i = 0 
    t0 = Sys.time() 
    while (i < 1000000) { 
     s$push(i) 
     i <- i + 1 
     if (i %% 10000 == 0) 
      print(i/as.numeric(Sys.time() - t0)) 
    } 
} 

시작 떨어지는 3,800 운영/s 속도의 2,700에 :

> ticker(Stack()) 
[1] 3784.634 
[1] 3546.138 
[1] 3429.046 
[1] 3303.904 
[1] 3192.252 
[1] 3090.162 
[1] 3000.161 
[1] 2908.317 
[1] 2826.459 
[1] 2744.961 
^C 

여기에 훨씬 더 높은 초기와 지역 환경

s = local({ 
    v = numeric() 
    list(push=function(elt) v <<- c(v, elt), 
     val=function() v) 
}) 

를 사용하여 불완전한 구현입니다 처리량 및 "복사 및 추가"전략의 한계가 훨씬 더 분명 해졌습니다. 여기

> ticker(s) 
[1] 67933.63 
[1] 41231.02 
[1] 29095.23 
[1] 22347.02 
[1] 18274.56 
[1] 14007.66 
[1] 12436.16 
[1] 11122.1 
[1] 10034.59 
[1] 9123.754 
^C 

함수 호출

stack <- function(type="numeric", length=1000L) { 
    v <- vector(type, length) 
    i <- 1L 
    list(push=function(elt) { 
     if (i == length(v)) 
      length(v) <<- 1.6 * length(v) 
     v[[i]] <<- elt 
     i <<- i + 1L 
    }, val=function() v[seq_len(i - 1L)]) 
} 

로 구현 같은 지역 환경의 접근 방식을 채택는 "미리 할당 및 채우기를"전략 그리고 그것은 성능을

> ticker(stack()) 
[1] 155448.8 
[1] 170315.3 
[1] 174391.1 
[1] 177424.6 
[1] 179275.5 
[1] 180605.6 
[1] 179693.4 
[1] 180258.7 
[1] 180681 
[1] 181290.1 
^C 

같아요 개선 것 이 모든 것들이 원래의 요점을 강조하고, 바퀴를 다시 발명하지 않고 Stack 구현을 원한다고 생각하고, 아마도 @CarlWhitthoft의 암묵적인 점은 생각보다 나을 수 있다고 생각합니다. R의 벡터 연산을 이용하는 알고리즘의 사용.