Velocity Reviews > faster way to do this?

# faster way to do this?

BartC
Guest
Posts: n/a

 12-04-2011
"lloyd" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

> 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

lloyd
Guest
Posts: n/a

 12-04-2011
On Dec 3, 8:26*pm, "BartC" <(E-Mail Removed)> wrote:
> "lloyd" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
>
>
> > 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.

James Dow Allen
Guest
Posts: n/a

 12-04-2011
On Dec 2, 3:28*am, lloyd <(E-Mail Removed)> 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)

BartC
Guest
Posts: n/a

 12-04-2011
"lloyd" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Dec 3, 8:26 pm, "BartC" <(E-Mail Removed)> 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

lloyd
Guest
Posts: n/a

 12-05-2011
On Dec 4, 6:39 am, "BartC" <(E-Mail Removed)> 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.)

Michael Angelo Ravera
Guest
Posts: n/a

 12-07-2011
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[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.

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.

88888 Dihedral
Guest
Posts: n/a

 12-08-2011
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+= //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
Guest
Posts: n/a

 12-08-2011
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+= //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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Terry Olsen ASP .Net 6 08-01-2005 11:26 PM Matt Stephens Java 0 02-06-2005 09:16 PM Jon Hyland C++ 4 10-04-2004 11:55 PM steve C++ 17 09-13-2004 08:19 PM Carol Haynes Computer Support 9 02-27-2004 08:50 PM