Count number of rows within certain range

Question

I have a data.table with some values ('value'), lower limits ('min_val') and upper limits ('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 |

I want to calculate the count of rows where value > min_val & value < max_val for each line for the values from the whole 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       |

I've tried dt[, count := nrow(dt[value > dt[min_val] & value < dt[max_val]])] but I'm on the wrong path.

Answer 1

The OP has disclosed that his production dataset consists of 81 million rows. Unfortunately, r2evans' benchmark used only the 4 rows sample dataset provided with the question and has neglected henrik's suggestion. To find the best approach for a large dataset like OP's one I find it worthwhile to run benchmarks with varying and realistic problem sizes in order to measure run time as well as memory consumption.

Run time and memory consumption may be depend on

1. the number of values,
2. the number of intervals,
3. and the number of values which fall into each interval.

Items 1 and 2 are linked as the number of values and the number of intervals is given by the number of rows in the dataset. So, there are two size parameter we can vary, the number of rows n and the number values within each interval m. In order to have reproducible and predictable benchmark data, the benchmark datasets are constructed by

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

In case of n <- 4 and m <- 1 d becomes

   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

In order to create equal conditions for each benchmark run the count column is pre-allocated with some dummy data.

The benchmark includes

• henrik's suggestion to aggregate in a non-equi self join,
• the 3 approaches in r2evans' 3 answer,
• the answer by ThomasIsCoding,
• the answer by Alexandre Léonard

Edit: A 3rd set of benchmark runs compares

• henrik's aggregate in a non-equi self join, and
• chinsoon12's Rcpp solution.

Unfortunately, TarJae's answer did not work for me.

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)

Please, note the logarithmic time scale.

The chart exhibits that

• Alexandre's approach is up to a magnitude slower than any of the other solutions (and may be omitted from further runs),
• with increasing number of rows n henrik's approach becomes neck and neck with r2evans1 (worth to be investigated further),
• the number of values in each interval m seems to have no or little effect on run time.

The latter can be verified by changing the facets and plotting the median times for different m in one facet:

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

In the next chart below, plotting mem_alloc instead of median times exhibits that

• m has no effect on memory allocation (with one exception),
• for large n, henrik's approach needs magnitudes less memory than any other approach:

Please, note the log scale.

2nd set of benchmark runs

Based on the previous results, the next set of benchmark runs varies only size parameter n while m is kept constant. Alexandre's approach is omitted as it is too slow.

n is varied from 2^10 (1024) to 2^14 (16384) with m = 1.0. Unfortunately, the run with n = 2^15 was aborted due to lack of memory on my PC.

autoplot(bm2)

henrik's approach has taken lead in terms of speed for the 2^14 (16384) rows case.

To identify if this indicates a trend, run time vs problem size n is plotted by

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's approach seems to have a high overhead but gains a speed advantage with increasing problem size.

Also with respect to memory allocation, henrik's approach aggregating in a non-equi self join seems to need substantially less memory than the other approaches. More importantly, memory allocation increases less steep with problem size which indicates that this approach can handle much larger problem sizes when available computer memory is a limiting factor.

EDIT: 3rd set of benchmark runs

This set of benchmark runs compares henrik's aggregate in a non-equi self join with chinsoon12's new Rcpp solution.

Due to the much smaller memory footprint of both approaches the problem size can be increased up to 2^18 (262144) rows before hitting the 16 GB memory limit on my Windows PC.

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
    )
  }
)

The next two charts show the median run time and the memory allocation vs problem size, resp. (please, note the log scales):

Results for 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

Apparently, chinsoon's approach is faster for problem sizes up to 2^16 (65536) while henrik's approach ist faster for larger problem sizes (and seems to have a more linear time behaviour). For problem size n = 2^18, henrik's approach is almost 4 times faster than chinsoon's.

On the other hand, henrik's approach allocates much more memory than chinsoon's. For problem size n = 2^18, henrik's approach allocates about 6 time more memory than chinsoon's. Apparently, this ratio is constant for increasing problem size.

So, there is a tradeoff between speed (henrik's approach) and memory requirement (chinsoon's approach) depending on problem size. Your mileage may vary.

Answer 2

We can try outer like this

> 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

data

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