Struct sqs_service_helper::autoscaling::StreamingMedian
[−]
[src]
pub struct StreamingMedian { /* fields omitted */ }StreamingMedian provides a simple interface for inserting values
and calculating medians. By default we start with a repeated median of 31,000.
31,000 is chosen because it is a "worst case" - we assume, at first, that the
time to process is longer than the time it takes for a message visibility to
time out.
Methods
impl StreamingMedian[src]
fn new() -> StreamingMedian
fn last(&self) -> u32
Returns the last median value without performing any recalculation
Example
use sqs_service_handler::autoscaling::median;
let stream = StreamingMedian::new();
assert_eq!(stream.last(), 31_000);
fn insert_and_calculate(&mut self, value: u32) -> u32
Calculates and returns the median
Arguments
value- The value to be inserted into the stream # Example ```norun use sqs_service_handler::autoscaling::median;
let stream = StreamingMedian::new(); assert_eq!(stream.insert_and_calculate(31_000), 31_000); ``` The algorithm used to efficiently insert and calculate relies on the fact that the data is always left in a sorted state.
First we pop off the oldest value, 'removed', from our internal ring buffer. Then we add our new value 'value' to the buffer at the back. We use this buffer to maintain a temporal relationship between our values.
A separate stack array 'self.sorted' is used to maintain a sorted representation of the data.
We binary search for 'removed' in our 'sorted' array and store the index as 'remove_index'.
We then calculate where to insert the new 'value' by binary searching for it, either finding it already or where to insert it.
If the 'insert_index' for our 'value' is less than the 'remove_index' we shift the data between the 'remove_index' and the 'insert_index' over one space. This overwrites the old value we want to remove while maintaining order. We can then insert our value into the array.
Example: Starting with a self.sorted of [2, 3, 4, 5, 7, 8] We then call insert_and_calculate(6) Let's assume that '3' is the oldest value. This makes 'remove_index' = 1 We search for where to insert our value '6' and its' index 3. [2, 3, 4, 5, 7, 8] <- remove_index = 1, insert_index = 3 Shift the data between 1 and 3 over by one. [2, 4, 5, 5, 7, 8] Insert our value into index 3. [2, 4, 5, 6, 7, 8]
A similar approach is performed in the case of the insert_index being before the remove index.
Unsafe is used here to dramatically improve performance - a full 3-5x