faster way to do this?

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

  1. lloyd

    lloyd Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. lloyd

    Eric Sosman Guest

    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
    #3
  4. lloyd

    lloyd Guest

    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
    #4
  5. lloyd

    lloyd Guest

    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
    #5
  6. lloyd

    BartC Guest

    "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
    #6
  7. lloyd

    Eric Sosman Guest

    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
    #7
  8. lloyd

    lloyd Guest

    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
    #8
  9. lloyd

    lloyd Guest

    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
    #9
  10. lloyd

    BartC Guest

    "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
    #10
  11. lloyd

    BartC Guest

    "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
    #11
  12. lloyd

    lloyd Guest

    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
    #12
  13. 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:

    http://groups.google.com/group/alt...._frm/thread/e1ee2d2e4fd6c6f7/2a24e266b1d8fb54

    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
    #13
  14. lloyd

    BartC Guest

    "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
    being already done).

    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
    #14
  15. lloyd

    lloyd Guest

    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
    #15
  16. 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
    #16
  17. 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
    #17
  18. 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
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Terry Olsen

    Any way to make pages faster?

    Terry Olsen, Aug 1, 2005, in forum: ASP .Net
    Replies:
    6
    Views:
    364
    clintonG
    Aug 2, 2005
  2. Matt Stephens

    XSLT is way faster using Java 5

    Matt Stephens, Feb 6, 2005, in forum: Java
    Replies:
    0
    Views:
    404
    Matt Stephens
    Feb 6, 2005
  3. steve
    Replies:
    17
    Views:
    681
    Mike Smith
    Sep 13, 2004
  4. Jon Hyland
    Replies:
    4
    Views:
    6,071
    Jon Hyland
    Oct 5, 2004
  5. Eamonn Sullivan

    A faster way of finding historical highs/lows

    Eamonn Sullivan, Jun 11, 2004, in forum: Python
    Replies:
    6
    Views:
    353
    Peter Hansen
    Jun 14, 2004
Loading...

Share This Page