1

The task is to efficiently extract events from this data:

data <- structure(
            list(i = c(1, 1, 1, 2, 2, 2), t = c(1, 2, 3, 1, 3, 4), x = c(1, 1, 2, 1, 2, 3)),
            .Names = c("i", "t", "x"), row.names = c(NA, -6L), class = "data.frame"
        )

> data
  i t x
1 1 1 1
2 1 2 1
3 1 3 2
4 2 1 1
5 2 3 2
6 2 4 3

Let's call i facts, t is time, and x is the number of selections of i at t.

An event is an uninterrupted sequence of selections of one fact. Fact 1 is selected all throughout t=1 to t=3 with a sum of 4 selections. But fact 2 is split into two events, the first from t=1 to t=1 (sum=1) and the second from t=3 to t=4 (sum=5). Therefore, the event data frame is supposed to look like this:

> event
  i from to sum
1 1    1  3   4
2 2    1  1   1
3 2    3  4   5

This code does what is needed:

event <- structure(
             list(i = logical(0), from = logical(0), to = logical(0), sum = logical(0)),
             .Names = c("i", "from", "to", "sum"), row.names = integer(0),
             class = "data.frame"
         )
l <- nrow(data) # get rows of data frame
c <- 1 # set counter
d <- 1 # set initial row of data to start with
e <- 1 # set initial row of event to fill
repeat{
    event[e,1] <- data[d,1] # store "i" in event data frame
    event[e,2] <- data[d,2] # store "from" in event data frame
    while((data[d+1,1] == data[d,1]) & (data[d+1,2] == data[d,2]+1)){
        c <- c+1
        d <- d+1
        if(d >= l) break
    }
    event[e,3] <- data[d,2] # store "to" in event data frame
    event[e,4] <- sum(data[(d-c+1):d,3]) # store "sum" in event data frame
    c <- 1
    d <- d+1
    e <- e+1
}

The problem is that this code takes 3 days to extract the events from a data frame with 1 million rows and my data frame has 5 million rows.

How can I make this more efficient?

P.S.: There's also a minor bug in my code related to termination.

P.P.S.: The data is sorted first by i, then by t.

2 Answers 2

1

can you try if this dplyr implementation is faster?

library(dplyr)

data <- structure(
    list(fact = c(1, 1, 1, 2, 2, 2), timing = c(1, 2, 3, 1, 3, 4), x = c(1, 1, 2, 1, 2, 3)),
    .Names = c("fact", "timing", "x"), row.names = c(NA, -6L), class = "data.frame"
)

group_by(data, fact) %>%
    mutate(fromto=cumsum(c(0, diff(timing) > 1))) %>%
    group_by(fact, fromto) %>%
    summarize(from=min(timing), to=max(timing), sumx=sum(x)) %>%
    select(-fromto) %>%
    ungroup()

how about this data.table implementation?

library(data.table)
data <- structure(
    list(fact = c(1, 1, 1, 2, 2, 2), timing = c(1, 2, 3, 1, 3, 4), x = c(1, 1, 2, 1, 2, 3)),
    .Names = c("fact", "timing", "x"), row.names = c(NA, -6L), class = "data.frame"
)
setDT(data)[, fromto:=cumsum(c(0, diff(timing) > 1)), by=fact]
event <- data[, .(from=min(timing), to=max(timing), sumx=sum(x)), by=c("fact", "fromto")][,fromto:=NULL]

##results when i enter event in the R console and my data.table package version is data.table_1.9.6
> event
   fact from to sumx
1:    1    1  3    4
2:    2    1  1    1
3:    2    3  4    5
> str(event)
Classes ‘data.table’ and 'data.frame':  3 obs. of  4 variables:
 $ fact: num  1 2 2
 $ from: num  1 1 3
 $ to  : num  3 1 4
 $ sumx: num  4 1 5
 - attr(*, ".internal.selfref")=<externalptr> 
> dput(event)
structure(list(fact = c(1, 2, 2), from = c(1, 1, 3), to = c(3, 
1, 4), sumx = c(4, 1, 5)), row.names = c(NA, -3L), class = c("data.table", 
"data.frame"), .Names = c("fact", "from", "to", "sumx"), .internal.selfref = <pointer: 0x0000000000120788>)

Reference detect intervals of the consequent integer sequences

5
  • Your first implementation took 150 seconds instead of 15 days for my 5 million lines :) Thanks indeed. Your second implementation I couldn't get to work. I ran the first line and then "event <- data[...". Is the code allright? Cause I like the data.table package.
    – hyco
    Apr 15, 2016 at 15:40
  • Thanks. Just run the code as it is. Don't introduce any more event data.table
    – chinsoon12
    Apr 15, 2016 at 23:04
  • Can you please check your data.table implementation? When I run it, it's like the last line doesn't have any effect. But earlier, your fromto column doesn't make sense to me.
    – hyco
    Apr 17, 2016 at 9:34
  • After you run the data.table implementation, just print out data
    – chinsoon12
    Apr 17, 2016 at 11:51
  • That's what I do. data is now the original table with one more column. It's not transformed into the event table. Maybe a version issue? I have checked 3.2.3 and 3.2.4. revised.
    – hyco
    Apr 17, 2016 at 18:47
1

Assuming the data frame is sorted according to data$t, you can try something like this

event <- NULL
for (i in unique(data$i)) {
    x <- data[data$i == i, ]
    ev <- cumsum(c(1, diff(x$t)) > 1)
    smry <- lapply(split(x, ev), function(z) c(i, range(z$t), sum(z$x)))
    event <- c(event, smry)
}
event <- do.call(rbind, event)
rownames(event) <- NULL
colnames(event) <- c('i', 'from', 'to', 'sum')

The result is a matrix, not a data frame.

2
  • Thx for your help. Unfortunately, your algorithm is ten times slower than mine.
    – hyco
    Apr 15, 2016 at 12:24
  • Too bad... You may want to use some profiling tool such as Rprof in order to figure out where in your algorithm the bottleneck is.
    – Ernest A
    Apr 15, 2016 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.