Rotation is a significant factor in runtime #9
Comments
|
I think your onto something with the views, the hard part will be proving that the views are unique, i'm going to run a test with the n=12 data to check. as for an efficient way to compare the views, I think we just need to come up with a quick to compute canonical direction and order for the vectors. polycube1_views -> [4, 1], [1, 1, 1, 2], [1, 0, 1, 0, 1, 0, 1, 1] something which ranks [4, 1] higher than [1, 4] for example. and something that ranks [1, 0, 1, 0, 1, 0, 1, 1] higher than, [4, 1] the problem I foresee is after doing all these checks to get the right order, is it any faster than the rot90? |
|
retracted for wrongness |
|
ah wait i'm dumb, i was packing to bits and changing 2's into 1's |
|
ok so you cannot in fact do a naive re-arrangement of the views based on their properties, the problem you hit is that certain rotations and flips swap 2 axis, the rotation essentially swaps 2 of the views because it is the same shape along different axis. the interesting part is ... that's a mirror!, and we have identified it as the same, the current code doesn't identify mirrors as the same, so is this actually an improvement in behavior ? or a regression ? |
|
some of these are really hard to tell if they are a mirror or not just by looking at them, any idea on how to make proper code to check for mirrors? |
|
I cant seem to get this to work, it does in fact collide more than just mirrors, at least with my naïve approach of sorting the vectors, (picking the largest out of each view and its reverse, and then ordering the views by size). I have pushed my code at |
|
I had opened an issue in cubes and had the idea of using radii to make it rotation independent. Maybe we could look into it. Or a multihash solution. Like not for 28 or so rotations but some specific ones and change all to a uniform structure, like to prefere some axis in the uniform structure. So we need less hashes and still count all shapes. Edit: link to issue |
|
@bertie2 ,
# polycube_1 and polycube_2 are both cropped `np.int8` ndarrays
id_1 = get_canonical_packing(polycube_1, set())
id_2 = get_canonical_packing(polycube_2, set())
id_2_mirror = get_canonical_packing(np.flipud(polycube_2), set())
are_mirrors = id_1 != id_2 and id_1 == id_2_mirror
Whether the mirrors should be counted as separate or not, this can be yet another flag of the main script. To consider mirrors as same, we can e.g. use the |
The collision you have in test.ipynb is actually from a mirror operation! Consider mirroring the polycube along the X/Y plane, where the furthest cube (along our Z, or depth of the image) is our starting point. This is the same polycube but rotated. I think the fundamental issue we will likely run into is that this allows "illegal" rotations, or mirroring, which are actually just 4D rotations, or p(n) as described by Kevin Gong. The same actually happens in 2D, representing the two skew tetrominoes S, Z this way (3D rotation to achieve mirroring). This could be useful for calculating p(n), which tends towards |
|
Just an afterthought, it makes heaps of sense that p(n) and r(n) appear to be linked by just a factor of 2. As n grows, we get more polycubes with chirality, relative to the number of achiral polycubes, and for each chiral polycube we will get exactly 1 other polycube with the inverse chirality. This is a lot easier to think about in 2D, where we will find more polysquares for larger values of n that we can mirror (3D rotate) in such a way that no 2D rotation can achieve the same shape. |
|
@ana-096 ,
for example, if shape is (4,4,4), then there are 64 variables (that can be 0 or 1), but only 3*16=48 equations that constrain them -> for some system of these equations more than 1 solution could be possible. Is this not a problem? I'll try to generate a collision and update this. |
|
@ana-096 , (I think that c++, and "Solution A" are the way to beat the record...) But thinking about more efficient representations of polycubes, do you agree that the total storage requirements cannot theoretically be smaller than described here?: On the other hand, if the point of this new representation is not to never have collisions, but to overcome the problem of wasting too much time on rotations, I agree that it could make sense to implement it: resolving a few collisions could be faster than rotating literally all off the polycubes. To go further with this, need to develop code how to:
|
|
@VladimirFokow your example is for a polycube n=33, did you find any smaller collisions? I did some quick tests for arbitrary shapes 2 < x,y,z < 10 (yes this is taking a long time) and haven't found any smaller collisions yet. Kevin Gong only got to n=16, so if there's no issues for collision, or we account for it, up to n=17, this could help us get further. |
|
@ana-096 results for n=9 and n=10:
|
|
@VladimirFokow are you checking for mirrors? The examples you provided for n=9 I think are mirrors, but it's hard to tell when it's represented as an array.
For a (4,4,4) boolean array, there are 2 ^ 64 values, represented as 2D views, they would each be (4,4) integer arrays, where the value of any given cell is 0 <= x <= 4, hence 5 ^ 16 values. This is approximately 2 ^ 37 values. In general for 2 dimensions, x, y, the number of possible values is 2 ^ (xy), while the 1D views would be (x+1) ^ (y) and (y+1) ^ (x). The number of possible values in the x,y sized boolean array grows faster than the views, however I haven't yet figured out how many of the values can be attributed to mirrors and rotationally symmetric arrays. |
Of course; I wouldn't claim that they are mirrors without checking it😁
I don't see a way to logically derive a formula for this number. For n=9 and n=10 there are really not so many collisions (only 4 and 43). So maybe this method would actually be helpful until n=17 -- if it doesn't grow astronomically fast there, I don't know.
|
From profiling the function
generate_polycubes, for larger values of n the time spent onrot90is a significant factor, with 45 of the 108 second runtime being spent in it for n=9 (see table at bottom of text).So far I've been thinking about a couple of potential solutions, but I haven't reach a point where either solution could be implemented:
Solution A - Writing a purpose-specific
rot90orall_rotationsNumpy appears to use index swapping to achieve 90 degree rotation of an array (definitely faster than a transformation matrix I would imagine), but it has significant overhead as it is written to work for n-dimensional arrays. In the case of polycubes, we know that the array we want to rotate is 3D, and that we want all 28 rotations. Writing a purpose specific version of this function could save on overhead time, but I think it would most likely need to be done in another language.
I haven't really been pursuing this as I don't know any low level or performant languages to try this in, and I think we won't save time with a pure python implementation.
Solution B - Representing the polycube as three 2-D views
This solution appeals to me far more than solution A, as it reduces either our comparisons between hashes, or our memory used on storing hashes (if we store rotations). As we conveniently have a boolean array aligned with the axes, I think we can represent any polycube with three, fast to calculate, 2-D views of the polycube:
For the simple L shaped (cropped) polycube with a length of 4 and 1 cube off the a side, the views would be represented this way:
[4, 1], [1, 1, 1, 2], [1, 0, 1, 0, 1, 0, 1, 1]We can avoid worrying about the order in which these appear by using collections.Counter or generally by treating it as an unsorted list. We could then compare the view to a rotated version of the polycube by ensuring that all entries match only once, hence finding that both polycubes are identical...
Unfortunately, though this works for comparing the two 1-D views of a polysquare with some additional checks, I haven't found a way to ensure these views match for polycubes after any of the 28 arbitrary rotations:
We can see from this that some rotations will give us outputs that are very hard to compare to the original polycube for equality.
Perhaps a solution to this is to rebuild the arbitrary polycube in a specific manner to always give the same output? I don't have a solution for this yet.
Profiling
cumtimeis the value we're worried about forrot90in this case, as looking at the source code for this function, it calls a number of other functions to achieve rotation by 90 degrees, withflipbeing the main point of concern.With optimisations from the PRs on the original repo (bertie2, georgedorn, and mine), the cProfile.run output looks like this for n=9:
The text was updated successfully, but these errors were encountered: