Velocity Reviews > faster way to do this?

# faster way to do this?

lloyd
Guest
Posts: n/a

 12-01-2011
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[i][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[i][j]-T[2][g[i][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[i][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[i][j]-T[4][g[j][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[i][j]-T[5][g[H-1-j][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[i][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[i][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;
}

88888 Dihedral
Guest
Posts: n/a

 12-01-2011
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[i]=tin64[torder[i]];

Figure out torder[i] 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.

Eric Sosman
Guest
Posts: n/a

 12-02-2011
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

lloyd
Guest
Posts: n/a

 12-02-2011
On Dec 1, 5:16*pm, 88888 Dihedral <dihedral88...@googlemail.com>
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[i]=tin64[torder[i]];
>
> Figure out torder[i] 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
Guest
Posts: n/a

 12-02-2011
On Dec 1, 8:46*pm, Eric Sosman <esos...@ieee-dot-org.invalid> 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
> esos...@ieee-dot-org.invalid

BartC
Guest
Posts: n/a

 12-02-2011

"lloyd" <> wrote in message
news:89b6e614-0a63-4dca-84ce-...
> 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

Eric Sosman
Guest
Posts: n/a

 12-03-2011
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

lloyd
Guest
Posts: n/a

 12-03-2011
On Dec 2, 8:22*pm, Eric Sosman <esos...@ieee-dot-org.invalid> 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
> esos...@ieee-dot-org.invalid

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
Guest
Posts: n/a

 12-03-2011
On Dec 2, 4:07*pm, "BartC" <b...@freeuk.com> wrote:
> "lloyd" <lloyd.hough...@gmail.com> wrote in message
>
> news:89b6e614-0a63-4dca-84ce-...
>
> > 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

BartC
Guest
Posts: n/a

 12-03-2011
"lloyd" <> wrote in message
news:affe862d-1ae6-4a34-bcaa-...
> On Dec 2, 8:22 pm, Eric Sosman <esos...@ieee-dot-org.invalid> 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