11 releases (4 breaking)

0.5.0 Aug 24, 2023
0.4.0 Aug 21, 2023
0.3.2 Mar 6, 2023
0.3.1 Feb 16, 2023
0.1.0 Feb 2, 2023

#1189 in Algorithms

Download history 220/week @ 2024-07-01 313/week @ 2024-07-08 317/week @ 2024-07-15 205/week @ 2024-07-22 289/week @ 2024-07-29 317/week @ 2024-08-05 261/week @ 2024-08-12 262/week @ 2024-08-19 154/week @ 2024-08-26 228/week @ 2024-09-02 185/week @ 2024-09-09 154/week @ 2024-09-16 295/week @ 2024-09-23 124/week @ 2024-09-30 265/week @ 2024-10-07 202/week @ 2024-10-14

927 downloads per month

MIT license

16KB
282 lines

TopK

TopK algorithm implementation in Rust.

This crate currently provides the Filtered Space-Saving algorithm.

Version numbers follow the semver convention.

Example

let mut topk = FilteredSpaceSaving::new(3);
topk.insert("1", 10);
topk.insert("2", 20);
topk.insert("3", 1);
topk.insert("4", 2);
let topk_result = topk.into_sorted_vec();
assert_eq!(topk_result.len(), 3);
assert_eq!(topk_result[0].0, "2");

merging space-saving results is supported:

let mut fss1 = FilteredSpaceSaving::new(3);
fss1.insert("1", 10);
fss1.insert("2", 20);
fss1.insert("3", 2);
fss1.insert("4", 1);
fss1.insert("4", 3);
fss1.insert("5", 3);
let mut fss2 = FilteredSpaceSaving::new(3);
fss2.insert("1", 10);
fss2.insert("2", 20);
fss2.insert("3", 20);
fss2.insert("4", 10);
fss1.merge(&fss2).unwrap();
let result = fss1.into_sorted_vec();
assert_eq!(result[0].0, "2");

lib.rs:

TopK algorithm implementation in Rust.

This crate currently provides the Filtered Space-Saving algorithm.

Version numbers follow the semver convention.

Example

let mut topk = FilteredSpaceSaving::new(3);
topk.insert("1", 10);
topk.insert("2", 20);
topk.insert("3", 1);
topk.insert("4", 2);
let topk_result = topk.into_sorted_vec();
assert_eq!(topk_result.len(), 3);
assert_eq!(topk_result[0].0, "2");

merging space-saving results is supported:

let mut fss1 = FilteredSpaceSaving::new(3);
fss1.insert("1", 10);
fss1.insert("2", 20);
fss1.insert("3", 2);
fss1.insert("4", 1);
fss1.insert("4", 3);
fss1.insert("5", 3);
let mut fss2 = FilteredSpaceSaving::new(3);
fss2.insert("1", 10);
fss2.insert("2", 20);
fss2.insert("3", 20);
fss2.insert("4", 10);
fss1.merge(&fss2).unwrap();
let result = fss1.into_sorted_vec();
assert_eq!(result[0].0, "2");

Dependencies

~2MB
~32K SLoC