forked from foudrer/Sux
-
Notifications
You must be signed in to change notification settings - Fork 0
/
CHANGES
77 lines (48 loc) · 2.09 KB
/
CHANGES
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
0.9.2
- Implemented Giuseppe Ottaviano's improvement to the broadword
algorithm for select.
0.9.1
- Fixed major bug in Elias-Fano implementation (the upper-bits array
wasn't zeroed).
0.9
- Improved bit extraction.
- Now the simple structure for selection interleaves first-level and
second-level inventories to reduce cache misses.
- We now use a slightly improved version of Gog & Petri's select-in-a-word.
- Replaced horrendous linear congruential generator with top-quality
xorshift1024* generator in testranksel.cpp.
- The maximum number of longwords per subinventory in simple_select is
now a mandatory parameter, rather than a #define. This should avoid
people thinking that simple_select cannot trade off space for speed.
0.8
- New elementary simple_rank structure, useful for testing space/speed
tradeoffs.
- We now heavily use gcc's built-in functions __builtin_popcountll(),
__builtin_clzll() and __builtin_ctzll(), which map to single
instructions for population counting, counting the number of leading
zeroes and counting the number of trailing zeroes. Please compile with
-msse4.2 using a recent gcc (4.7+). The speed improvement is impressive.
- The broadword algorithm for selection has been modified following the
idea used by Simon Gog in its SDSL library, that is, replacing the
second part (ranking in a byte) using a table lookup. Now it's twice
as fast.
0.7
- Fixed minor bug in simple_select in the case of zero-length bit vectors, and
wrong assertion (the code was right, the assert was wrong). Thanks to Jeffrey
Sorensen for reporting these bugs.
0.6
- Fixed pernicious bug in select 9.
0.5
- Faster basic operation: some broadword operation were implemented in a redundant
way.
- New implementation for balanced parentheses.
0.4
- Fixed bug in simple_select_zero: under certain conditions, an error in
counting zeroes was causing a out-of-bounds array access.
0.3
- Renamed some classes to adjuct to Sux4J.
- More precise bound for Elias-Fano representations.
0.2
- New structures for sparse arrays, and new select implementations.
0.1
- First release.