topn for efficiently doing sorted head/tail

[MichaelChirico]

Inspired by Matt's observation here: e1ac663

DT[topn(score, 5L)] also looks nicer than DT[order(score)[1:5]] or DT[order(score)][1:5].

A quick search suggests two possible implementations which might be better in one situation or another:

https://stackoverflow.com/questions/4956593/optimal-algorithm-for-returning-top-k-values-from-an-array-of-length-n

Will take a look at feasibility to implement cleanly.

Just looked now and dplyr also has top_n but seems they implement it inefficiently:

dplyr:::top_n_rank
function (n, wt) 
{
    if (n > 0) {
        min_rank(desc(wt)) <= n
    }
    else {
        min_rank(wt) <= abs(n)
    }
}

[2005m]

Questions:

• I am wrong in saying that you want something more like DT[order(score, decreasing = TRUE)[1:5]] ?
• order works for character vector..etc do you want the same or just numeric columns/vectors?
• Do you have 4-5 examples of usage so I get a good idea of what you would like?
  Thanks

[MichaelChirico]

Yes, order(score, decreasing = TRUE)[1:5], however, it's inefficient to (1) sort and (2) return millions of observations when we're only after the top 5.

The link suggests either a tournament or a min-heap implementation

[2005m]

Ok thank you. I think I can suggest something different from what is in your link but not far. My initial experiment suggests a 76 times speed-up.

[MichaelChirico]

Awesome, that's exactly the sort of thing I had in mind! 🚀

[jangorecki]

and why topn and not head? we could easily optimize head(order(.), 5) or order(.)[1:5]

[MichaelChirico]

That looks wrong to me... head(x, by = col_spec) maybe looks more natural. But topn fits more naturally into i:

head(x, 5L, by = .(V1, -V2))
# vs
x[topn(V1, -V1, 5L)]

Looking at this, I'm not sure how safe it is to have ... signature, and topn(..., n=5L) reads funny, maybe top(..., n = 5L) is more natural.

[jangorecki]

but x has particular order already so doing head(x, by = cols) does not really asks for any new order.
topn sounds nice but it is always a new function for users to learn vs just base R known functions

[MichaelChirico]

Agree, but I think we're stretching head pretty far to accommodate here. Certainly I wouldn't understand what's going on if I read head(order(.), 5)

We can optimize it, but users would have to know that we're optimizing it to even try writing like that. Users knowing internal optimizations like this is I would guess harder than knowing a new function.

[jangorecki]

If we just document that then I think it should be fine, users who don't read documentation cannot expect to write efficient code. And because it is build base R way it should be easy to remember.

[MichaelChirico]

I disagree with that... already the manual on CRAN is 120+ pages:

https://cran.r-project.org/web/packages/data.table/data.table.pdf

Is reading this really required to get the most out of data.table?

Anyway, even with long-time familiarity with base R, I highly doubt I would write order(...)[1:5] as head(order(...), 5) -- I would have to know that's optimized, and change my code to take advantage.

When we do auto-optimizations, I would expect we catch common coding style, and optimize it, rather than making user change coding style to get optimization. Once user is required to change coding style to get optimization, I no longer see the benefit of avoiding a new function.