| commit | e3c9565b438cb2eb4be6c2bd57696e378f754e46 | [log] [tgz] |
|---|---|---|
| author | Eric Eisner <eric.d.eisner@gmail.com> | Tue Jan 11 21:46:50 2011 -0800 |
| committer | Robert Griesemer <gri@golang.org> | Tue Jan 11 21:46:50 2011 -0800 |
| tree | f603c18865447d3291e3fc316265057e9841434b | |
| parent | 6f62e407733cb8b340e75bc91bc2633976675d9d [diff] |
suffixarray: faster creation algorithm
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