• 509
• 3
• 11

• 509
• 3
• 11

Overview

I’m trying to learn Rust, so I’m reading The Rust Programming Language. At Chapter 8, there was a task to write a program that calculates the median and mode of a bunch of numbers. I originally skipped the task and kept reading but I’ve returned to it as I think it will give me some practice with the language. I’ve designed my solution as a library crate that provides a function pub fn median_and_mode<T: Ord + Eq + Hash + Clone>(values: &mut [T]) -> Option<MedianAndMode<T>>.

The directory structure is as follows:

src
├── common.rs
├── lib.rs
├── select_and_iterate
│  └── test.rs
├── select_and_iterate.rs
└── test.rs

I took a hopefully more efficient approach to the task than sorting the list, by using the median of medians algorithm and quickselect, which I largely copied from Wikipedia, but slightly modified to also count each element. To do this I used a point in the algorithm where it already looped over every element. However, I’m unsure of if my use of a closure to do this might slow things down, as later iterations are passed a noop closure, which might slow things down a bit.

I used the proptest crate to create property-based tests for my code.

Here are the source files from my project:

lib.rs

mod common;
mod select_and_iterate;
#[cfg(test)]
mod test;
use std::{
 collections::{HashMap, HashSet},
 hash::Hash,
};
use crate::{common::noop, select_and_iterate::select_and_iterate};
#[derive(Debug, PartialEq, Eq)]
pub enum Median<T> {
 At(T),
 Between(T, T),
}
#[derive(Debug, PartialEq, Eq)]
pub struct Mode<T: Eq + Hash>(HashSet<T>);
#[derive(Debug, PartialEq, Eq)]
pub struct MedianAndMode<T: Eq + Hash> {
 pub median: Median<T>,
 pub mode: Mode<T>,
}
pub fn median_and_mode<T: Ord + Eq + Hash + Clone>(values: &mut [T]) -> Option<MedianAndMode<T>> {
 let len = values.len();
 if len == 0 {
 return None;
 }
 let mut frequencies = HashMap::new();
 let action = |x: &T| {
 let frequency = frequencies.entry((*x).clone()).or_insert(0);
 *frequency += 1;
 };
 let median;
 if len % 2 == 1 {
 let middle = len / 2;
 let Some(median_index) = select_and_iterate(values, middle, action)
 else { return None; };
 median = Median::At(values[median_index].clone());
 } else {
 let middle_1 = len / 2 - 1;
 let middle_2 = len / 2;
 let Some(median_1_index) = select_and_iterate(values, middle_1, action)
 else { return None; };
 let median_1 = values[median_1_index].clone();
 let Some(median_2_index) = select_and_iterate(values, middle_2, noop)
 else { panic!() };
 let median_2 = values[median_2_index].clone();
 if median_1 == median_2 {
 median = Median::At(median_1);
 } else {
 median = Median::Between(median_1, median_2);
 }
 }
 let mode = Mode(get_mode(frequencies));
 Some(MedianAndMode { median, mode })
}
fn get_mode<T: Eq + Hash>(frequencies: HashMap<T, usize>) -> HashSet<T> {
 let mut modes = HashSet::new();
 let mut highest_frequency = 0;
 for (value, frequency) in frequencies {
 match frequency.cmp(&highest_frequency) {
 std::cmp::Ordering::Less => {}
 std::cmp::Ordering::Equal => {
 modes.insert(value);
 }
 std::cmp::Ordering::Greater => {
 highest_frequency = frequency;
 modes.clear();
 modes.insert(value);
 }
 }
 }
 modes
}

select_and_iterate.rs

