search

mikepound / cubes

This code calculates all the variations of 3D polycubes for any size (time permitting!)
MIT License
163 stars 43 forks source link

Reduce number of polycubes subjected to 24x rotations/hashes/lookups #5

Closed georgedorn closed 1 year ago

georgedorn commented 1 year ago

Only rotate found new polycubes, rather than every candidate, but storing all rotations in the set. Uses slightly less than 24x the memory for the rle map, but this shouldn't matter. Saves about 20-25% of time finding the same results.

mikepound commented 1 year ago

Lovely! I saw this mentioned a few times in the comments, a nice speed up. One issue will be that the size of the map is going to balloon out at around n=13+, it grows by 7x each n+1. Do you think it's worth having a flag that allows you to prioritise memory efficiency vs speed?

In any case, pretty happy to merge this - I won't do it immediately, there's lot of people suggesting stuff and I'd like to back up the original file anyway to give people who watch the video a baseline. I'll mull over a good way to deal with all the various changes - there may not be one! I also have a full time job - oops :D

georgedorn commented 1 year ago

Obviously there's some point at which memory will be a consideration, because infinity and all. I suspect that speed will remain more important than anything else, though, and the fix is to either throw more memory at it, or rework the temporary storage to make use of a pool of memory cache servers (redis or memcache or something).

In other words, I think either your original main branch or my fix alone won't do the job when pushing n closer to the cutting edge.

It's also possible that reducing the polycube hash to a simple string or bitstring could reduce memory consumption; #4 combines well with this PR and adds additional speedups and I think may use less memory than tuples.

mikepound commented 1 year ago

I've now created a new one for these kinds of pull requests:

https://github.com/mikepound/opencubes

This way this one can be fixed to reflect how it was in the video, but many more people can start contributing. I've invited you as a collaborator on it, so you can help managed some of the requests and make changes directly!