]> Cypherpunks repositories - gostls13.git/commit
projects / gostls13.git / commit
summary | shortlog | log | commit | commitdiff | tree
(parent: 6f62e40) | patch
suffixarray: faster creation algorithm
authorEric Eisner <eric.d.eisner@gmail.com>
Wed, 12 Jan 2011 05:46:50 +0000 (21:46 -0800)
committerRobert Griesemer <gri@golang.org>
Wed, 12 Jan 2011 05:46:50 +0000 (21:46 -0800)
commite3c9565b438cb2eb4be6c2bd57696e378f754e46
treef603c18865447d3291e3fc316265057e9841434btree
parent6f62e407733cb8b340e75bc91bc2633976675d9dcommit | 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
src/pkg/index/suffixarray/Makefile diff | blob | history
src/pkg/index/suffixarray/qsufsort.go [new file with mode: 0644] blob
src/pkg/index/suffixarray/suffixarray.go diff | blob | history
src/pkg/index/suffixarray/suffixarray_test.go diff | blob | history
Go GOST TLS 1.3