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/Cargo.lock | 85 ++++++++++++++ kattis-kth-alginda-quicksort/Cargo.toml | 12 ++ kattis-kth-alginda-quicksort/gen.py | 11 ++ kattis-kth-alginda-quicksort/radix.c | 146 +++++++++++++++++++++++++ kattis-kth-alginda-quicksort/src/main.rs | 28 +++++ kattis-kth-alginda-quicksort/src/radix_sort.rs | 141 ++++++++++++++++++++++++ kattis-kth-alginda-quicksort/test.fish | 10 ++ 7 files changed, 433 insertions(+) create mode 100644 kattis-kth-alginda-quicksort/Cargo.lock create mode 100644 kattis-kth-alginda-quicksort/Cargo.toml create mode 100644 kattis-kth-alginda-quicksort/gen.py create mode 100644 kattis-kth-alginda-quicksort/radix.c create mode 100644 kattis-kth-alginda-quicksort/src/main.rs create mode 100644 kattis-kth-alginda-quicksort/src/radix_sort.rs create mode 100755 kattis-kth-alginda-quicksort/test.fish (limited to 'kattis-kth-alginda-quicksort') diff --git a/kattis-kth-alginda-quicksort/Cargo.lock b/kattis-kth-alginda-quicksort/Cargo.lock new file mode 100644 index 0000000..b3ab7a2 --- /dev/null +++ b/kattis-kth-alginda-quicksort/Cargo.lock @@ -0,0 +1,85 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "getrandom" +version = "0.2.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d39cd93900197114fa1fcb7ae84ca742095eed9442088988ae74fa744e930e77" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "kattis-kth-alginda-quicksort" +version = "0.1.0" +dependencies = [ + "rand", + "rand_pcg", +] + +[[package]] +name = "libc" +version = "0.2.119" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1bf2e165bb3457c8e098ea76f3e3bc9db55f87aa90d52d0e6be741470916aaa4" + +[[package]] +name = "ppv-lite86" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eb9f9e6e233e5c4a35559a617bf40a4ec447db2e84c20b55a6f83167b7e57872" + +[[package]] +name = "rand" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +dependencies = [ + "libc", + "rand_chacha", + "rand_core", +] + +[[package]] +name = "rand_chacha" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +dependencies = [ + "ppv-lite86", + "rand_core", +] + +[[package]] +name = "rand_core" +version = "0.6.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d34f1408f55294453790c48b2f1ebbb1c5b4b7563eb1f418bcfcfdbb06ebb4e7" +dependencies = [ + "getrandom", +] + +[[package]] +name = "rand_pcg" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "59cad018caf63deb318e5a4586d99a24424a364f40f1e5778c29aca23f4fc73e" +dependencies = [ + "rand_core", +] + +[[package]] +name = "wasi" +version = "0.10.2+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fd6fbd9a79829dd1ad0cc20627bf1ed606756a7f77edff7b66b7064f9cb327c6" diff --git a/kattis-kth-alginda-quicksort/Cargo.toml b/kattis-kth-alginda-quicksort/Cargo.toml new file mode 100644 index 0000000..4968225 --- /dev/null +++ b/kattis-kth-alginda-quicksort/Cargo.toml @@ -0,0 +1,12 @@ +[package] +name = "kattis-kth-alginda-quicksort" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dev-dependencies] +rand = "0.8" +rand_pcg = "0.3" + +[dependencies] diff --git a/kattis-kth-alginda-quicksort/gen.py b/kattis-kth-alginda-quicksort/gen.py new file mode 100644 index 0000000..37c4095 --- /dev/null +++ b/kattis-kth-alginda-quicksort/gen.py @@ -0,0 +1,11 @@ +from random import randint as r +from sys import argv + +lo = int(argv[1]) +hi = int(argv[2]) +n = int(argv[3]) + +xs = [r(lo, hi) for _ in range(n)] + +print(len(xs), " ") +print(' \n '.join(str(x) for x in xs)) diff --git a/kattis-kth-alginda-quicksort/radix.c b/kattis-kth-alginda-quicksort/radix.c new file mode 100644 index 0000000..babc0ec --- /dev/null +++ b/kattis-kth-alginda-quicksort/radix.c @@ -0,0 +1,146 @@ +/* https://kth.kattis.com/problems/kth.alginda.quicksort */ + +#include +#include +#include +#include +#include +#include +/* #include */ + +// longest int: -2147483648 +#define BUFFER_MAX (12 * 600000) +char buffer[BUFFER_MAX]; +int xs[600000]; +int tmp[600000]; + +int *radix_sort(int n) { + int *out = xs; + int *in = tmp; + // we loop an even amount of times so the completely sorted array + // will be in xs, not tmp + for (int m = 0; m < 32; m += 8) { + int *tmp = out; + out = in; + in = tmp; + + int counts[256] = { 0 }; + for (int i = 0; i < n; i++) + counts[(uint8_t) (in[i] >> m)]++; + + int sum = 0; + for (int i = 0; i < 256; i++) { + sum += counts[i]; + counts[i] = sum; + } + for (int i = n - 1; i >= 0; i--) { + uint8_t fx = in[i] >> m; + counts[fx]--; + out[counts[fx]] = in[i]; + } + } +} + +int main() { + /* char *buffer = malloc(BUFFER_MAX); */ + /* ssize_t len = 0; */ + /* while (true) { */ + /* if (len >= BUFFER_MAX) return 1; */ + /* ssize_t r = read(0, &buffer[len], BUFFER_MAX - len); */ + /* len += r; */ + /* if (r == 0) */ + /* break; */ + /* } */ + ssize_t len = read(0, buffer, BUFFER_MAX); + + int curr = 0; + int n = 0; + while (buffer[curr] != ' ' && buffer[curr] != '\n') { + n *= 10; + n += buffer[curr] - '0'; + curr++; + } + while (buffer[curr] == ' ' || buffer[curr] == '\n') curr++; + + for (int i = 0; i < n; i++) { + int x = 0; + bool neg = false; + if (buffer[curr] == '-') { + neg = true; + curr++; + } + while (curr < len && buffer[curr] != ' ' && buffer[curr] != '\n') { + x *= 10; + x += buffer[curr] - '0'; + curr++; + } + while (curr < len && (buffer[curr] == ' ' || buffer[curr] == '\n')) curr++; + + if (neg) x = -x; + xs[i] = x ^ (1 << 31); + } + + radix_sort(n); + + len = 0; + for (int i = 0; i < n; i++, len += 12) { + long x = xs[i] ^ (1 << 31); + bool neg = false; + if (x < 0) { + neg = true; + x = -x; + } + int j = 11; + buffer[len + j--] = '\n'; + do { + buffer[len + j--] = (x % 10) + '0'; + x /= 10; + } while (x > 0); + if (neg) buffer[len + j--] = '-'; + while (j >= 0) buffer[len + j--] = ' '; + } + + /* + len = 0; + + __m256i highestbit = _mm256_set1_epi32(1 << 32); + __m256i zero = _mm256_set1_epi32(0); + __m256i lens = _mm256_set_epi32(0 * 12, + 1 * 12, + 2 * 12, + 3 * 12, + 4 * 12, + 5 * 12, + 6 * 12, + 7 * 12); + __m256i lenoffset = _mm256_set1_epi(8 * 12); + + for (int i = 0; i < n; i += 8) { + // long x = xs[i] ^ (1 << 31); + __m256i xx = _mm256_load_si256(&xs[i]); + xx = _mm256_xor_si256(xx, highestbit); + // bool neg = false; + // if (x < 0) { + // neg = true; + // x = -x; + // } + __m256i negs = _mm256_cmpgt(zero, xx); + xx = _mm256_abs_epi64(xx); + // todo... + int j = 11; + buffer[len + j--] = '\n'; + do { + buffer[len + j--] = (x % 10) + '0'; + x /= 10; + } while (x > 0); + if (neg) buffer[len + j--] = '-'; + while (j >= 0) buffer[len + j--] = ' '; + + // len += 8 * 12 + lens = _mm256_add_epi32(lens, lenoffset); + } + */ + /* ssize_t c = 0; */ + /* while (c < len) c += write(1, &buffer[c], len - c); */ + write(1, buffer, len); +} 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)); + }); + } +} diff --git a/kattis-kth-alginda-quicksort/test.fish b/kattis-kth-alginda-quicksort/test.fish new file mode 100755 index 0000000..6aaf60c --- /dev/null +++ b/kattis-kth-alginda-quicksort/test.fish @@ -0,0 +1,10 @@ +#!/bin/fish + +echo hej > out_c +echo hej > out_r + +while diff out_c out_r + python gen.py -2147483648 2147483647 600000 > max + time ./radix < max > out_r + time ~/.cache/target/release/kattis-kth-alginda-quicksort < max > out_c +end -- cgit v1.2.3