4

以下の問題に対するより迅速な解決策を探しています。小さな例で問題を説明し、大きなデータをシミュレートするコードを提供します。これがこの質問のポイントです。私の実際の問題のサイズは、リストの長さ = 100 万エントリです。

以下に示すように、2つのリストがあるとします。

x <- list(c(82, 18), c(35, 50, 15))
y <- list(c(1,2,3,55,90), c(37,38,95))

x と y のプロパティ:

  • リストの各要素のx合計は常に 100 になります。
  • の各要素はy常にソートされ、常に 1 から 100 の間になります。

問題：

さて、私が欲しいのはこれです。とをとっx[[1]]てy[[1]]、1) <= 82 および 2) > 82 および <= 100 である数字の数を見つけたいと思いますy[[1]]。これは c(4, 1) になります。数字 <= 82c(1,2,3,55)は83と100はc(90). x[[2]]とy[[2]]、c(0, 2, 1)についても同様です。つまり、答えは次のようになります。

[[1]]
[1] 4 1

[[2]]
[1] 0 2 1

これがまだ不明な場合はお知らせください。

100 万エントリのシミュレートされたデータ

set.seed(1)
N <- 100
n <- 1e6
len <- sample(2:3, n, TRUE)

x <- lapply(seq_len(n), function(ix) {
    probs <- sample(100:1000, len[ix])
    probs <- probs/sum(probs)

    oo <- round(N * probs)
    if (sum(oo) != 100) {
        oo[1] <- oo[1] + (100 - sum(oo))
    }
    oo
})

require(data.table)
ss <- sample(1:10, n, TRUE)
dt <- data.table(val=sample(1:N, sum(ss), TRUE), grp=rep(seq_len(n), ss))
setkey(dt, grp, val)
y <- dt[, list(list(val)),by=grp]$V1

私がこれまでに行ったこと：

使用mapply（遅い）：

最初にand （2つのリストを使用rankした明らかな選択）を使用することを考え、これを試しました：ties.method="first"mapply

tt1 <- mapply(y, x, FUN=function(a,b) { 
    tt <- rank(c(a, cumsum(b)), ties="first")[-(1:length(a))]; c(tt[1]-1, diff(tt)-1)
})

これは問題なく機能しますが、1M エントリではかなりの時間がかかります。rankコンピューティングのオーバーヘッドとdiffそれが何度も追加されると思います。これには241 秒かかります。

したがって、 「グループ」列を使用してソートすることで、andrankの使用法を克服することにしました。以下に示す、より長いがはるかに高速なソリューションを思いつきました。diffdata.table

使用data.table（高速）：

xl <- sapply(x, length)
yl <- sapply(y, length)
xdt <- data.table(val=unlist(x, use.names=FALSE), grp=rep(seq_along(xl), xl), type = "x")
xdt[, cumval := cumsum(val), by=grp]
ydt <- data.table(val=unlist(y, use.names=FALSE), grp=rep(seq_along(yl), yl), type = "y")
tt2 <-rbindlist(list(ydt, xdt[, list(cumval, grp, type)]))
setkey(tt2, grp, val)
xdt.pos <- which(tt2$type == "x")
tt2[, type.x := 0L][xdt.pos, type.x := xdt.pos]
tt2 <- tt2[xdt.pos][tt2[, .N, by = grp][, N := cumsum(c(0, head(N, -1)))]][, sub := type.x - N]
tt2[, val := xdt$val]

# time consuming step
tt2 <- tt2[, c(sub[1]-1, sub[2:.N] - sub[1:(.N-1)] - 1), by = grp]
tt2 <- tt2[, list(list(V1)),by=grp]$V1

これには26 秒かかります。つまり、約 9 倍高速です。このような 100 万個の要素を 5 ～ 10 個再帰的に計算する必要があるため、さらに高速化できるかどうか疑問に思っています。ありがとうございました。

4

2 に答える 2

0

これは約 25% 高速ですが、リストではなくマトリックスとして出力します。appy/sappy を使用して、リストで動作させることができます (リストとして保存すると速度が低下していました)。

c=matrix(0,length(x),100)
for(j in 1:length(x)){
  a=-1
  b=0
  for(i in 1:length(x[[j]])){
    a=b
    b=b+x[[j]][i]
    c[j,i]=sum((a<=y[[j]])*(y[[j]]<=b))
  }
}
于 2013-07-19T14:59:10.960 に答える