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

#1245 in Algorithms

Download history 224/week @ 2024-07-19 269/week @ 2024-07-26 296/week @ 2024-08-02 289/week @ 2024-08-09 223/week @ 2024-08-16 200/week @ 2024-08-23 190/week @ 2024-08-30 233/week @ 2024-09-06 146/week @ 2024-09-13 317/week @ 2024-09-20 108/week @ 2024-09-27 279/week @ 2024-10-04 160/week @ 2024-10-11 175/week @ 2024-10-18 118/week @ 2024-10-25 190/week @ 2024-11-01

688 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