Documentation
¶
Overview ¶
Package sigbits extracts significant bits from a sorted list of strings. Significant bits are the minimal bit set to distinguish all of the strings. E.g. we have 3 strings:
ab // bin: 0110 0001 0110 0010 ac // bin: 0110 0001 0110 0011 b // bin: 0110 0010
The significant bits are [15, 7], which means the first different bits of "ab" and "ac" is the 15-th bit, and the 7-th bit for "ac" and "b".
Since 0.1.9
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func FirstDiffBits ¶
FirstDiffBits find the first different bit position of every two adjacent keys.
Since 0.1.9
func ShardByPrefix ¶ added in v0.1.20
ShardByPrefix splits a sorted string slice into shards each of which has at most maxSize elts.
The rule is that every shard has a unique prefix. All prefixes are still a sorted string slice.
It returns a slice of prefix lengths in bytes of each shard, and a slice of the starting index of each shard.
Since 0.1.20
Types ¶
type SigBits ¶
type SigBits struct {
// contains filtered or unexported fields
}
SigBits is a helper to get information about how many bits are required to distinguish a set of keys.
Since 0.1.9
func (*SigBits) CountPrefixes ¶
CountPrefies counts the number of n-bit prefix in a subset of keys [keyStart, keyEnd):
The first return value is the index of the first bit where there is a different bit among all keys. The second return values is a []int32 of maxitem + 1 elements. The ith element is the number of i-bits long prefix.
Since 0.1.9
Source Files