Source Edit

Approximately k-Most Oft. This is constant space & constant inc&query time with adjustably small error. AMOft[K,C] augments the sketch with an O(k) paired Table & HeapQueue. Present impl does NOT scale well to very large k (past ~top-1000). E.g.:

var amo = initAMOft[int, uint32](k=10)
for i in 0..<500: amo.inc i, i # Not v.skewed => not v.accurate
for (i, c) in amo.mostCommon(5): echo i, " ", c

Types

AMOft[K; C] = object: Track most often hashable K with counters C. Source Edit
CtMnSketch[K; C] = object: CountMinSketch over hashable K & counters C. Source Edit

Procs

proc inc[K, C](a: var AMOft[K, C]; key: K; r = 1): Count key as being seen r times. Source Edit
proc inc[K, C](cs: var CtMnSketch[K, C]; key: K; r = 1): C {.discardable.}: Count key r times; Gives new counts; I.e., (key, r=0) can query. Source Edit
proc initAMOft[K, C](k, w: int; d = 4; salts: seq[int] = @[]): AMOft[K, C]: Source Edit
proc initCtMnSketch[K, C](w: int; d = 4; salts: seq[int] = @[]): CtMnSketch[K, C]: w=Size(count tables), larger implies less overestimation. d=nTables, larger implies less P(overEst). salts=Override default generated salts. Source Edit

Iterators

iterator mostCommon[K, C](a: AMOft[K, C]; k = 0): (K, C): Yield (k-most common values in a, each count) tuples; k<=0 => known. Source Edit

adix/amoft

Types

Procs

Iterators