I have two one-line code snippets I haven't yet gotten correct in Rust.
1: Ruby|Crystal: return [2, 3, 5].select { |p| p <= val } if val < num
Rust: if val < num { return [2, 3, 5] ?? }
2: Ruby|Crystal: total = [2, 3, 5] + primes, where primes is array of primes
Rust: tried total = concat([2,3,5], primes), but get error message about concat
What do these do, specifically?
1: Ruby|Crystal: return [2, 3, 5].select { |p| p <= val } if val < num
Returns an array of the primes from [2,3,5] <= val, when val < num
Example: num = 7, val = 4 returns the array [2,3]
2: Ruby|Crystal: total = [2, 3, 5] + primes, where primes is array of primes
adds|appends|combines|concatentates into one array: [2,3,5] with primes
The first is Iterator::filter(), but what should it yield if the condition is not met?
Concatenation is Iterator::chain. You can then collect the iterator into anything appropriate, eg. a Vec.
For the 2nd one you can also use itertools::concat
The code returns an empty array when (p = 2) for (val = 0 or 1)
[2, 3, 5].select { |p| p <= val } if val < num ==> [] if val < 2
In case it's part of the confusion, Rust is strictly and statically typed, and the length of arrays is part of their type. So you can't dynamically generate an array of arbitrary size. If you want the result to be collected, you'll end up with a Vec.
Yes, I understand that, I was using generic language.
So how do you do it so it works?
Literally, that'd be something like
if val < num {
[2, 3, 5].iter().filter(|&p| p <= val).collect()
} else {
Vec::new()
}
One of many ways.
fn foo(val: u128, num: u128, primes: &[u128], more_primes: &[u128]) -> Vec<u128> {
let mut v: Vec<_> = (val < num)
.then(|| primes.iter().copied().filter(|p| p <= &val).collect())
.unwrap_or_default();
v.extend_from_slice(more_primes);
v
}
I had to add it to my Toml file first, then add: use itertools:concat;
It worked, but slows the program down significantly.
What I ended up doing, which actually made the program faster all around, was to first change
let primes = ... to let mut primes = ... and then just did
primes.push(2); primes.push(3); primes.push(5);
Its ugly, inelegant, but it gets the result I want, and it doesn't slow the program down.
If you can show me a prettier, and just as fast, alternative I'll use it.
In that case you can just do...
primes.extend([2,3,5]);
That didn't work!
Are you building it with optimizations enabled? cargo run --release
If so, please provide more code; preferably a complete program we can examine and run. It's likely that there is something to improve.
Here's the whole code, which currently give correct results for input >= 7.
This line doesn't work yet:
if num < RES[0] { return ([2, 3, 5].iter().filter(|&p| p <= num).collect()) } else { return Vec<usize>::new() }
Here's the whole program, which works as shown for values >= 7.
extern crate integer_sqrt;
extern crate num_cpus;
extern crate rayon;
use integer_sqrt::IntegerSquareRoot;
use rayon::prelude::*;
use std::sync::atomic::{AtomicU8, Ordering};
use std::time::SystemTime;
fn print_time(title: &str, time: SystemTime) {
print!("{} = ", title);
println!("{} secs", {
match time.elapsed() {
Ok(e) => e.as_secs() as f64 + e.subsec_nanos() as f64 / 1_000_000_000f64,
Err(e) => { panic!("Timer error {:?}", e) },
}
});
}
fn atomic_slice(slice: &mut [u8]) -> &[AtomicU8] {
unsafe { &*(slice as *mut [u8] as *const [AtomicU8]) }
}
fn sozp5(num: usize) -> Vec<usize> {
let (md, rescnt) = (30, 8); // P5's modulus and residues count
static RES: [usize; 8] = [7,11,13,17,19,23,29,31];
static BITN: [u8; 30] = [0,0,0,0,0,1,0,0,0,2,0,4,0,0,0,8,0,16,0,0,0,32,0,0,0,0,0,64,0,128];
//if num < RES[0] { return ([2, 3, 5].iter().filter(|&p| p <= num).collect()) } else { return Vec<usize>::new() }
let kmax = (num - 2) / md + 1;
let mut prms = vec![0u8; kmax];
let sqrt_n = num.integer_sqrt();
let (mut modk, mut r, mut k) = (0,0,0);
loop {
if r == rescnt { r = 0; modk += md; k += 1 }
if (prms[k] & (1 << r)) != 0 { r += 1; continue }
let prm_r = RES[r];
let prime = modk + prm_r;
if prime > sqrt_n { break }
let prms_atomic = atomic_slice(&mut prms);
RES.par_iter().for_each (|ri| {
let prod = prm_r * ri - 2;
let bit_r = BITN[prod % md];
let mut kpm = k * (prime + ri) + prod/md;
while kpm < kmax { prms_atomic[kpm].fetch_or(bit_r, Ordering::Relaxed); kpm += prime; };
});
r += 1;
}
let mut primes: Vec<usize> = RES.par_iter().enumerate().flat_map_iter( |(i, ri)| {
prms.iter().enumerate().filter_map(move |(k, resgroup)| {
if resgroup & (1 << i) == 0 {
let prime = md * k + ri;
if prime <= num { return Some(prime) }
} None
}) }).collect();
primes.push(2); primes.push(3); primes.push(5);
primes
}
fn main() {
let mut val = String::new();
std::io::stdin().read_line(&mut val).expect("Failed to read line");
let mut substr_iter = val.split_whitespace();
let mut next_or_default = |def| -> usize {
substr_iter.next().unwrap_or(def).parse().expect("Input is not a number")
};
let num = next_or_default("0");
println!("threads = {}", num_cpus::get());
let ts = SystemTime::now();
let primes: Vec<usize> = sozp5(num);
print_time("total time", ts);
println!("total primes = {}", primes.len());
}
Is this a continuation of the discussion you were having with @Michael-F-Bryan here (A humble request/challenge - #6 by jzakiya) ?
I'm creating a new smaller sieve extracted from the larger code, which includes adding the primes < RES[0] for just the P5 generator (this is for the book I'm writing). I'm comparing it to the Ruby, and Crystal versions to show performance differences in various languages. The code as shown produces all the primes up to any N >= 7, the RES[0] of P5. As shown, that's super simple to do in Ruby|Crystal, and for apples-to-apples functionality I want to do that in the Rust version too.
Rust is very good if you know what to do, but (currently) it's too complex|verbose for me to use (as my requests for these examples illustrate) for development purposes. I only use it for better performance after I know what to do from Ruby|Crystal. But that's another discussion, so please don't focus on that.
This works:
primes.extend(&[2, 3, 5]);
This seems a smidgen faster:
primes.extend_from_slice(&[2, 3, 5]);