faster way to do this?

Discussion in 'C Programming' started by lloyd, Dec 1, 2011.

1. lloydGuest

So I have a little program that enumerates rectangular arrays of small
integers with a particular property. Each rotation and reflection of a
solution is valid, but when you rotate/reflect, the entries in each
cell of the array are transformed too. I want to enumerate the reduced
count of solutions that have been rotated and reflected into a canonic
form, but I also want to enumerate the larger number of solutions that
include all rotations and reflections as separate. My generating
program will reach all possibilities eventually.

Here's how I do it: I precompute the effect that each of the 8
transformations (combinations of rotation and reflection) will have on
any possible entry (currently there are only 8 possible entries). I
store these in a two-dimensional array T[8][8] where the first index
identifies which transformation we're dealing with and the second is
the "input". For each unreduced array solution that I generate and
hold in the array g[][], I see if I can put it in a lexicographically
lower form by transforming it by each of the transformations; I of
course skip the identity, and I only use the first three
transformations (no 90-degree rotations or reflections across
diagonals) if my array isn't square. As soon as I find a
transformation that is lower, I bail out, because the canonic form is
the lowest lexicographically. If the solution being tested is lower
than (or equal to) all possible transformations, I'm interested in its
degree of symmetry, which I calculate here as dsym (I don't care about
dsym if the solution being tested is in non-canonic form). My
rectangle is given by #DEFINED values B (breadth) and H (height). The
code for this function, which returns NO if we're not in canonic form
and YES if we are, plus it calculates the global variable dsym, is as
follows, and I wonder if anyone sees any significant speed
improvements I could make. Is it possible to do the same without going
through this loop 7 times?? Maybe using seven different flags? Thank
you!

