计算一定范围内的行数

html5 • • 问答

我有一个 data.table，其中包含一些值 ('value')、下限 ('min_val') 和上限 ('max_val')：

   | value | min_val | max_val |
1: | 94.001 | 94.00 | 94.02 |
2: | 94.002 | 94.00 | 94.03 |
3: | 94.003 | 94.01 | 94.04 |
4: | 95 | 94.98 | 95.02 |

我想计算行数，其中 value > min_val & value < max_val 对于来自整个 dt 的值的每一行。

   | value | min_val | max_val | count |
1: | 94.001 | 94.00 | 94.02 |  1       |   #(num of value(s) > 94.00 &  < 94.02)
2: | 94.002 | 94.00 | 94.03 |  2       |
3: | 94.003 | 94.01 | 94.04 |  2       |
4: | 95     | 94.98 | 95.02 |  1       |

我试过了，
dt[, count := nrow(dt[value > dt[min_val] & value < dt[max_val]])]但我走错了路。

回答

该OP已经透露，他的生产数据集包括81万行。不幸的是， r2evans 的基准测试仅使用了问题提供的 4 行样本数据集，而忽略了henrik 的建议。为了找到像 OP 这样的大型数据集的最佳方法，我发现运行具有不同和实际问题大小的基准测试以测量运行时间和内存消耗是值得的。

运行时间和内存消耗可能取决于

  1. 值的数量，
  2. 间隔数，
  3. 以及落入每个区间的值的数量。

第 1 项和第 2 项作为值的数量链接，间隔数由数据集中的行数给出。因此，我们可以改变两个大小参数，行n数和每个区间内的数值m。为了获得可重复和可预测的基准数据，基准数据集由

d <- data.table(value = as.double(seq(n)))[, min_val := value - m][, max_val := value + m][, count := -1L]

在n <- 4和 的情况下m <- 1 d成为

   value min_val max_val count
<num>   <num>   <num> <int>
1:     1       0       2    -1
2:     2       1       3    -1
3:     3       2       4    -1
4:     4       3       5    -1

为了为每个基准运行创建相等的条件，该count列预先分配了一些虚拟数据。

基准包括

  • henrik 的建议是在非等价自联接中聚合，
  • r2evans 的 3 个答案中的 3 种方法，
  • ThomasIsCoding的回答，
  • 亚历山大·莱昂纳德的回答

编辑：第三组基准运行比较

  • 非对等自联接中的 henrik聚合，以及
  • chinsoon12 的 Rcpp解决方案。

不幸的是，TarJae 的回答对我不起作用。

library(data.table)
library(bench)
library(ggplot2)
options(datatable.print.class = TRUE)
bm1 <- press(
n = 2^c(2, 10, 13),
m = 2^c(0, 9, 12),
{
d <- data.table(value = as.double(seq(n)))[, min_val := value - m][, max_val := value + m][, count := -1L]
mark(
henrik = {
d[ , count := d[d, on = .(value > min_val, value < max_val), .N, by = .EACHI]$N]
},
r2evans0 = {
d[, count := rowSums(outer(seq_len(.N), value, function(i, v) {min_val[i] < v & v < max_val[i];}))]
},
r2evans1 = {
d[, count := mapply(function(mi,ma) sum(mi < value & value < ma), min_val, max_val)]
},
r2evans2 = {
d[, count := rowSums(outer(min_val, d$value, `<`) &
outer(max_val, d$value, `>`)),
by = .(g = seq_len(nrow(d)) %/% 100)]
},
Thomas = {
d[, count := colSums(outer(value, min_val, ">") & outer(value, max_val, "<"))]
},
Alexandre = {
d[, count := lapply(
# seq.int(1, nrow(d)),
seq_len(nrow(d)),
function(i) sum(d[, value] > d[i, min_val] & d[, value] < d[i, max_val])
)]
},
min_iterations = 3
)
}
)
autoplot(bm1)

请注意对数时间刻度。

该图表表明

  • Alexandre 的方法比任何其他解决方案都要慢一个数量级（并且可能会从进一步运行中省略），
  • 随着行数的增加，n亨里克的方法变得并驾齐驱r2evans1（值得进一步研究），
  • 每个间隔中的值数量m似乎对运行时间没有影响或影响很小。

后者可以通过更改方面并绘制m一个方面不同方面的中值时间来验证：

ggplot(bm1) +
aes(x = median, y = expression, color = as.factor(m)) +
geom_point() +
facet_wrap(vars(n))

