3 ms·

I'm genuinely surprised that the Picat is so much faster than the C++. I assumed it would be easier to write, but also slower.

by hwayne 2y ago

Karliss 2y ago
I have a feeling that it might be due to C++ solution not being proper BFS since it doesn't have anything preventing the visiting of same state multiple times. One thing that slightly tripped me is that full BFS state space without additional tricks is in theory N^2 (current length x copied length) . Also the memory usage for C++ solution is ~1.8GB and bumping N to 200K increased it to 6GB . I assume that Picat automatically detects and prevents duplicate computation on identical states. Got nerd sniped. If you think about the problem a bit harder (but not hard to go into math of prime factors) there is a dynamic programming solution. The code for obtaining only steps is a bit simpler, but it can be also extended to recover full answer https://gist.github.com/karliss/5ca978390791daca71a1d812c43a924c https://gist.github.com/karliss/5ca978390791daca71a1d812c43a... Had no issue obtaining full 9104 step solution for ==100001 . On my computer: C++ DP: <0.003s C++ from article: 3.032s Memory usage of DP solution is linear. The double nested loops look a bit scary, but it actually forms harmonic series sum: `sum (n/i) ~ n log n` so the speed isn't bad for non analytic solution. The main insight for fast DP solution is how to reduce the state space from NxN (lenght X copied length) to N. All solutions will be in form (SC(P)+)+. Once you know minimum step count for reaching some length, you don't care about what the currently copied length is. Assuming you reach some length L_2 = L_1 * i, any solutions L_1(i+j) would already be processed when handling L_1, means you only need to updated L_2 (i). Now that I have written it I get where the factorization related math talk in stack exchange comes from.

I'm genuinely surprised that the Picat is so much faster than the C++. I assumed it would be easier to write, but also slower.

by hwayne 2y ago

I'm genuinely surprised that the Picat is so much faster than the C++. I assumed it would be easier to write, but also slower.

Karliss 2y ago

I have a feeling that it might be due to C++ solution not being proper BFS since it doesn't have anything preventing the visiting of same state multiple times. One thing that slightly tripped me is that full BFS state space without additional tricks is in theory N^2 (current length x copied length) . Also the memory usage for C++ solution is ~1.8GB and bumping N to 200K increased it to 6GB . I assume that Picat automatically detects and prevents duplicate computation on identical states. Got nerd sniped. If you think about the problem a bit harder (but not hard to go into math of prime factors) there is a dynamic programming solution. The code for obtaining only steps is a bit simpler, but it can be also extended to recover full answer https://gist.github.com/karliss/5ca978390791daca71a1d812c43a924c https://gist.github.com/karliss/5ca978390791daca71a1d812c43a... Had no issue obtaining full 9104 step solution for ==100001 . On my computer: C++ DP: <0.003s C++ from article: 3.032s Memory usage of DP solution is linear. The double nested loops look a bit scary, but it actually forms harmonic series sum: `sum (n/i) ~ n log n` so the speed isn't bad for non analytic solution. The main insight for fast DP solution is how to reduce the state space from NxN (lenght X copied length) to N. All solutions will be in form (SC(P)+)+. Once you know minimum step count for reaching some length, you don't care about what the currently copied length is. Assuming you reach some length L_2 = L_1 * i, any solutions L_1(i+j) would already be processed when handling L_1, means you only need to updated L_2 (i). Now that I have written it I get where the factorization related math talk in stack exchange comes from.