3

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

2 回答 2

5

没有真正回答您的问题，但是（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 向量操作的算法。

于 2013-09-07T22:16:48.013 回答
1

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

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

您可以查看旧的源代码，也许可以将其复活并作为维护者使用？虽然这可能很有趣，因为其中很大一部分是没有明显来源的 java jar 文件。这就解释了为什么它被拉了。可能更容易开始自己的。

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

于 2013-09-07T21:44:16.560 回答