### 3 releases (breaking)

0.4.0 | Mar 15, 2024 |
---|---|

0.2.0 | Apr 14, 2023 |

0.1.0 | Sep 20, 2022 |

#**384** in Algorithms

**AGPL-3.0-only**

17KB

217 lines

# Median accumulator

Simple, space-efficient algorithm to compute the median of an accumulation of elements.

**Push-only**(no running window)- Median is
**updated at each push**(getting the median is always

)`O``(``1``)` **Space-efficient**:

space, D being the number of`O``(`D`)`*different*samples, not the*total*number of samples**Time-efficient**: push is`O``(``log``(`N`)``)`**Generic**:`T``:``Clone``+``Ord`**No unsafe****no_std**(optional): supports generic collections

Faster than other implementations if lots of samples have the same value. If this is not your case, you should use another implementation.

## Use

`use` `median_accumulator``::``*``;`
`let` `mut` acc `=` `vec``::``MedianAcc``::`new`(``)``;`
`assert_eq!``(`acc`.``get_median``(``)``,` `None``)``;`
acc`.``push``(``7``)``;`
`assert_eq!``(`acc`.``get_median``(``)``,` `Some``(``MedianResult``::`One`(``7``)``)``)``;`
acc`.``push``(``5``)``;`
`assert_eq!``(`acc`.``get_median``(``)``,` `Some``(``MedianResult``::`Two`(``5``,` `7``)``)``)``;`
acc`.``push``(``7``)``;`
`assert_eq!``(`acc`.``get_median``(``)``,` `Some``(``MedianResult``::`One`(``7``)``)``)``;`

If you ever encounter an

panic, please file an issue or send me an e-mail.`unreachable`

## no_std

Example with smallvec: (

feature required)`smallvec`

`use` `median_accumulator``::``*``;`
`let` `mut` acc `=` `MedianAcc``::``<``i32`, `smallvec``::`SmallVec`<``[``(``i32`, `u32``)``;` `64``]``>``>``::`new`(``)``;`

For other collections than

or `Vec`

, you must implement cc-traits and `SmallVec`

.`InsertIndex`

## License

CopyLeft 2022-2024 Pascal Engélibert (why copyleft?)

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, version 3 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.

You should have received a copy of the GNU Affero General Public License along with this program. If not, see https://www.gnu.org/licenses/.

#### Dependencies

~79KB