R中的堆栈类-更简洁的东西

Question

R有没有一个你不需要自己编码的堆栈？

从字面上讲，我只是想从CS102中得到一些东西。

我写了下面的代码，它工作得很好。但我更希望有其他更通用、更可靠的东西。

这门语言有什么用吗？或者一些包含所有常用算法的包，比如队列、树等等？

####################################################################################################
# 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

没有真正回答您的问题，但(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次/秒开始下降到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的向量运算的算法。

Answer 2

在CRAN上曾经有一个“容器”包实现了这些东西，但它似乎在几年前就已经死亡了：

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

你可以检查一下旧的源代码，也许让它复活，然后把它当作维护者？尽管这可能很有趣，因为其中很大一部分是没有明显来源的java jar文件。这就解释了为什么它会被拉出来。创建自己的网站可能会更容易。

否则，我很难找到实现。我知道我在很多年前也写过一个堆栈类。