Struct nekolib::ds::BicrementalMedianDev

pub struct BicrementalMedianDev<M: CommutativeGroup>where
    M::Set: Ord + Clone,{ /* private fields */ }

中央値と偏差の管理。

多重集合 $S$ への要素の追加と削除を行いつつ、中央値と偏差を管理する。 ここで、偏差は中央値との絶対値の総和とする。 $S$ のうち小さい方から $\lceil|S|/2\rceil$ 個取り出したものを $L$、 残りの $\lfloor|S|/2\rfloor$ 個取り出したものを $R$ とする。 中央値を $L$ の最大値として定義し、$a_{\text{med}}$ と書く。 このとき、偏差 $\sigma$ は次のように書ける。 $$ \sigma = \sum_{a\in L} (a_{\text{med}}-a) + \sum_{a\in R} (a-a_{\text{med}}). $$ $\sum_{a\in L} a = \sigma_L$、$\sum_{a\in R} a = \sigma_R$ とすると、 $$ \begin{aligned} \sigma &= \begin{cases} -\sigma_L + \sigma_R, & \text{if } |L| = |R|; \\ -\sigma_L + \sigma_R + a_{\text{med}}, & \text{if } |L| = |R|+1. \\ \end{cases} \end{aligned} $$

Implementations

impl<M: CommutativeGroup> BicrementalMedianDev<M>where M::Set: Ord + Clone,

pub fn new() -> Selfwhere M: Default,

pub fn with(cgroup: M) -> Self

pub fn insert(&mut self, x: M::Set)

pub fn remove(&mut self, x: M::Set) -> bool

pub fn median(&self) -> Option<&M::Set>

pub fn median_dev(&self) -> M::Set

Trait Implementations

impl<M: Clone + CommutativeGroup> Clone for BicrementalMedianDev<M>where M::Set: Ord + Clone + Clone,

fn clone(&self) -> BicrementalMedianDev<M>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<M: Debug + CommutativeGroup> Debug for BicrementalMedianDev<M>where M::Set: Ord + Clone + Debug,

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

Formats the value using the given formatter.

impl<M: PartialEq + CommutativeGroup> PartialEq<BicrementalMedianDev<M>> for BicrementalMedianDev<M>where M::Set: Ord + Clone + PartialEq,

fn eq(&self, other: &BicrementalMedianDev<M>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<M: Eq + CommutativeGroup> Eq for BicrementalMedianDev<M>where M::Set: Ord + Clone + Eq,

impl<M: CommutativeGroup> StructuralEq for BicrementalMedianDev<M>where M::Set: Ord + Clone,

impl<M: CommutativeGroup> StructuralPartialEq for BicrementalMedianDev<M>where M::Set: Ord + Clone,