Leetcode palindrome prime fasted solutions
November 28, 2020 ยท View on GitHub
Several solutions with 0ms execution time and benchmarks for prime-palindrome problem on leetcode.
Benchmark result
Benchmark_primePalindrome/letientai299-12 20000 95646 ns/op 1008 B/op 29 allocs/op
Benchmark_primePalindrome/unknown-12 5000 252136 ns/op 0 B/op 0 allocs/op
Benchmark_primePalindrome/tjucoder-12 500 2118324 ns/op 524816 B/op 36900 allocs/op
unknownguy's solution does zero allocation, and cool trick to generate palindrome with odds number of digits, but his solution need to check many more palindrome numbers than mine.tjucoder's solution works withstring, thus require many more allocation and also his palindrome generation is not effective.- Mine is currently the fastest thanks to: generate potental palindrome as list
of
intdigits (so less allocation and conversion), filter out those palindrome that can't be prime.
If you have faster solutions, feel free to submit an MR. Note that:
big.NewInt().ProbablyPrime()has terrible performance in the problem space (int). I got 4512 ms before switch to simple prime test up tosqrt(n).
Disclaimer
- I finish my solution without refer to either others solutions.
- This's for fun only (because I write quite a lot of code for this
problems, so I want to know if it worth it). These code're not for production
usage and I don't know if the performance of those solutions are still in above
order if the problem space is bigger (from
inttouint64orbig.Int).