From 517381626f0d59b91519436b388ac505ced792f2 Mon Sep 17 00:00:00 2001 From: mathiasmagnusson Date: Sat, 26 Feb 2022 17:20:49 +0100 Subject: Initial commit --- kattis-kth-alginda-quicksort/src/main.rs | 28 +++++ kattis-kth-alginda-quicksort/src/radix_sort.rs | 141 +++++++++++++++++++++++++ 2 files changed, 169 insertions(+) create mode 100644 kattis-kth-alginda-quicksort/src/main.rs create mode 100644 kattis-kth-alginda-quicksort/src/radix_sort.rs (limited to 'kattis-kth-alginda-quicksort/src') diff --git a/kattis-kth-alginda-quicksort/src/main.rs b/kattis-kth-alginda-quicksort/src/main.rs new file mode 100644 index 0000000..67646b3 --- /dev/null +++ b/kattis-kth-alginda-quicksort/src/main.rs @@ -0,0 +1,28 @@ +// https://kth.kattis.com/problems/kth.alginda.quicksort + +#![feature(test)] + +use std::fmt::Write; +use std::io::{stdin, Read}; + +mod radix_sort; + +use radix_sort::radix_sort; + +fn main() { + let mut buffer = String::new(); + stdin().lock().read_to_string(&mut buffer).unwrap(); + let xs: Vec = buffer + .split_ascii_whitespace() + .skip(1) + .map(|x| x.parse().unwrap()) + .collect(); + + let xs = radix_sort(xs); + + buffer.clear(); + for x in xs { + writeln!(buffer, "{}", x).unwrap(); + } + print!("{}", buffer); +} diff --git a/kattis-kth-alginda-quicksort/src/radix_sort.rs b/kattis-kth-alginda-quicksort/src/radix_sort.rs new file mode 100644 index 0000000..e7d4e02 --- /dev/null +++ b/kattis-kth-alginda-quicksort/src/radix_sort.rs @@ -0,0 +1,141 @@ +use std::mem; + +pub trait RadixFilters: 'static { + const FILTERS: &'static [fn(&Self) -> u8]; +} + +impl RadixFilters for u32 { + const FILTERS: &'static [fn(&Self) -> u8] = &[ + |x| ((x & 0x000000ff) >> (8 * 0)) as _, + |x| ((x & 0x0000ff00) >> (8 * 1)) as _, + |x| ((x & 0x00ff0000) >> (8 * 2)) as _, + |x| ((x & 0xff000000) >> (8 * 3)) as _, + ]; +} + +impl RadixFilters for i32 { + const FILTERS: &'static [fn(&Self) -> u8] = &[ + |x| ((x & 0x000000ff) >> (8 * 0)) as _, + |x| ((x & 0x0000ff00) >> (8 * 1)) as _, + |x| ((x & 0x00ff0000) >> (8 * 2)) as _, + |x| (((x & 0xff000000u32 as i32) ^ (1 << 31)) >> (8 * 3)) as _, + ]; +} + +impl RadixFilters for u64 { + const FILTERS: &'static [fn(&Self) -> u8] = &[ + |x| ((x & 0x00000000000000ff) >> (8 * 0)) as _, + |x| ((x & 0x000000000000ff00) >> (8 * 1)) as _, + |x| ((x & 0x0000000000ff0000) >> (8 * 2)) as _, + |x| ((x & 0x00000000ff000000) >> (8 * 3)) as _, + |x| ((x & 0x000000ff00000000) >> (8 * 4)) as _, + |x| ((x & 0x0000ff0000000000) >> (8 * 5)) as _, + |x| ((x & 0x00ff000000000000) >> (8 * 6)) as _, + |x| ((x & 0xff00000000000000) >> (8 * 7)) as _, + ]; +} + +pub fn radix_sort(xs: Vec) -> Vec +where + T: Default + Copy + Clone + RadixFilters, +{ + // The first thing that happens it that these two are swapped so thats why this seems backwards + let mut output = xs; + let mut input = vec![T::default(); output.len()]; + for f in T::FILTERS { + mem::swap(&mut input, &mut output); + + let mut counts = [0; 256]; + for x in &input { + counts[f(x) as usize] += 1; + } + let mut sum = 0; + for c in &mut counts { + sum += *c; + *c = sum; + } + for x in input.iter_mut().rev() { + let fx = f(x) as usize; + counts[fx] -= 1; + output[counts[fx]] = *x; + } + } + output +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn basic_rand() { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec = (0..1_000_000).map(|_| r.next_u32()).collect(); + + let xs = radix_sort(xs); + for w in xs.as_slice().windows(2) { + assert!(w[0] <= w[1]); + } + } + + #[test] + fn negatives() { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec = (0..1_000_000).map(|_| r.next_u32() as i32).collect(); + + let xs = radix_sort(xs); + for w in xs.as_slice().windows(2) { + assert!(w[0] <= w[1], "{} <= {}", w[0], w[1]); + } + } + + extern crate test; + use rand::RngCore; + use test::{black_box, Bencher}; + + #[bench] + fn std_u32_x1e6(b: &mut Bencher) { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec = (0..1_000_000).map(|_| r.next_u32()).collect(); + + b.iter(|| { + let mut xs = black_box(xs.clone()); + xs.sort(); + black_box(xs); + }); + } + + #[bench] + fn radix_u32_x1e6(b: &mut Bencher) { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec = (0..1_000_000).map(|_| r.next_u32()).collect(); + + b.iter(|| { + let xs = black_box(xs.clone()); + black_box(radix_sort(xs)); + }); + } + + #[bench] + fn std_u64_x1e6(b: &mut Bencher) { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec = (0..1_000_000).map(|_| r.next_u64()).collect(); + + b.iter(|| { + let mut xs = black_box(xs.clone()); + xs.sort(); + black_box(xs); + }); + } + + #[bench] + fn radix_u64_x1e6(b: &mut Bencher) { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec = (0..1_000_000).map(|_| r.next_u64()).collect(); + + b.iter(|| { + let xs = black_box(xs.clone()); + black_box(radix_sort(xs)); + }); + } +} -- cgit v1.2.3