在下面的下一个图表中，绘制mem_alloc而不是median时间表明

  • m 对内存分配没有影响（有一个例外），
  • 对于 large n，henrik 的方法比任何其他方法需要更少的内存：

请注意对数刻度。

第二组基准测试

根据之前的结果，下一组基准测试只改变大小参数，n而m保持不变。Alexandre 的方法被省略，因为它太慢了。

n从2^10(1024) 到2^14(16384) 变化m = 1.0。不幸的是，n = 2^15由于我的电脑内存不足，运行被中止。

autoplot(bm2)

henrik 的方法在2^14(16384) 行情况下的速度方面处于领先地位。

为了确定这是否表明趋势，运行时间与问题大小的n关系由下式绘制

ggplot(bm2) +
aes(x = n, y = median, color = expression, group = attr(expression, "description"),
label = ifelse(n == max(n), attr(expression, "description"), "")) +
geom_point() +
geom_smooth(method = "lm", se = FALSE) +
scale_x_continuous(trans = scales::log2_trans(), expand = expansion(mult = c(0.05, 0.1))) +
ggrepel::geom_label_repel(direction = "y", nudge_x = 1000)

henrik 的方法似乎有很高的开销，但随着问题规模的增加而获得速度优势。

同样在内存分配方面，henrik在非等自连接中聚合的方法似乎比其他方法需要的内存要少得多。更重要的是，内存分配随问题大小增加的陡峭程度较低，这表明当可用计算机内存是一个限制因素时，这种方法可以处理更大的问题。

编辑：第三组基准测试

这组基准测试将henrik 在非等价自联接中的聚合与chinsoon12 的新Rcpp解决方案进行了比较。

由于这两种方法的内存占用要小得多，在我的 Windows PC 上2^18达到16 GB 内存限制之前，问题大小可以增加到(262144) 行。

library(Rcpp)
bm4 <- press(
n = 2^(10:18),
{
m <- 1.
d <- data.table(value = as.double(seq(n)))[, min_val := value - m][, max_val := value + m][, count := -1L]
mark(
henrik = {
d[ , count := d[d, on = .(value > min_val, value < max_val), .N, by = .EACHI]$N]
},
chinsoon = {
cppFunction("IntegerVector inrange(NumericVector v, NumericVector minv, NumericVector maxv) {
int n = v.size();
IntegerVector res(n);
for (int r=0; r<n; r++) {
for (int i=0; i<n; i++) {
if (v[i] > minv[r] && v[i] < maxv[r]) {
res[r]++;
}
}
}
return res;
}")
d[, count := inrange(value, min_val, max_val)]
},
min_iterations = 3
)
}
)

接下来的两个图表分别显示了运行时间的中位数和内存分配与问题大小的关系。（请注意对数刻度）：

n = 2^18(262144) 的结果：

setDT(bm4)[n == 2^18, .(expression = unique(attr(expression, "description")),
n, median, mem_alloc)]

   expression      n       median     mem_alloc
<char>  <num> <bench_time> <bench_bytes>
1:     henrik 262144       17.47s       12.14MB
2:   chinsoon 262144        1.03m        2.06MB

显然，chinsoon 的方法对于高达2^16(65536) 的问题大小更快，而 henrik 的方法对于更大的问题大小更快（并且似乎具有更线性的时间行为）。对于问题大小n = 2^18，henrik 的方法几乎比 chinsoon 的方法快 4 倍。

另一方面，henrik 的方法分配的内存比 chinsoon 的多得多。对于问题大小n = 2^18，henrik 的方法分配的内存比 chinsoon 的方法多 6 倍。显然，这个比率随着问题规模的增加而保持不变。

因此，根据问题的大小，在速度（henrik 的方法）和内存要求（chinsoon 的方法）之间存在权衡。你的旅费可能会改变。

我们可以尝试outer这样的

> setDT(df)[, count := colSums(outer(value, min_val, ">") & outer(value, max_val, "<"))][]
value min_val max_val count
1: 94.001   94.00   94.02     3
2: 94.002   94.00   94.03     3
3: 94.003   94.01   94.04     0
4: 95.000   94.98   95.02     1

数据

> dput(df)
structure(list(value = c(94.001, 94.002, 94.003, 95), min_val = c(94,
94, 94.01, 94.98), max_val = c(94.02, 94.03, 94.04, 95.02)), class = "data.frame", row.names = c(NA,
-4L))
以上是计算一定范围内的行数的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>