Added a small benchmark, the output can be shown with "cargo test -- --nocapture" locally.
pub fn sort_desc(mut n: u64) -> u64 { let mut digit_counts = [0; 10]; while n > 0 { let digit = (n % 10) as usize; digit_counts[digit] += 1; n /= 10; } let mut result = 0; let mut fac = 1; for digit in 0..10 { for _ in 0..digit_counts[digit] { result += (digit as u64) * fac; fac *= 10; } } result } use std::iter::repeat; pub fn sort_desc_it(mut n: u64) -> u64 { let mut digit_counts = [0; 10]; while n > 0 { digit_counts[n as usize % 10] += 1; n /= 10; } digit_counts .into_iter() .enumerate() .rev() .flat_map(|(digit, count)| repeat(digit as u64).take(count)) .fold(0, |result, digit| result * 10 + digit) } use std::time::Instant; fn benchmark<F>(func: F, input: u64, iterations: u32) -> (u64, f64) where F: Fn(u64) -> u64, { let mut total_duration = 0.0; let mut result = 0; for _ in 0..iterations { let start = Instant::now(); result = func(input); let duration = start.elapsed(); total_duration += duration.as_secs_f64(); } let avg_duration = total_duration / iterations as f64; (result, avg_duration) }
- pub fn sort_desc(mut n: u64) -> u64 {
- let mut digit_counts = [0; 10];
- while n > 0 {
- let digit = (n % 10) as usize;
- digit_counts[digit] += 1;
- n /= 10;
- }
- let mut result = 0;
- let mut fac = 1;
- for digit in 0..10 {
- for _ in 0..digit_counts[digit] {
- result += (digit as u64) * fac;
- fac *= 10;
- }
- }
- result
- }
- use std::iter::repeat;
pub fn sort_desc(mut n: u64) -> u64 {- pub fn sort_desc_it(mut n: u64) -> u64 {
- let mut digit_counts = [0; 10];
- while n > 0 {
- digit_counts[n as usize % 10] += 1;
- n /= 10;
- }
- digit_counts
- .into_iter()
- .enumerate()
- .rev()
- .flat_map(|(digit, count)| repeat(digit as u64).take(count))
- .fold(0, |result, digit| result * 10 + digit)
}- }
- use std::time::Instant;
- fn benchmark<F>(func: F, input: u64, iterations: u32) -> (u64, f64)
- where
- F: Fn(u64) -> u64,
- {
- let mut total_duration = 0.0;
- let mut result = 0;
- for _ in 0..iterations {
- let start = Instant::now();
- result = func(input);
- let duration = start.elapsed();
- total_duration += duration.as_secs_f64();
- }
- let avg_duration = total_duration / iterations as f64;
- (result, avg_duration)
- }
#[cfg(test)] mod tests { use super::*; fn do_test(number: u64, expected: u64) { let actual = sort_desc(number); assert_eq!( actual, expected, "For {} expected {} but got {}", number, expected, actual ); } #[test] fn test_sort_desc() { do_test(0, 0); do_test(1, 1); do_test(12, 21); do_test(123, 321); do_test(310, 310); do_test(12034, 43210); do_test(12345, 54321); do_test(123456789, 987654321); do_test(1234567890, 9876543210); } #[test] fn benchmark_max_num() { let numbers = vec![ 1234567890, 9876543210, 112233445566778899, 987654321987654321, ]; let iterations = 1000; for (ix, func) in [sort_desc, sort_desc_it].iter().enumerate() { if ix == 0 { println!("sort_desc:"); } else { println!("sort_desc_it:"); } for &number in &numbers { let (result, avg_duration) = benchmark(func, number, iterations); println!( "Max number formed from {}: {} (average time: {:.9} seconds)", number, result, avg_duration ); } } } }
- #[cfg(test)]
- mod tests {
use super::sort_desc;- use super::*;
- fn do_test(number: u64, expected: u64) {
- let actual = sort_desc(number);
assert_eq!(actual, expected, "For {} expected {} but got {}", number, expected, actual);- assert_eq!(
- actual, expected,
- "For {} expected {} but got {}",
- number, expected, actual
- );
- }
- #[test]
- fn test_sort_desc() {
- do_test(0, 0);
- do_test(1, 1);
- do_test(12, 21);
- do_test(123, 321);
- do_test(310, 310);
- do_test(12034, 43210);
- do_test(12345, 54321);
- do_test(123456789, 987654321);
- do_test(1234567890, 9876543210);
- }
- #[test]
- fn benchmark_max_num() {
- let numbers = vec![
- 1234567890,
- 9876543210,
- 112233445566778899,
- 987654321987654321,
- ];
- let iterations = 1000;
- for (ix, func) in [sort_desc, sort_desc_it].iter().enumerate() {
- if ix == 0 {
- println!("sort_desc:");
- } else {
- println!("sort_desc_it:");
- }
- for &number in &numbers {
- let (result, avg_duration) = benchmark(func, number, iterations);
- println!(
- "Max number formed from {}: {} (average time: {:.9} seconds)",
- number, result, avg_duration
- );
- }
- }
- }
- }
This doesn't allocate and doesn't use crates, it works by counting digits using an array.
It's faster.
pub fn sort_desc(mut n: u64) -> u64 { let mut digit_counts = [0; 10]; while n > 0 { let digit = (n % 10) as usize; digit_counts[digit] += 1; n /= 10; } let mut result = 0; let mut fac = 1; for digit in 0..10 { for _ in 0..digit_counts[digit] { result += (digit as u64) * fac; fac *= 10; } } result }
use itertools::Itertools;fn sort_desc(number: u64) -> u64 {number.to_string().chars().sorted().rev().collect::<String>().parse().unwrap()- pub fn sort_desc(mut n: u64) -> u64 {
- let mut digit_counts = [0; 10];
- while n > 0 {
- let digit = (n % 10) as usize;
- digit_counts[digit] += 1;
- n /= 10;
- }
- let mut result = 0;
- let mut fac = 1;
- for digit in 0..10 {
- for _ in 0..digit_counts[digit] {
- result += (digit as u64) * fac;
- fac *= 10;
- }
- }
- result
- }
#[cfg(test)] mod tests { use super::sort_desc; fn do_test(number: u64, expected: u64) { let actual = sort_desc(number); assert_eq!(actual, expected, "For {} expected {} but got {}", number, expected, actual); } #[test] fn test_sort_desc() { do_test(0, 0); do_test(1, 1); do_test(12, 21); do_test(123, 321); do_test(12345, 54321); do_test(123456789, 987654321); do_test(1234567890, 9876543210); } }
- #[cfg(test)]
- mod tests {
- use super::sort_desc;
- fn do_test(number: u64, expected: u64) {
- let actual = sort_desc(number);
- assert_eq!(actual, expected, "For {} expected {} but got {}", number, expected, actual);
- }
- #[test]
- fn test_sort_desc() {
- do_test(0, 0);
- do_test(1, 1);
- do_test(12, 21);
- do_test(123, 321);
- do_test(12345, 54321);
- do_test(123456789, 987654321);
- do_test(1234567890, 9876543210);
- }
#[test]fn random_test() {fn solution(number: u64) -> u64 {let mut number = number.to_string().chars().map(|c| c.to_digit(10).unwrap() as u64).collect::<Vec<u64>>();number.sort();number.iter().rev().map(|c| c.to_string()).collect::<Vec<String>>().join("").parse::<u64>().unwrap()}for _ in 0..100 {let number = rand::random::<u32>();do_test(number as u64, solution(number as u64));}}- }