Comments (10)
How do you store the already found polycubes to check if a polycubes is new ?
In my implementation (https://gitlab.com/dzamlo/polycubes), this is the issue, it consumes too much ram and is killed for n=14.
Regarding the speed, on my laptop with 16 threads, I can compute N=13 in less than 19 minutes, but my implementation is already multithreaded.
I also, f(13) = 138462649 not 138457022. See https://oeis.org/A000162 for value up to N=14.
from cubes.
Hi dzamlo,
The key is that I don't store the already found polycubes.
For every polycube I find, I have a function that does a 'race' to figure out if the cube and rotation we're using as a starting point for the polycube results is the 'first' time the polycube would be explored. That may sound impossible, but if you only develop the polycubes in a specific order (like in the order of a deterministic breath-first search), and not randomly,
there's 'only' 24*N different competitors every time you run the 'race'. (24 is the # of symmetries and N is the number of cubes that could act as a starting point.)
The space usage is small ( O(n^3) ) (or lower if I really wanted it be), but the time taken is still exponential.
The time it takes is something like O( A(n) * n * log(n) )
where 'A(n)' is the number of answers which seem to increase exponentially, and n is the number of cubes.
I think I could do some simple changes to squeeze out a bit more performance. I'll make those changes and I'll make more formal documentation as soon as I have time.
Also, thanks for pointing out the error. I think the algorithm is correct and I just copied the number of solutions from the last heartbeat message... :(
I'll rerun to make sure it's the case. I'm sorry about that.
from cubes.
Thanks for reaching out by the way. And if were keeping score, N=13 took me around 28 minutes with the latest optimizations, but I just used a single CPU. Later on, I'll get my algo to be distributed to multiple machines, and get a speed boost that scales with the number of machines.
from cubes.
Well done for your work! I think you will flat out beat my implementation when you implement parallel processing.
from cubes.
I ported your implementation to rust: https://gitlab.com/dzamlo/polycubes2
It is slightly faster than your implementation (1m24 vs 2m55 for n=12 on my machine)
There is still some not very idiomatic code I need to fix.
from cubes.
I'm impressed! That was fast and the code looks great! Thank you for doing that! I noticed a few changes that I liked. For example, you were sane had the coordinates be x, y, and z, and used vectors instead of only using arrays. I hope that the activity of porting it over taught you what it does and why it does it.
There's two things I wanted to point out though:
- The reason getNeighbourIndex(Coord3D point, boolean cubesUsed[][][]) looks like this:
`32 * (cubesUsed[point.a + nudgeBasedOnRotation[0][0]][point.b + nudgeBasedOnRotation[1][0]][point.c + nudgeBasedOnRotation[2][0]] ? 1 : 0)
- 16 * (cubesUsed[point.a + nudgeBasedOnRotation[0][1]][point.b + nudgeBasedOnRotation[1][1]][point.c + nudgeBasedOnRotation[2][1]] ? 1 : 0)...`
is because I was trying to tell the compiler that it should NOT do branching here. I was told that branching is an expensive operation and the getNeighbourIndex() function gets called a lot of times. Maybe you could try to ask Rust to do arithmetic instead of branching there? (I'm not 100% sure if it will make a difference) You motivated me to try making cubesUsed[][][] a multidimensional int array and check if that's faster. EDIT: The experiment didn't work out for me :(
- I'm not quite done with the code yet. I'm currently planning on making something that will allow a program to start from any polycube shape at depth 4 (or some small depth d). That way, I could potentially have multiple programs running at the same time, and search different areas of the search space at the same time. But even if I don't add the depth 4 start code, your code seems to be fast enough to find N=17 in under a month... so we're getting there.
from cubes.
For you point 1., I tried multiple ways of rewriting it, in ways that should avoid branching, but didn't see a diff in performance. After profiling, I didn't see this function as a hot spot.
from cubes.
Good to know. Sorry to bother you about that.
from cubes.
Apparently, there's more discussions in the open cubes repo. I didn't know that until now.
from cubes.
I wasn't aware either, will check it out
from cubes.
Related Issues (20)
- slap jit from numba on it HOT 1
- Suggestion for orientation fixing HOT 5
- Suggestion: for rotation or translation fixed HOT 10
- crop_cube() very expensive HOT 2
- n=12 npy file. HOT 1
- Suggestion to reduce number of run encodings/lookups/rotations needed in many cases while keeping memory use to a minimum HOT 1
- Add permissive license to project HOT 2
- [Discussion] I made a graph that allows me to estimate about how big a cubes_n.npy file will get (in bytes) when given n cubes. HOT 4
- Rust version
- [Discussion] A possible strategy for optimizing search space and symmetries HOT 7
- [Discussion] Traversal as opposed to grid representation HOT 1
- Doesn't run? HOT 1
- Lookup time
- Go Version
- Typo in function 'render_shapes' HOT 1
- Potential Idea For Finding Rotations Quicker HOT 1
- Potential new method for generating unique strings to describe the shapes. HOT 1
- Rotation invariant representation for 2-D shapes HOT 3
- RUST Compile optimisations built on the excellent work of others. Linux & Windows. With a RUST setup guide for Windows
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cubes.