• Eric Eisner's avatar
    suffixarray: faster creation algorithm · e3c9565b
    Eric Eisner authored
    This implements the algorithm qsufsort using the sort package
    as a sorting primitive. Its worst-case performance is O(N*log(N)), and it
    uses only an additional slice of N ints of memory during creation.
    
    Benchmarks (seconds):
               old    new
    10k nulls          149    0.044
    1M English corpus  32.0   3.6
    
    R=gri, gri1
    CC=golang-dev
    https://golang.org/cl/3752044
    e3c9565b
qsufsort.go 4.67 KB