#[cfg(test)]
mod test;
use std::cmp::{min, Ordering};
use crate::common::noop;
// Algorithm stolen wholesale from Wikipedia: https://en.wikipedia.org/wiki/Median_of_medians
pub fn select_and_iterate<T: Ord + Clone>(
 values: &mut [T],
 index: usize,
 action: impl FnMut(&T),
) -> Option<usize> {
 let len = values.len();
 if len == 0 || index > len {
 return None;
 }
 Some(select_and_iterate_inner(values, index, action))
}
fn select_and_iterate_inner<T: Ord + Clone>(
 values: &mut [T],
 index: usize,
 mut action: impl FnMut(&T),
) -> usize {
 let len = values.len();
 debug_assert_ne!(len, 0);
 if len == 1 {
 debug_assert_eq!(index, 0);
 action(&values[0]);
 return 0;
 }
 let pivot_index = pivot(values);
 let pivot_index = partition(values, pivot_index, index, action);
 match index.cmp(&pivot_index) {
 Ordering::Less => select_and_iterate_inner(&mut values[0..pivot_index], index, noop),
 Ordering::Equal => pivot_index,
 Ordering::Greater => {
 select_and_iterate_inner(
 &mut values[pivot_index + 1..len],
 index - (pivot_index + 1),
 noop,
 ) + (pivot_index + 1)
 }
 }
}
fn pivot<T: Ord + Clone>(values: &mut [T]) -> usize {
 let len = values.len();
 if len <= 5 {
 return median_of_5(values);
 }
 for i in (0..len - 1).step_by(5) {
 let right_index = min(i + 4, len - 1);
 let median = median_of_5(&mut values[i..right_index]);
 values.swap(median, i / 5);
 }
 select_and_iterate_inner(&mut values[0..len / 5], (len - 1) / 10, noop)
}
fn median_of_5<T: Ord>(values: &mut [T]) -> usize {
 values.sort();
 (values.len() - 1) / 2
}
fn partition<T: Ord + Clone>(
 values: &mut [T],
 pivot_index: usize,
 target_index: usize,
 mut action: impl FnMut(&T),
) -> usize {
 let len = values.len();
 let pivot_value_ref = &values[pivot_index];
 action(pivot_value_ref);
 let pivot_value = pivot_value_ref.clone();
 values.swap(pivot_index, len - 1);
 let mut store_index = 0;
 for i in 0..len - 1 {
 action(&values[i]);
 if values[i] < pivot_value {
 values.swap(store_index, i);
 store_index += 1;
 }
 }
 let mut store_index_eq = store_index;
 for i in store_index..len - 1 {
 if values[i] == pivot_value {
 values.swap(store_index_eq, i);
 store_index_eq += 1;
 }
 }
 values.swap(len - 1, store_index_eq);
 if target_index < store_index {
 store_index
 } else if target_index <= store_index_eq {
 target_index
 } else {
 store_index_eq
 }
}

common.rs

pub fn noop<T>(_: &T) {}

test.rs

