Struct amadeus::MostFrequent

pub struct MostFrequent<T: Hash + Eq + Clone> { /* fields omitted */ }

This data structure tracks the n most frequently seen elements in a stream, using only O(n) space. It is approximate.

The formulation used is described here.

while an item i from the input stream arrives:
    if H[i] exists
        increment the value associated with H[i]
    elsif number of items in H < k
        put H[i] into map with value of base + 1
    elseif there exists an entry j with a value of base
        remove j and put H[i] into map with value of base + 1
    else
        increment base
endwhile

See A Simple Algorithm for Finding Frequent Elements in Streams and Bags for more information.

Methods

impl<T: Hash + Eq + Clone> MostFrequent<T>

pub fn new(n: usize) -> Self

Create an empty MostFrequent data structure with the specified capacity.

pub fn capacity(&self) -> usize

The n most frequent elements we have capacity to track.

pub fn push(&mut self, item: T)

"Visit" an element.

Important traits for MostFrequentIter<'a, T>

impl<'a, T: Hash + Eq + Clone> Iterator for MostFrequentIter<'a, T> type Item = (&'a T, usize);

pub fn iter(&self) -> MostFrequentIter<T>

An iterator visiting all elements and their counts in descending order of frequency. The iterator element type is (&'a T, usize).

Trait Implementations

impl<T: Clone + Hash + Eq + Clone> Clone for MostFrequent<T>

fn clone(&self) -> MostFrequent<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a, T: Hash + Eq + Clone + Debug> Debug for MostFrequent<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Hash + Eq + Clone> Sum for MostFrequent<T>

fn sum<I>(iter: I) -> Self where     I: Iterator<Item = Self>,

Method which takes an iterator and generates Self from the elements by "summing up" the items.

impl<T: Hash + Eq + Clone> Add for MostFrequent<T>

type Output = Self

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self

Performs the + operation.

impl<T: Hash + Eq + Clone> AddAssign for MostFrequent<T>

fn add_assign(&mut self, other: Self)

Performs the += operation.