digest::ds Namespace Reference

Classes
struct	Adaptive
	Adaptive data structure. Selects between Naive and Naive2 based on the large window size. More...
struct	Adaptive64
	Same as Adaptive but uses 64-bit hashes. More...
struct	Interface
struct	Naive
	Naive data structure. Naively loops through the array to find the minimum. More...
struct	Naive2
	Naive2 data structure. Remembers the last minimum index and only loops through the array when this index leaves the window. More...
struct	SegmentTree
	Segment Tree data structure. Supports log(n) point updates and range minimum queries. More...

Detailed Description

Data structures for minimum hash queries on a window. ntHash does not support large_window < 4

Selecting the correct data_structure our general guidelines:

• for large_window < 12, use Naive
• for 12 <= large_window <= 16 use SegmentTree
• for large_window > 16 use Naive2

Adaptive performs at worst about 10% slower than best Adaptive64 performs at worst about 100% slower than best