use super::{median_and_mode, Median, MedianAndMode, Mode};
use proptest::{collection::vec, prop_assert, prop_assert_eq, prop_assert_ne, proptest};
use std::collections::HashSet;
// See https://github.com/proptest-rs/proptest/issues/256
#[test]
fn test_median_and_mode_empty_array() {
 let mut values: [i128; 0] = [];
 let None = median_and_mode(&mut values)
 else { panic!("Wrong result pattern") };
}
#[test]
fn test_median_and_mode_1() {
 let mut values: [i128; 12] = [
 30050, 17767, 12534, -24364, 20538, -17, 690, -7966, -40, -1172, -25598, 34,
 ];
 let Some(MedianAndMode { median, mode }) = median_and_mode(&mut values)
 else { panic!() };
 assert_eq!(median, Median::Between(-17, 34));
 assert_eq!(mode, Mode(HashSet::from_iter(values.iter().copied())))
}
#[test]
fn test_median_and_mode_2() {
 let mut values: [i128; 9] = [
 7952,
 19412,
 -1450,
 6978825196251534519,
 11125,
 5270098434161345047,
 -13739,
 -27060,
 -467,
 ];
 let Some(MedianAndMode { median, mode }) = median_and_mode(&mut values)
 else { panic!("Wrong result pattern") };
 assert_eq!(median, Median::At(7952));
 assert_eq!(mode, Mode(HashSet::from_iter(values.iter().copied())));
}
proptest! {
 #[test]
 fn proptest_median_and_mode(mut values in vec(i8::MIN..i8::MAX, 1..32768)) {
 let len = values.len();
 if len == 0 {
 let None = median_and_mode(&mut values)
 else { panic!("Wrong result pattern") };
 } else {
 let Some(MedianAndMode { median, mode }) = median_and_mode(&mut values)
 else { panic!("Wrong result pattern") };
 values.sort();
 match median {
 Median::At(x) => {
 prop_assert_eq!(x, values[len / 2]);
 },
 Median::Between(x, y) => {
 prop_assert_eq!(x, values[len / 2 - 1]);
 prop_assert_eq!(y, values[len / 2]);
 },
 }
 let Mode(mode) = mode;
 prop_assert_ne!(mode.len(), 0);
 let mut frequencies = Vec::new();
 for value in mode {
 frequencies.push(values.iter().filter(|n| **n == value).count())
 };
 let first_frequency = frequencies[0];
 prop_assert!(first_frequency <= len);
 prop_assert!(frequencies.iter().all(|n| *n == first_frequency));
 }
 }
 #[test]
 fn proptest_median_and_mode_singleton_vec(value in i128::MIN..i128::MAX) {
 let mut values = vec![value];
 let Some(MedianAndMode { median, mode }) = median_and_mode(&mut values)
 else { panic!("Wrong result pattern") };
 prop_assert_eq!(median, Median::At(value));
 prop_assert_eq!(mode, Mode(HashSet::from([value])))
 }
}

select_and_iterate/test.rs

use super::select_and_iterate;
use crate::common::noop;
use proptest::{collection::vec, prop_assert, prop_assert_eq, proptest};
use std::collections::HashMap;
#[test]
fn test_select_empty_vec() {
 let mut values: Vec<i128> = vec![];
 let None = select_and_iterate(&mut values, 0, noop)
 else { panic!("Wrong result pattern") };
}
proptest! {
 #[test]
 fn proptest_select(mut values in vec(i8::MIN..i8::MAX, 1..32768), index in 0..usize::MAX) {
 let len = values.len();
 if len == 0 {
 let None = select_and_iterate(&mut values, index, noop)
 else { panic!("Wrong result pattern") };
 } else {
 let index = index % len;
 let mut frequencies = HashMap::new();
 let action = |x: &i8| {
 let frequency = frequencies.entry(*x).or_insert(0);
 *frequency += 1;
 };
 let Some(value_index) = select_and_iterate(&mut values, index, action)
 else { panic!() };
 let value = values[value_index];
 values.sort();
 prop_assert_eq!(value, values[index]);
 for (value, frequency) in frequencies {
 prop_assert!(values.contains(&value));
 prop_assert!(frequency <= len);
 }
 }
 }
 #[test]
 fn proptest_select_singleton_vec(value in i128::MIN..i128::MAX) {
 let mut counter = 0;
 let action = |_: &i128| {
 counter += 1;
 };
 let mut values = vec![value];
 let Some(0) = select_and_iterate(&mut values, 0, action)
 else { panic!("Wrong result pattern") };
 prop_assert_eq!(counter, 1);
 }
}

Questions

In particular, I’m interested in these questions:

• Is this code actually notably faster than the sorting method? In my tests it seemed to perform O(n), as Wikipedia suggested
• Does the use of a closure and passing noop to later iterations slow down the code notably?
• Is the structure and organization of the code sensible?
• Is the Clone requirement for median_and_mode sensible? I ran into issues with the borrow checker, which I still don’t fully understand, and used Clone, but I’m not sure if it’s a sensible requirement
• Is the Clone requirement for select_and_iterate sensible? It comes from the call to clone in pivot, where I assume it’s because the compiler must assume that the mutable borrow in swap might result in a dangling pointer. Would this be a good place to use unsafe? Or is there some hack I’m not aware of that might circumvent this need? I assume it’s not that big of a deal as any other use of the same code could just pass references to be compared, as is done here, too, to avoid median_and_mode taking a mutable reference