r - R中的堆栈类-更简洁

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()

最佳答案

(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))
    }
}

从3800次操作/秒开始的吞吐量下降到2700次:

> 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向量向量的算法。