• Dave Watson's avatar
    Use radix sort in TDigest · 7fed85c2
    Dave Watson authored
    Summary:
    Update the TDigest interface to accept unsorted or sorted data.
    If unsorted, use a custom radix sort explicitly aimed at this use case:
    doubles only, assume small data, so we don't use in-place and everything still
    fits in cache (1000-10000 items).
    
    Previously D8875766.  This version does not require newer boost versions, and puts
    everything in the heap, so there should be no fiber overflows.
    
    Reviewed By: yfeldblum
    
    Differential Revision: D9197722
    
    fbshipit-source-id: 10088cf14d1ff88e1072c00084e09129271e97ec
    7fed85c2
TDigestTest.cpp 11.3 KB