prob/topk
TopK
(defstruct TopK [keys : (Vec int) counts : (Vec int) k : int])
an exact Top-K tracker with parallel key/count Vecs.
Since: probabilistic-spice-plan C2
topk-len
(topk-len [^borrow tk : TopK] :)
the number of distinct items tracked.
Since: probabilistic-spice-plan C2
topk-count
(topk-count [^borrow tk : TopK key : int] :)
the count for a key, or 0 if not tracked.
Since: probabilistic-spice-plan C2
topk-new
(topk-new [k : int] :)
create a TopK tracker with capacity K.
| k | the maximum number of items to return from topk-list |
A new empty TopK tracker.
(let [tk (topk-new 10)] ...)
Since: probabilistic-spice-plan C2
topk-free
(topk-free [tk : TopK] :)
release the key and count arrays.
Since: probabilistic-spice-plan C2
topk-add!
(topk-add! [^borrow tk : TopK key : int] :)
record one occurrence of an element.
| tk | the tracker (mutated in place) | |
| key | the integer key to add |
nil
Since: probabilistic-spice-plan C2
topk-list
(topk-list [^borrow tk : TopK] :)
return the top K (count, key) pairs sorted by count descending.
| tk | the tracker |
A new flat Vec[int] of [count1, key1, count2, key2, ...] sorted by count descending. If fewer than K items have been tracked, returns all of them. The caller owns the returned Vec and must free it.
Since: probabilistic-spice-plan C2
topk-merge
(topk-merge [^borrow a : TopK ^borrow b : TopK] :)
"add all of B's items into A" into a new tracker.
| a | first tracker | |
| b | second tracker |
A new TopK containing all entries from both a and b, with counts summed for shared keys. Both inputs remain valid. The result's K is taken from a. Note: this merge is NOT idempotent and NOT commutative under shared items. Joining a TopK with itself doubles every count. No JoinSemilattice instance is declared for TopK (probabilistic-spice-plan 2.6).
Since: probabilistic-spice-plan C2
Internal definitions
__topk-find-count-- internal: linear scan for key, return its count.__topk-init-- internal: push n zeros into a Vec.__topk-find-slot-- internal: find the slot index for key, or -1.__topk-find-max-- internal: find the index of the maximum count__topk-swap-- internal: swap entries at indices i and j.__topk-select-- internal: selection sort the top K entries to the front.__topk-copy-front-- internal: copy the first K (count, key) pairs__topk-merge-scan-- internal: add all entries from src into dst.