Seems the most sensible method is using a cartesian join or a series of for-loops.
Using data.table's non-equi joins, we can obtain this by changing the data.frames to data.table, non-equi merge and then sum of the columns
id <- c("a", "b", "c", "d", "e")
a <- c(2, 4, 20, 8, 7)
b <- c(1, 3, 4, 7)
c <- c(3, 6, 9, 12)
d1 <- data.frame(id, a)
d2 <- data.frame(b, c)
library(data.table)
#Could have used "d1 <- data.table(id, a)" and "d2 <- data.table(b, c" instead of setDT
setDT(d1)
setDT(d2)
#Non-equi join, following by sum using dt[i, j, by, ...] syntax. (see link wiki in link)
d2[d1, on = .(b <= a), allow.cartesian = TRUE][, sum(c), by = id]
Edit: Workaround for 2e31+ rows
A problem that might occur when using cartesian joins is the vector length limitation of R. One possible work-around for this (and there are likely myriads) is to avoid joining altogether, and use the fast subsetting aspect of data.table, as shown below
setkey(d1, 'id')
d1[.(unique(id)), d2[a >= b, sum(c)], by = .EACHI]
explanation:
The query goes as follows:
setkey(d1, 'id') reorders d1 according to id, which allows using the i argument.
d1[.(unique(id))]: Once we've reordered we can utilize fast binary subsetting in the first argument. Here it is saying "give me all rows with id's contained in unique(id).
- While (2) seems unnecessary, it is necessary for the
by = .EACHI argument, which lets data.table know we want to perform the action in j seperately for each i.
- letting
j = d2[a >= b, sum(c)] performs all the calculations. data.table will automatically index a such that the comparison b <= a can be performed using binary search.
This should be somewhat if not much faster than subsetting using a regular for-loop. Albeit slower than using a cartesian join.
Edit: Alternative using Rcpp
Looking at the comment from @caalbarracinb, the number of summations to be done seems to be quit large, using either of these methods. Avoiding duplicate summation will speed up this calculation quite handsomely.
One method for doing this is to assume that a, and b are sorted in ascending order, and iterating over values in a smart way.
Below is my (likely quite inefficient) example of how one could achieve this with an Rcpp function.
#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export(rng=false)]]
NumericVector sumCompar(NumericVector a, NumericVector b, NumericVector c){
// assumes b, a are sorted in ascending order according to sum.
int na = a.length(), nb = b.length(), j = 0;
NumericVector sums(na);
auto sum = 0.0;
// Iterate over a, sum over elements in b until a < b.
// Once this happens we've summed over all values in the specific category.
for(int i = 0; i < na; ++i){
while(j < nb){
if(a(i) < b(j))
break;
sum += c(j);
j++;
}
sums(i) = sum;
}
return sums;
}
which we can use as
aa <- d1[, .(a = max(a)), by = id][order(a), a]
idd <- d1[, .(a = max(a)), by = id][order(a), id]
bb <- d2[order(b), b]
cc <- d2[order(b), c]
data.table(id = idd, sum = sumCompar(a = aa, b = bb, c = cc))
Now to make a (horrible) comparison of speed, we could use microbenchmark:
microbenchmark::microbenchmark(
cart_join = d2[d1, on = .(b <= a), allow.cartesian = TRUE][, sum(c), by = id],
subset = d1[.(unique(id)), d2[a >= b, sum(c)], by = .EACHI],
rcpp = {
out <- data.table(id = d1[, id[1L], by = id]$id,
sum = sumCompar(a = aa, b = bb, c = cc))
}
)
#output:
Unit: microseconds
expr min lq mean median uq max neval
cart_join 2224.201 2457.6510 3972.440 3063.801 5195.200 12475.101 100
subset 3251.001 3573.3510 5638.339 3994.851 7969.900 13460.502 100
rcpp 530.701 645.3015 1055.473 735.201 1016.551 9147.501 100
And looking at the median time, we can see the Rcpp implementation is quite a bit faster in this example.
But the important thing here, is that this speed difference will be much greater for larger inputs, as it does not have to perform unnecessary comparisons as a, b and c are assumed to have the correct order.