int best_symmetry()
{
int i,j,flag;
dsym=1;
flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[1][g[H-1-i][j]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[2][g[B-1-j]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[3][g[H-1-i][B-1-j]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

if (H != B) /* stop here if we're not on a square
grid */
return YES;

flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[4][g[j]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[5][g[H-1-j]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[6][g[j][H-1-i]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

flag=0;
for (i=0;i<H;i++) {
for (j=0;j<B;j++) {
flag=g[j]-T[7][g[H-1-j][H-1-i]];
if (flag)
break;
} if (flag)
break;
} if (flag>0)
return NO;
if (flag==0)
dsym++;

return YES;
}

lloyd, Dec 1, 2011

2. 88888 DihedralGuest

On Friday, December 2, 2011 4:28:13 AM UTC+8, lloyd wrote:
> So I have a little program that enumerates rectangular arrays of small
> integers with a particular property. Each rotation and reflection of a
> solution is valid, but when you rotate/reflect, the entries in each
> cell of the array are transformed too. I want to enumerate the reduced
> count of solutions that have been rotated and reflected into a canonic
> form, but I also want to enumerate the larger number of solutions that
> include all rotations and reflections as separate. My generating
> program will reach all possibilities eventually.
>
> Here's how I do it: I precompute the effect that each of the 8
> transformations (combinations of rotation and reflection) will have on
> any possible entry (currently there are only 8 possible entries). I
> store these in a two-dimensional array T[8][8] where the first index
> identifies which transformation we're dealing with and the second is
> the "input".

There are only 64 entries and most of your transforms can be done by an reordering stored performed in one line in c

for (i=0;i<64;i++) tout64=tin64[torder];

Figure out torder for i=0 to 63 by constants or some formula to set correct
values first and I assume you have to apply the 8X8 transforms many times for
your image. Of course you have to input the 8x8 pixels first and write back
to the image at the right portion which is trivial in C.

In the worst case one has to write down the 64 point transform one by one to save the loop overhead to meet the processing speed requirement.

Double looping is expensive for every 8X8 block.

88888 Dihedral, Dec 1, 2011

3. Eric SosmanGuest

On 12/1/2011 3:28 PM, lloyd wrote:
> So I have a little program that enumerates rectangular arrays of small
> integers with a particular property. Each rotation and reflection of a
> solution is valid, but when you rotate/reflect, the entries in each
> cell of the array are transformed too. I want to enumerate the reduced
> count of solutions that have been rotated and reflected into a canonic
> form, but I also want to enumerate the larger number of solutions that
> include all rotations and reflections as separate. My generating
> program will reach all possibilities eventually.
>
> Here's how I do it: I precompute the effect that each of the 8
> transformations (combinations of rotation and reflection) will have on
> any possible entry (currently there are only 8 possible entries). I
> store these in a two-dimensional array T[8][8] where the first index
> identifies which transformation we're dealing with and the second is
> the "input". For each unreduced array solution that I generate and
> hold in the array g[][], I see if I can put it in a lexicographically
> lower form by transforming it by each of the transformations; I of
> course skip the identity, and I only use the first three
> transformations (no 90-degree rotations or reflections across
> diagonals) if my array isn't square. As soon as I find a
> transformation that is lower, I bail out, because the canonic form is
> the lowest lexicographically. If the solution being tested is lower
> than (or equal to) all possible transformations, I'm interested in its
> degree of symmetry, which I calculate here as dsym (I don't care about
> dsym if the solution being tested is in non-canonic form). My
> rectangle is given by #DEFINED values B (breadth) and H (height). The
> code for this function, which returns NO if we're not in canonic form
> and YES if we are, plus it calculates the global variable dsym, is as
> follows, and I wonder if anyone sees any significant speed
> improvements I could make. Is it possible to do the same without going
> through this loop 7 times?? Maybe using seven different flags? Thank
> you!
>[... code snipped; see up-thread ...]

It seems to me you could filter out a lot of non-canonical
arrangements just by considering the values at the corners. You
don't say what lexicographic ordering you use, but let's suppose
the top left corner is the most significant slot: if it's not the
minimum of the four corners, then the arrangement is not canonical
(because the corner that *is* the minimum can be brought to the top
left by one or two reflections). If the top left is the minimum and
the rectangle is square, you can go on to compare the top right to
the bottom left (because they can be interchanged by one diagonal
reflection).

You don't mention whether the values in the rectangles are unique;
if they are, there may be further simple elimination tests. But even
without such, a couple of simple comparisons up front will eliminate
three-quarters of the non-canonical candidates (seven-eighths for
squares), giving you an immediate fourfold (eightfold) speedup,
approximately.

--
Eric Sosman
d

Eric Sosman, Dec 2, 2011
4. lloydGuest

On Dec 1, 5:16 pm, 88888 Dihedral <>
wrote:
> On Friday, December 2, 2011 4:28:13 AM UTC+8, lloyd wrote:
> > So I have a little program that enumerates rectangular arrays of small
> > integers with a particular property. Each rotation and reflection of a
> > solution is valid, but when you rotate/reflect, the entries in each
> > cell of the array are transformed too. I want to enumerate the reduced
> > count of solutions that have been rotated and reflected into a canonic
> > form, but I also want to enumerate the larger number of solutions that
> > include all rotations and reflections as separate. My generating
> > program will reach all possibilities eventually.

>
> > Here's how I do it: I precompute the effect that each of the 8
> > transformations (combinations of rotation and reflection) will have on
> > any possible entry (currently there are only 8 possible entries). I
> > store these in a two-dimensional array T[8][8] where the first index
> > identifies which transformation we're dealing with and the second is
> > the "input".

>
> There are only 64 entries and most of your transforms can be done by an reordering stored performed in one line in c
>
> for (i=0;i<64;i++) tout64=tin64[torder];
>
> Figure out torder for i=0 to 63 by constants or some formula to set correct
> values  first and I assume you have to apply the 8X8 transforms many times for
> your image. Of course you have to input the 8x8 pixels first and write back
> to the image at the right portion which is trivial in C.
>
> In the worst case one has to  write down the 64 point transform one by one to save the loop overhead to meet the processing speed requirement.
>
> Double looping is expensive for every 8X8 block.

This doesn't make any sense. It seems like you read too quickly and
didn't understand. First, your suggestion would be just as costly in
terms of time, as the extra multiplication required to fetch something
from a 2D array instead of a 1D array costs the same as the
multiplication I'd need to make to find the input parameter each time
I called your 1D version. Second, I'd still have to go through my i,j
loop 7 times.

To recap, I have a B-by-H array. Each entry in the array is a small
integer (representing a puzzle piece, if that helps). If I rotate and/
or reflect the array, the puzzle pieces need to be transformed
individually, so as well as changing place in the array they change
their label number. For example, piece #2, when turned upside down,
will become piece #3.

lloyd, Dec 2, 2011
5. lloydGuest

On Dec 1, 8:46 pm, Eric Sosman <> wrote:
> On 12/1/2011 3:28 PM, lloyd wrote:
>
>
>
> > So I have a little program that enumerates rectangular arrays of small
> > integers with a particular property. Each rotation and reflection of a
> > solution is valid, but when you rotate/reflect, the entries in each
> > cell of the array are transformed too. I want to enumerate the reduced
> > count of solutions that have been rotated and reflected into a canonic
> > form, but I also want to enumerate the larger number of solutions that
> > include all rotations and reflections as separate. My generating
> > program will reach all possibilities eventually.

>
> > Here's how I do it: I precompute the effect that each of the 8
> > transformations (combinations of rotation and reflection) will have on
> > any possible entry (currently there are only 8 possible entries). I
> > store these in a two-dimensional array T[8][8] where the first index
> > identifies which transformation we're dealing with and the second is
> > the "input". For each unreduced array solution that I generate and
> > hold in the array g[][], I see if I can put it in a lexicographically
> > lower form by transforming it by each of the transformations; I of
> > course skip the identity, and I only use the first three
> > transformations (no 90-degree rotations or reflections across
> > diagonals) if my array isn't square. As soon as I find a
> > transformation that is lower, I bail out, because the canonic form is
> > the lowest lexicographically. If the solution being tested is lower
> > than (or equal to) all possible transformations, I'm interested in its
> > degree of symmetry, which I calculate here as dsym (I don't care about
> > dsym if the solution being tested is in non-canonic form). My
> > rectangle is given by #DEFINED values B (breadth) and H (height). The
> > code for this function, which returns NO if we're not in canonic form
> > and YES if we are, plus it calculates the global variable dsym, is as
> > follows, and I wonder if anyone sees any significant speed
> > improvements I could make. Is it possible to do the same without going
> > through this loop 7 times?? Maybe using seven different flags? Thank
> > you!
> >[... code snipped; see up-thread ...]

>
>      It seems to me you could filter out a lot of non-canonical
> arrangements just by considering the values at the corners.

But that's just what I do in those loops--the first step of each loop
looks at the corresponding corner, and if it is "better" when it
undergoes the appropriate transform, I return the answer NO and drop
out. I still have to generate the entire array before testing for
canonicity, because as I said I also need to find out the number of
non-canonic arrangements. (An alternative way, which strikes me as
probably slower, would be to do a bunch of testing while generating
and weed out non-canonical ones, and for each canonical one I find,
putting it through all the transformations to discover its degree of
symmetry and hence how many different versions of it there are.)

And something else, which I don't blame you for because I didn't spell
it out, is that there's only one possibility for each corner piece, so
the first potentially different piece is the one *next* to the corner
(which means seven tests up front not just three). Actually that could
save me a tiny amount of time, by not bothering to test the corners
themselves and starting all my i and j loops with 1 instead of 0. But
it's not the big speed-up I'm looking for, which is doing all 7 double-
loops at once.

Thanks though. Any other suggestions? --Lloyd

> You
> don't say what lexicographic ordering you use, but let's suppose
> the top left corner is the most significant slot: if it's not the
> minimum of the four corners, then the arrangement is not canonical
> (because the corner that *is* the minimum can be brought to the top
> left by one or two reflections).  If the top left is the minimum and
> the rectangle is square, you can go on to compare the top right to
> the bottom left (because they can be interchanged by one diagonal
> reflection).
>
>      You don't mention whether the values in the rectangles are unique;
> if they are, there may be further simple elimination tests.  But even
> without such, a couple of simple comparisons up front will eliminate
> three-quarters of the non-canonical candidates (seven-eighths for
> squares), giving you an immediate fourfold (eightfold) speedup,
> approximately.
>
> --
> Eric Sosman
>

lloyd, Dec 2, 2011
6. BartCGuest

"lloyd" <> wrote in message
news:...
> So I have a little program that enumerates rectangular arrays of small
> integers with a particular property. Each rotation and reflection of a
> solution is valid, but when you rotate/reflect, the entries in each
> cell of the array are transformed too. I want to enumerate the reduced
> count of solutions that have been rotated and reflected into a canonic
> form, but I also want to enumerate the larger number of solutions that
> include all rotations and reflections as separate. My generating
> program will reach all possibilities eventually.

Difficult to see exactly what you are trying to achieve. So you have a
rectangular array of small integers, for example:

10 20 30
40 50 60

And with mirroring and flipping you have 3 more:

30 20 10
60 50 40

40 50 60
30 20 10

60 50 40
30 20 10

And with 90-degree rotation of the original, you have this:

40 10
50 20
60 30

And by mirroring and flipping of that you have 3 more, total 8 arrangements
(the same number of ways you could put a 5.25" floppy into a drive, of which
only one was correct...)

(And I understand that if the array is not square, you don't bother with
rotations, as presumably they can't be solutions.)

So assuming the above is correct, you have these 4 or 8 matrices, what are
you trying to achieve again?

--
Bartc

BartC, Dec 2, 2011
7. Eric SosmanGuest

On 12/2/2011 2:48 PM, lloyd wrote:
>[...]
> Thanks though. Any other suggestions? --Lloyd

No. I lack the patience to iterate and reiterate while somebody
dribbles details drop by drop. If you feel like posting a usable
description of your problem, I might be tempted to think about it.
Or not; one never knows.

--
Eric Sosman
d

Eric Sosman, Dec 3, 2011
8. lloydGuest

On Dec 2, 8:22 pm, Eric Sosman <> wrote:
> On 12/2/2011 2:48 PM, lloyd wrote:
>
> >[...]
> > Thanks though. Any other suggestions?  --Lloyd

>
>      No.  I lack the patience to iterate and reiterate while somebody
> dribbles details drop by drop.  If you feel like posting a usable
> description of your problem, I might be tempted to think about it.
> Or not; one never knows.
>
> --
> Eric Sosman
>

Ooh, snark. The details that I left out made no difference, which is
why I left them out. The solution I posted did exactly what you
suggested anyway, checking each corner first. I added in my follow-up
the (in my opinion irrelevant) extra detail that even if I *hadn't*
already done it that way, it wouldn't be as efficient as you thought,
because I'd have to check the squares next to the corners.

That's ok, I don't *expect* you to help, or to wade through a problem
that is too much of a pain in the neck or that lies outside your
experience. I just thought someone here might have come across it
before and knew of a technique that would work. The same problem has
cropped up with me before and I've never found a good answer.

lloyd, Dec 3, 2011
9. lloydGuest

On Dec 2, 4:07 pm, "BartC" <> wrote:
> "lloyd" <> wrote in message
>
> news:...
>
> > So I have a little program that enumerates rectangular arrays of small
> > integers with a particular property. Each rotation and reflection of a
> > solution is valid, but when you rotate/reflect, the entries in each
> > cell of the array are transformed too. I want to enumerate the reduced
> > count of solutions that have been rotated and reflected into a canonic
> > form, but I also want to enumerate the larger number of solutions that
> > include all rotations and reflections as separate. My generating
> > program will reach all possibilities eventually.

>
> Difficult to see exactly what you are trying to achieve. So you have a
> rectangular array of small integers, for example:
>
> 10 20 30
> 40 50 60
>
> And with mirroring and flipping you have 3 more:
>
> 30 20 10
> 60 50 40
>
> 40 50 60
> 30 20 10
>
> 60 50 40
> 30 20 10
>
> And with 90-degree rotation of the original, you have this:
>
> 40 10
> 50 20
> 60 30
>
> And by mirroring and flipping of that you have 3 more, total 8 arrangements
> (the same number of ways you could put a 5.25" floppy into a drive, of which
> only one was correct...)
>
> (And I understand that if the array is not square, you don't bother with
> rotations, as presumably they can't be solutions.)
>
> So assuming the above is correct, you have these 4 or 8 matrices, what are
> you trying to achieve again?

Hi Bart, say this is a valid array (I won't bother explaining what my
problem means by "valid"):

3 6 1
5 4 9

Then automatically the reflections and rotations of this array are
also valid. They are:

1 6 3
9 4 5

5 4 9
3 6 1

9 4 5
1 6 3

My program, as it performs a back-tracking search for these and other
similar valid solutions, will encounter each of these as it goes, and
first verify that the array is valid. Then it calls best_symmetry() to
determine whether the valid array it has encountered is in canonical
form or not. For my purposes I use the lexicographically "lowest",
when the array is read by rows and flattened. So as my program goes
through all potential solutions, it examines the four above when it
validates them, and inquires of best_symmetry() whether or not the
array is in canonical form. It receives an answer of "no" for the 1st,
3rd and 4th arrays above, and "yes" for the 2nd array above. The code
I submitted was my attempt at an efficient check of canonicity. I bail
out as soon as I notice that another array would be lower, which in
this case would happen when I checked the top right-hand corner of the
horizontal reflection.

If the array had been square, I would need to perform another four
transformations to see whether I had the best form.

An additional complication that I needn't have mentioned, but did in
my first version, is that every integer entry, in an array when it is
reflected or rotated, is itself transformed. The array T[][] holds
these transformations, and it looks like this:

const int T[8][9] = {{0, 1,2,3,4, 5,6, 7,8},
{0, 4,3,2,1, 5,6, 8,7},
{0, 2,1,4,3, 5,6, 8,7},
{0, 3,4,1,2, 5,6, 7,8},
{0, 1,4,3,2, 6,5, 7,8},
{0, 2,3,4,1, 6,5, 8,7},
{0, 4,1,2,3, 6,5, 8,7},
{0, 3,2,1,4, 6,5, 7,8}};

That's why I need to send array entries through the T[][] transform
while I am testing each transformation.

Thanks,
Lloyd

lloyd, Dec 3, 2011
10. BartCGuest

"lloyd" <> wrote in message
news:...
> On Dec 2, 8:22 pm, Eric Sosman <> wrote:

>> No. I lack the patience to iterate and reiterate while somebody
>> dribbles details drop by drop. If you feel like posting a usable

> experience. I just thought someone here might have come across it
> before and knew of a technique that would work. The same problem has
> cropped up with me before and I've never found a good answer.

Perhaps try comp.graphics.algorithms.

--
Bartc

BartC, Dec 3, 2011
11. BartCGuest

"lloyd" <> wrote in message
news:...

> Hi Bart, say this is a valid array (I won't bother explaining what my
> problem means by "valid"):
>
> 3 6 1
> 5 4 9
>
> Then automatically the reflections and rotations of this array are
> also valid. They are:
>
> 1 6 3
> 9 4 5
>
> 5 4 9
> 3 6 1
>
> 9 4 5
> 1 6 3
>
> My program, as it performs a back-tracking search for these and other
> similar valid solutions, will encounter each of these as it goes, and
> first verify that the array is valid. Then it calls best_symmetry() to
> determine whether the valid array it has encountered is in canonical
> form or not. For my purposes I use the lexicographically "lowest",
> when the array is read by rows and flattened.

I doubt I'm going to offer any helpful advice, just trying to clarify the
problem further.

So, you have a process that generates arrays like the above, but not
necessarily grouped together like that (so these solutions could be
interspersed with others).

With each solution you check to see if this is in 'canonical' form
(normalised?) so that those can be marked or counted.

You have a function best_symmetry() which does this (by executing a
complicated-looking B*H loop up to 7 times), which is what you want to
optimise.

You check for canonicity by generating, for each solution, the up to 7 other
arrangements, and doing an element-by-element compare. (Although those other
7 arrangements will come up as solutions in their turn, or already have
done, and are themselves compared to 7 transformed versions each time).

Might be worth looking at the bigger picture; how big are B and H likely to
be? How big are the numbers in the arrays? And how many different arrays
might there be? More importantly, how big an overhead is this checking
function?

--
Bartc

BartC, Dec 4, 2011
12. lloydGuest

On Dec 3, 8:26 pm, "BartC" <> wrote:
> "lloyd" <> wrote in message
>
> news:...
>
>
>
> > Hi Bart, say this is a valid array (I won't bother explaining what my
> > problem means by "valid"):

>
> > 3 6 1
> > 5 4 9

>
> > Then automatically the reflections and rotations of this array are
> > also valid. They are:

>
> > 1 6 3
> > 9 4 5

>
> > 5 4 9
> > 3 6 1

>
> > 9 4 5
> > 1 6 3

>
> > My program, as it performs a back-tracking search for these and other
> > similar valid solutions, will encounter each of these as it goes, and
> > first verify that the array is valid. Then it calls best_symmetry() to
> > determine whether the valid array it has encountered is in canonical
> > form or not. For my purposes I use the lexicographically "lowest",
> > when the array is read by rows and flattened.

>
> I doubt I'm going to offer any helpful advice, just trying to clarify the
> problem further.
>
> So, you have  a process that generates arrays like the above, but not
> necessarily grouped together like that (so these solutions could be
> interspersed with others).
>
> With each solution you check to see if this is in 'canonical' form
> (normalised?) so that those can be marked or counted.
>
> You have a function best_symmetry() which does this (by executing a
> complicated-looking B*H loop up to 7 times), which is what you want to
> optimise.
>
> You check for canonicity by generating, for each solution, the up to 7 other
> arrangements, and doing an element-by-element compare. (Although those other
> 7 arrangements will come up as solutions in their turn, or already have
> done, and are themselves compared to 7 transformed versions each time).
>
> Might be worth looking at the bigger picture; how big are B and H likely to
> be? How big are the numbers in the arrays? And how many different arrays
> might there be? More importantly, how big an overhead is this checking
> function?
>
> --
> Bartc

Yes Bart, you've got it - but I usually don't actually have to
completely generate the other 7 solutions - I just start checking the
array against what the transformed version would be, and at the first
difference I stop. If at the point of difference the transformed one
was better then I bail out completely (I don't actually have to find
the canonical form), and if the original version is lower, then I
start checking it against the next of the 7 reflections/rotations.
Where I'm at currently, which is counting valid 8 X 8 arrays, there
are going to be probably around a trillion solutions. There were 55
million valid 7 x 7 arrays (before reducing for normalised forms), and
it took my program about 20 minutes to complete its run. So I'm
probably p!\$\$!ng in the wind by hoping to get to 8 X 8, but there's no
harm in making the thing run as efficiently as possible before giving
up, and I'm sure I can at least get to the point where I can squeeze
out the 8 X 7 solutions.

lloyd, Dec 4, 2011
13. James Dow AllenGuest

On Dec 2, 3:28 am, lloyd <> wrote:
> So I have a little program that enumerates rectangular arrays of small
> integers with a particular property. Each rotation and reflection of a
> solution is valid, but when you rotate/reflect, the entries in each
> cell of the array are transformed too.

Little or no advice to offer. I just wanted to chirp in and
say I've been faced with the same problem many times over
the years. Like you, I've wondered if there was a smarter
faster way....

How small are your "small integers"? If you can pack several
into a word, that *might* lead to a slight speedup.
In that case you might want to build, redundantly, *two* forms
of your array, one with row/column transposed.

I posted a question similar to yours a year ago:

In that case, my small integers were very small (1 bit!),
but rather than just reversals, all permutations were equivalent.
I did find a heuristic for that case. It detects only *most*
equivalences, not *all*, but sometimes that's good enough

James Dow Allen (jamesdowallen at gmail)

James Dow Allen, Dec 4, 2011
14. BartCGuest

"lloyd" <> wrote in message
news:...
> On Dec 3, 8:26 pm, "BartC" <> wrote:

>> Might be worth looking at the bigger picture; how big are B and H likely
>> to
>> be? How big are the numbers in the arrays? And how many different arrays
>> might there be? More importantly, how big an overhead is this checking
>> function?

> Yes Bart, you've got it - but I usually don't actually have to
> completely generate the other 7 solutions - I just start checking the
> array against what the transformed version would be, and at the first
> difference I stop. If at the point of difference the transformed one
> was better then I bail out completely (I don't actually have to find
> the canonical form), and if the original version is lower, then I
> start checking it against the next of the 7 reflections/rotations.
> Where I'm at currently, which is counting valid 8 X 8 arrays, there
> are going to be probably around a trillion solutions. There were 55
> million valid 7 x 7 arrays (before reducing for normalised forms), and
> it took my program about 20 minutes to complete its run. So I'm
> probably p!\$\$!ng in the wind by hoping to get to 8 X 8, but there's no
> harm in making the thing run as efficiently as possible before giving
> up, and I'm sure I can at least get to the point where I can squeeze
> out the 8 X 7 solutions.

20 minutes for 55 million, makes 250 days for a trillion, plus extra because
presumably 8x8 each take longer than 7x7, so the best part of a year.

This is where the overheads of best_symmetry() become important. If you
can't profile it, perhaps just call it twice each time, and find out what
happens to that twenty minutes. But even if that that function accounts for
99% of runtime, and you can eliminate it completely, you might still looking
at a runtime of several days.

With that much data, you can't really generate all of it first then sort it
or something (although that means all canonical forms will occur first, I'm
not sure it would help unless you can identify each subsequent version as

The arrays themselves seem small, so they could be perhaps be represented as
strings of up to 64 characters, or perhaps 32-bytes if they can be packed,
then you can use standard string compares. But you still have the headache
of transforming the string.

But before going any further, what *is* the overhead of calling
best_symmetry?

--
Bartc

BartC, Dec 4, 2011
15. lloydGuest

On Dec 4, 6:39 am, "BartC" <> wrote:

> But before going any further, what *is* the overhead of calling
> best_symmetry?

Well, you're very sensible, I should have checked that from the start.
And it turns out it's almost negligable. I can see why now: it almost
always has to attempt only a few comparisons before finding a
transformation that's better, or once out of 8 times it needs
marginally more than 7 or 8 comparisons before confirming that it's
already in best canonical form. Only in the situations where a
solution has a high degree of symmetry does it ever need to go through
all seven doubly-nested loops till the bitter end, and as the
dimensions of the array get bigger and bigger the symmetrical
solutions are more and more rare. So any savings will have to come
somewhere in the recursive generation procedure I use.

I'll tinker with it some more, strip it down to its essentials and
repost if it seems there could be a speed-up remaining that I can't
locate.

Thanks for helping me to figure this out. (Thanks also to James Dow
Allen for your post, I was sure someone else would have encountered
the same general problem in the past.)

lloyd, Dec 5, 2011
16. Michael Angelo RaveraGuest

On Thursday, December 1, 2011 2:16:32 PM UTC-8, 88888 Dihedral wrote:
> On Friday, December 2, 2011 4:28:13 AM UTC+8, lloyd wrote:
> > So I have a little program that enumerates rectangular arrays of small
> > integers with a particular property. Each rotation and reflection of a
> > solution is valid, but when you rotate/reflect, the entries in each
> > cell of the array are transformed too. I want to enumerate the reduced
> > count of solutions that have been rotated and reflected into a canonic
> > form, but I also want to enumerate the larger number of solutions that
> > include all rotations and reflections as separate. My generating
> > program will reach all possibilities eventually.
> >
> > Here's how I do it: I precompute the effect that each of the 8
> > transformations (combinations of rotation and reflection) will have on
> > any possible entry (currently there are only 8 possible entries). I
> > store these in a two-dimensional array T[8][8] where the first index
> > identifies which transformation we're dealing with and the second is
> > the "input".

>
> There are only 64 entries and most of your transforms can be done by an reordering stored performed in one line in c
>
> for (i=0;i<64;i++) tout64=tin64[torder];
>
> Figure out torder for i=0 to 63 by constants or some formula to set correct
> values first and I assume you have to apply the 8X8 transforms many times for
> your image. Of course you have to input the 8x8 pixels first and write back
> to the image at the right portion which is trivial in C.
>
> In the worst case one has to write down the 64 point transform one by one to save the loop overhead to meet the processing speed requirement.
>
> Double looping is expensive for every 8X8 block.

Mich's first law of solutions:
If there is a cannonical form, solve only the cannonical form. (and transform all inputs into cannonical form and generate all outputs that aren't in cannonical form).

If you can precompute the effect, you can also precompute the resultant values, if the integers are small enough. How many resultant values do you need? If you have only, say 256 * 256 possible resultant values, you only needto precompute those once (and that will only take a trice). If you have table lookups where each dimension is a power of 2, you can use bit shifts rather than multiplies (which will get done behind the scenes in a multi-dimensional array anyway) and look up the answers in a one-dimensional array.

The next speed up is in improving your evaluator.

Michael Angelo Ravera, Dec 7, 2011
17. 88888 DihedralGuest

I'll give some example in C code to check the symmetric patterns in an 8x8=64
unsigned char *

// unsigned char * subimg that stores 64 bytes
// unsigned char * ptr local pointer
// int hsym_flag marker

for(ptr=subimg, hsym_flag=1, j=0;j<8;j++, ptr+=8) //for each row in j
if ((ptr[0]^ptr[7]) || (ptr[1]^sub[6])||(ptr[2]^ptr[5])||(ptr[3]^ptr[4]))
{ hsym_flag=0; break;}

//

88888 Dihedral, Dec 8, 2011
18. 88888 DihedralGuest

On Thursday, December 8, 2011 1:54:55 PM UTC+8, 88888 Dihedral wrote:
> I'll give some example in C code to check the symmetric patterns in an 8x8=64
> unsigned char *
>
> // unsigned char * subimg that stores 64 bytes
> // unsigned char * ptr local pointer
> // int hsym_flag marker
>
> for(ptr=subimg, hsym_flag=1, j=0;j<8;j++, ptr+=8) //for each row in j
> if ((ptr[0]^ptr[7]) || (ptr[1]^sub[6])||(ptr[2]^ptr[5])||(ptr[3]^ptr[4]))
> { hsym_flag=0; break;}
>
> //

I could use a pointer that points to 32 bits here!
This one is really illustrative.

88888 Dihedral, Dec 8, 2011