diff options
Diffstat (limited to 'kattis-kth/alginda-quicksort/src')
| -rw-r--r-- | kattis-kth/alginda-quicksort/src/main.rs | 72 | ||||
| -rw-r--r-- | kattis-kth/alginda-quicksort/src/radix_sort.rs | 151 |
2 files changed, 223 insertions, 0 deletions
diff --git a/kattis-kth/alginda-quicksort/src/main.rs b/kattis-kth/alginda-quicksort/src/main.rs new file mode 100644 index 0000000..afb23f7 --- /dev/null +++ b/kattis-kth/alginda-quicksort/src/main.rs @@ -0,0 +1,72 @@ +// https://kth.kattis.com/problems/kth.alginda.quicksort + +#![feature(test)] + +use std::io::{stdin, stdout, Read, Write}; + +mod radix_sort; +use radix_sort::radix_sort; + +fn main() { + let mut buffer = String::new(); + stdin().lock().read_to_string(&mut buffer).unwrap(); + let mut p = buffer.bytes(); + let mut n = 0; + while let Some(b) = p.next() { + if b == b' ' { + break; + } + n *= 10; + n += (b - b'0') as usize; + } + let mut xs = vec![0; n]; + for i in 0..n { + let mut neg = false; + let mut x = 0i32; + while let Some(b) = p.next() { + match b { + b' ' | b'\n' => break, + b'-' => neg = true, + b => { + x *= 10; + x += (b - b'0') as i32; + } + } + } + if neg { + x = -x; + } + xs[i] = x; + } + + radix_sort(&mut xs); + + let mut p = buffer.len() - 1; + let b = unsafe { buffer.as_mut_vec() }; + b[p] = b'\n'; + p -= 1; + for i in (0..n).rev() { + let x = xs[i]; + let neg = x < 0; + let mut x = if neg { (-x) as u32 } else { x as u32 }; + loop { + b[p] = (x % 10) as u8 + b'0'; + p -= 1; + x /= 10; + if x == 0 { + break; + } + } + if neg { + b[p] = b'-'; + p -= 1; + } + if i > 0 { + b[p] = b'\n'; + p -= 1; + } + } + p += 1; + + stdout().lock().write(&b[p..]).unwrap(); +} 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..2f8d32a --- /dev/null +++ b/kattis-kth/alginda-quicksort/src/radix_sort.rs @@ -0,0 +1,151 @@ +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_with<T>(xs: &mut [T], temp: &mut [T]) +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 = temp; + debug_assert!(T::FILTERS.len() % 2 == 0); + for f in T::FILTERS { + mem::swap(&mut input, &mut output); + + let mut counts = [0; 256]; + for x in input.iter() { + 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; + } + } +} + +pub fn radix_sort<T>(xs: &mut [T]) +where + T: Default + Copy + Clone + RadixFilters, +{ + let n = xs.len(); + radix_sort_with(xs, vec![Default::default(); n].as_mut_slice()); +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn basic_rand() { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let mut xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect(); + + radix_sort(&mut 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 mut xs: Vec<i32> = (0..1_000_000).map(|_| r.next_u32() as i32).collect(); + + radix_sort(&mut 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<u32> = (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<u32> = (0..1_000_000).map(|_| r.next_u32()).collect(); + + b.iter(|| { + let mut xs = black_box(xs.clone()); + radix_sort(&mut xs); + black_box(xs); + }); + } + + #[bench] + fn std_u64_x1e6(b: &mut Bencher) { + let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7); + let xs: Vec<u64> = (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<u64> = (0..1_000_000).map(|_| r.next_u64()).collect(); + + b.iter(|| { + let mut xs = black_box(xs.clone()); + radix_sort(&mut xs); + black_box(xs); + }); + } +} |