Extend uniqueN to speed up for factors as well

[MichaelChirico]

I think the key insight of #2648 (optimizing uniqueN for logical input) was: we know in advance the output of uniqueN can only take on a small number of values (namely, NA, TRUE, or FALSE).

This logic should extend easily to factor columns as well, where we know the maximum possible uniqueN(factor_col) is length(levels(factor_col)) (+1 if !na.rm).

This is probably related to #2458, as well as #1120.

[HughParsonage]

Yikes, could be an even more dramatic improvement than for logical v. For y <- sample(letters, size = 1e5, replace = TRUE):

Unit: nanoseconds
                      expr    min     lq      mean   median       uq     max neval cld
                uniqueN(y) 375868 386108 540984.89 392131.5 401317.5 7641140   100   b
         length(levels(y))   2710   3313   5623.13   6024.0   6325.0   25600   100  a 
 length(attr(y, "levels"))      0    301    415.80    302.0    602.0    2109   100  a 

[MichaelChirico]

what I wrote up quickly is worst-case O(n^2) so rethinking. I don't know how to do hash lookups in C (and also not sure if that's appropriate for production code due to potential collisions)... My idea instead is to try to essentially run nlevels(factor(x)) which should drop unused levels, hopefully quickly. maybe shortcut to whatever's being done under the hood there.

…

On Sun, Mar 25, 2018, 10:48 AM HughParsonage ***@***.***> wrote: Yikes, could be an even more dramatic improvement than for logical v. For y <- sample(letters, size = 1e5, replace = TRUE): Unit: nanoseconds expr min lq mean median uq max neval cld uniqueN(y) 375868 386108 540984.89 392131.5 401317.5 7641140 100 b length(levels(y)) 2710 3313 5623.13 6024.0 6325.0 25600 100 a length(attr(y, "levels")) 0 301 415.80 302.0 602.0 2109 100 a — You are receiving this because you were assigned. Reply to this email directly, view it on GitHub <#2703 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AHQQdZUtD0wI26y7YHBqFHAl1sJuRlgYks5thwWFgaJpZM4S4Njh> .

[HughParsonage]

Ah of course, not all levels may be present. Too good to be true...

[MichaelChirico]

So much for that idea (from factor):

  if (missing(levels)) {
    y <- unique(x, nmax = nmax)
    ind <- sort.list(y)
    levels <- unique(as.character(y)[ind])
  }

[MichaelChirico]

Thinking again quickly I think this is O(nk) where k is the number of levels and typically k << n. Still not sure if it'll speed up the code but may be worth giving it a go anyway.