gosaca
Description
Pure Go implementation of An Optimal Suffix Array Construction
Algorithm, a paper by
Ge Nong.
Benchmarks
More extensive tests and benchmarks run on large copora are available as
gosaca-bigtests so as not to
balloon the size of this repo.
The following table compares
sa-is with gosaca running on a
2012 Macbook Pro. The comparision is not really fair in many senses (SA-IS is
an earlier, slightly less efficient algorithm, but it's implemented in
optimized C code); here it is nonetheless. Times are in seconds.
File |
Size |
sa-is |
gosaca |
chr22dna |
34553758 |
5.893 |
10.807 |
etext99 |
105277340 |
21.507 |
41.862 |
gcc30tar |
86630400 |
10.252 |
23.149 |
howto |
39422105 |
6.050 |
12.123 |
jdk13c |
69728899 |
6.567 |
19.807 |
linux245tar |
116254720 |
14.635 |
32.696 |
rctail96 |
114711151 |
15.143 |
40.225 |
rfc |
116421901 |
16.191 |
36.505 |
sprot34dat |
109617186 |
17.485 |
39.164 |
w3c2 |
104201579 |
10.395 |
30.164 |
abac |
200000 |
0.005 |
0.016 |
abba |
10500600 |
0.646 |
2.326 |
book1x20 |
15375420 |
1.620 |
5.126 |
fib_s14930352 |
14930352 |
0.981 |
4.579 |
fss10 |
12078908 |
0.739 |
3.539 |
fss9 |
2851443 |
0.145 |
0.518 |
houston |
3840000 |
0.102 |
0.288 |
paper5x80 |
981924 |
0.041 |
0.099 |
test1 |
2097152 |
0.096 |
0.236 |
test2 |
2097152 |
0.103 |
0.251 |
test3 |
2097152 |
0.094 |
0.206 |
Copyright
Copyright © John Gallagher. MIT
License; see LICENSE for further details.