Sort a data.table fast by Ascending/Descending order

Question

I have a data.table with about 3 million rows and 40 columns. I would like to sort this table by descending order within groups like the following sql mock code:

sort by ascending Year, ascending MemberID, descending Month

Is there an equivalent way in data.table to do this? So far I have to break it down into 2 steps:

setkey(X, Year, MemberID)

This is very fast and takes only a few second.

X <- X[,.SD[order(-Month)],by=list(Year, MemberID)]

This step takes so much longer (5 minutes).

Update: Someone made a comment to do X <- X[sort(Year, MemberID, -Month)] and later deleted. This approach seems to be much faster:

user  system elapsed 
5.560  11.242  66.236

My approach: setkey() then order(-Month)

   user  system elapsed 
816.144   9.648 848.798

My question is now: if I want to summarize by Year, MemberId and Month after sort(Year, MemberID, Month), does data.table recognize the sort order?

Update 2: to response to Matthew Dowle:

After setkey with Year, MemberID and Month, I still have multiple records per group. What I would like is to summarize for each of the groups. What I meant was: if I use X[order(Year, MemberID, Month)], does the summation utilizes binary search functionality of data.table:

monthly.X <- X[, lapply(.SD[], sum), by = list(Year, MemberID, Month)]

Update 3: Matthew D proposed several approaches. Run time for the first approach is faster than order() approach:

   user  system elapsed 
  7.910   7.750  53.916

Matthew: what surprised me was converting the sign of Month takes most of the time. Without it, setkey is blazing fast.

Matt Dowle Matt Dowle · Accepted Answer · 2012-12-03T15:47:49

Update June 5 2014:

The current development version of data.table v1.9.3 has two new functions implemented, namely: setorder and setorderv, which does exactly what you require. These functions reorder the data.table by reference with the option to choose either ascending or descending order on each column to order by. Check out ?setorder for more info.

In addition, DT[order(.)] is also by default optimised to use data.table's internal fast order instead of base:::order. This, unlike setorder, will make an entire copy of the data, and is therefore less memory efficient, but will still be orders of magnitude faster than operating using base's order.

Benchmarks:

Here's an illustration on the speed differences using setorder, data.table's internal fast order and with base:::order:

require(data.table) ## 1.9.3
set.seed(1L)
DT <- data.table(Year     = sample(1950:2000, 3e6, TRUE), 
                 memberID = sample(paste0("V", 1:1e4), 3e6, TRUE), 
                 month    = sample(12, 3e6, TRUE))

## using base:::order
system.time(ans1 <- DT[base:::order(Year, memberID, -month)])
#   user  system elapsed 
# 76.909   0.262  81.266 

## optimised to use data.table's fast order
system.time(ans2 <- DT[order(Year, memberID, -month)])
#   user  system elapsed 
#  0.985   0.030   1.027

## reorders by reference
system.time(setorder(DT, Year, memberID, -month))
#   user  system elapsed 
#  0.585   0.013   0.600 

## or alternatively
## setorderv(DT, c("Year", "memberID", "month"), c(1,1,-1))

## are they equal?
identical(ans2, DT)    # [1] TRUE
identical(ans1, ans2)  # [1] TRUE

On this data, benchmarks indicate that data.table's order is about ~79x faster than base:::order and setorder is ~135x faster than base:::order here.

data.table always sorts/orders in C-locale. If you should require to order in another locale, only then do you need to resort to using DT[base:::order(.)].

All these new optimisations and functions together constitute FR #2405. bit64::integer64 support also has been added.

NOTE: Please refer to the history/revisions for earlier answer and updates.

Sort a data.table fast by Ascending/Descending order

2 Answers

Update June 5 2014:

Benchmarks: