7 ms·
In the spirit of "every programmer loves to fizzbuzz", I rewrote this in Rust. Aside from rewriting it in a different language, the biggest change I made was on
by chucksmash 11y ago
In the spirit of "every programmer loves to fizzbuzz", I rewrote this in Rust. Aside from rewriting it in a different language, the biggest change I made was only doing trial division against known primes <= the square root of a number we are checking for primality. Able to get the first 1,000,000 primes in 20 seconds:
use std::collections::HashMap;
pub fn first_n_primes(n: u64) -> Vec<u64> {
let mut primes = Vec::new();
let mut candidate = 3;
let mut count = 0;
if n >= 1 {
primes.push(2);
count += 1;
}
while count <= n {
let candidate_sqrt = ((candidate as f64).sqrt().ceil() + 1.0) as u64;
let mut is_prime: bool = true;
for prime in &primes {
if candidate % prime == 0 {
is_prime = false;
break;
}
if prime > &candidate_sqrt {
break;
}
}
if is_prime {
primes.push(candidate);
count += 1;
}
candidate += 2;
}
primes
}
fn main() {
let mut last_digit_pair_counts: HashMap<String, u64> = HashMap::new();
let primes = first_n_primes(1000000);
for i in 0..(primes.len() - 1) {
let last_digit0 = primes[i] % 10;
let last_digit1 = primes[i+1] % 10;
let digit_str = format!("{}-{}", last_digit0, last_digit1).to_string();
let counter = last_digit_pair_counts.entry(digit_str).or_insert(0);
*counter += 1;
}
last_digit_pair_counts.remove("2-3");
last_digit_pair_counts.remove("3-5");
last_digit_pair_counts.remove("5-7");
let mut ordered_keys: Vec<String> = last_digit_pair_counts.keys().cloned().collect();
ordered_keys.sort();
for key in &ordered_keys {
println!("{}: {}", key, last_digit_pair_counts[key]);
}
}
which outputs:
1-1: 42853
1-3: 77475
1-7: 79453
1-9: 50153
3-1: 58255
3-3: 39668
3-7: 72828
3-9: 79358
7-1: 64230
7-3: 68595
7-7: 39603
7-9: 77586
9-1: 84596
9-3: 64371
9-7: 58130
9-9: 42843
- steveklabnik 11y agoSmall speed note: Rust 1.7 just made custom hashing functions available. Rust uses a cryptographically secure hashing function by default, but for work like this, that's inappropriate. To use FNV instead: 1. add fnv to your Cargo.toml's dependencies section 2. The first few lines become: extern crate fnv; use std::collections::HashMap; use std::hash::BuildHasherDefault; use fnv::FnvHasher; type MyHasher = BuildHasherDefault<FnvHasher>; 2. and the hash creation line becomes let mut last_digit_pair_counts: HashMap<String, u64, MyHasher> = HashMap::default(); This is 17% faster on my two runs of your code. :) Other notes: format!("{}-{}", last_digit0, last_digit1).to_string(); The .to_string() is redundant here, format! already gives you a String. That should remove a bunch of allocations.
- chucksmash 11y agoThanks for taking time to give pointers to a noob Rustacean - this made my day.
- steveklabnik 11y agoAny time :) Oh, one other thing: I noticed you said 20 seconds. Mine took about 4 seconds, and I was wondering where the difference was... did you compile with optimizations? Without, it takes 22s on my machine... `--release` as an argument to Cargo, or `-C opt-level=3` as an argument to rustc.
- dr_zoidberg 11y agoIt's good to see this over a different language. I like how when working on larger data the 3-9 transition looses a big part of its "advantage" over the 3-7 transition. 9 is still the prefered/most probable "end-digit follower" for primes ending in 3, but it jumped form being alost 20% more probable (10k) to about 12% (1m).
- Houshalter 11y agoOh this is fun. I tried it in Lua: primes = {} function inPrimes(n) for _, v in ipairs(primes) do if n%v == 0 then return false end if v > math.ceil(math.sqrt(n)) then break end end return true end for i = 3, 1.6e7, 2 do if inPrimes(i) then table.insert(primes, i) end end last = '7' totalDigits = {} for i = 4, #primes do c = last..tostring(primes[i]):sub(-1) totalDigits[c] = totalDigits[c] and totalDigits[c] + 1 or 1 last = c:sub(-1) end for k, v in pairs(totalDigits) do print(k, v) end Gets just as many primes and runs in 7 seconds in LuaJIT.
- Houshalter 11y agoComputed up to 1e9: 79 3796948 37 3595468 19 2744958 97 3046626 31 3046813 71 3243702 93 3243354 33 2229686 11 2328414 73 3443707 99 2328896 17 3842263 39 3840531 77 2227956 13 3795751 91 4092457
- eddyb 11y agoIn a sibling answer, steveklabnik suggests the Rust version was compiled without optimizations - https://news.ycombinator.com/item?id=11285569 https://news.ycombinator.com/item?id=11285569 Could you try running both on the same machine? I'm curious if LuaJIT can still beat Rust if both have optimizations working. I know it can beat native code sometimes, which is pretty impressive (it finds common cases and specializes to them AFAIK, almost like "sufficiently advanced optimizing compiler" fairy tales).
- Houshalter 11y agoI don't know how to Rust, but you are welcome to try it. LuaJIT is amazingly fast. It shouldn't be faster than native code in general, but it's still not orders of magnitude behind like interpreted languages are. As I understand it, JITs can sometimes do better by doing statistics on code paths and optimizing them. And of course, it takes 0 seconds to compile, if you factor in that time : )
- mudita 11y agoHaskell: import Data.Numbers.Primes import Data.Counter countPrimeTransitions n = count $ zip primeEndings (tail primeEndings) where primeEndings = take (n+1) (map (`mod` 10) primes)
- odbol_ 11y agoI have no idea what's happening but I think you just won