1 
bucketIndex <- function(v, N){
  o <- rep(0, length(v))

  curSum <- 0
  index  <- 1

  for(i in seq(length(v))){
    o[i] <- index

    curSum <- curSum + v[i]
    if(curSum > N){
      curSum <- 0
      index <- index + 1
    }
  }

  o
}

> bucketIndex(c(1, 1, 2, 1, 5, 1), 3)
[1] 1 1 1 2 2 3

我想知道这个函数是否从根本上是不可矢量化的。如果是，是否有一些包来处理这个“类”函数，或者是唯一的选择（如果我想要速度）将它写为 ac 扩展？

4

3 回答 3

2

这是一个尝试（尚未到达bucketIndex！）：

  • 您的 

    curSum <- curSum + v[i]
if(curSum > N){
  curSum <- 0
  index <- index + 1
}

    几乎是 的整数除法%/%。cumsum (v)

  • 但不完全是，即使 v [i] > 几次N并且您从 1 开始，您的索引也只会增加 1。我们几乎可以通过转换为因子并返回整数来解决这个问题。

  • 但是，我想知道（从函数的名称）这种行为是否真的是有意的： 

    > bucketIndex (c(1, 1, 2, 1, 2, 1, 1, 2, 1, 5, 1), 3)
[1] 1 1 1 2 2 2 3 3 3 4 5
> bucketIndex (c(1, 1, 1, 2, 2, 1, 1, 2, 1, 5, 1), 3)
[1] 1 1 1 1 2 2 2 3 3 3 4

    即只是交换两个连续的条目v可能会导致结果中的最大值不同。

  • 另一点是您仅在导致总和为 > 的元素之后N才计数。这意味着结果应该在开头有一个额外的 1 并且应该删除最后一个元素。

  • curSum不管它射了多少，你都重置为 0 N。所以对于所有带有 的元素cumsum (v) > N，你需要减去这个值，然后寻找下一个cumsum (v) > N，依此类推。这减少了与您的for循环相关的循环迭代次数，但这是否会给您带来实质性的改进取决于v和 on N（或max (index)：length (v)比率）的条目。如果如您的示例中那样为 50%，我认为您不会获得可观的收益。除非他们之间至少有一个数量级，否则我会选择inline::cfunction.

于 2012-10-05T16:56:41.043 回答
0

我要在这里站出来，说答案是“不”。从本质上讲，您正在根据当前总和的结果更改总和。这意味着未来的计算取决于中间计算的结果，而向量化操作无法做到这一点。

于 2012-10-05T17:37:53.603 回答
0

我不认为这是完全可矢量化的，但@cbeleites 采用一种方法通过一次处理整个块（桶）来减少循环中的迭代次数。每次迭代都会查找累积和超过 的位置N，将索引分配到该范围，将累积和减少超出的任何值N，然后重复直到向量用尽。剩下的就是簿记（值的初始化和值的递增）。

bucketIndex2 <- function(v, N) {
    index <- 1
    cs <- cumsum(v)
    bk.old <- 0
    o <- rep(0, length(v))

    repeat {
        bk <- suppressWarnings(min(which(cs > N)))
        o[(bk.old+1):min(bk,length(v))] <- index
        if (bk >= length(v)) break
        cs <- cs - cs[bk]
        index <- index + 1
        bk.old <- bk
    }

    o
}

这与您的各种随机输入的功能相匹配：

for (i in 1:200) {
  v <- sample(sample(20,1), sample(50,1)+20, replace=TRUE)
  N <- sample(10,1)
  bi <- bucketIndex(v, N)
  bi2 <- bucketIndex2(v, N)
  if (any(bi != bi2)) {
    print("MISMATCH:")
    dump("v","")
    dump("N","")
  }
}
于 2012-10-05T17:38:49.797 回答