[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] arend_1_24.5: dfa 1D conversion
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] arend_1_24.5: dfa 1D conversion |
|
Date: |
Sat, 2 Feb 2002 19:25:32 +0100 (CET) |
- internal dfa structure rewritten 1D
I did a little 1D conversion as well, hope it does not overlap what Inge
started to do. This small patch saves about 3.7% time for the nngs test
suite (according to gprof output), by eliminating the function read_board.
Arend
Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.20
diff -u -r1.20 matchpat.c
--- engine/matchpat.c 31 Jan 2002 08:29:17 -0000 1.20
+++ engine/matchpat.c 2 Feb 2002 18:20:03 -0000
@@ -637,13 +637,12 @@
/* data */
extern int board_size;
static int dfa_board_size = -1;
-extern int dfa_p[DFA_MAX_BOARD * 4][DFA_MAX_BOARD * 4];
-extern order_t spiral[8][MAX_ORDER];
+extern int dfa_p[DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4];
+extern int spiral[8][MAX_ORDER];
const int convert[3][4];
/* Forward declarations. */
static void dfa_prepare_for_match(int color);
-static int read_board(int ll, int m, int n, int row);
static int scan_for_patterns(dfa_t *pdfa, int l, int m, int n,
int *pat_list);
#if DFA_SORT
@@ -716,49 +715,24 @@
dfa_prepare_for_match(int color)
{
int i, j;
+ int ii;
if (dfa_board_size != board_size) {
dfa_board_size = board_size;
/* clean up the board */
- for (i = 0; i != DFA_MAX_BOARD * 4; i++)
- for (j = 0; j != DFA_MAX_BOARD * 4; j++)
- dfa_p[i][j] = OUT_BOARD;
+ for (ii = 0; ii < 4 * DFA_MAX_BOARD * 4 * DFA_MAX_BOARD; ii++)
+ dfa_p[ii] = OUT_BOARD;
}
/* copy the board */
- for (i = 0; i != dfa_board_size; i++)
- for (j = 0; j != dfa_board_size; j++)
- dfa_p[DFA_MAX_BOARD+i][DFA_MAX_BOARD+j] =
+ for (i = 0; i < dfa_board_size; i++)
+ for (j = 0; j < dfa_board_size; j++)
+ dfa_p[DFA_POS(i, j) + DFA_OFFSET] =
EXPECTED_COLOR(color, p[i][j]);
prepare_for_match(color);
}
-
-/*
- * A function to read the board's values folowing order
- * spiral[ll] from anchor (m, n).
- *
- */
-static int
-read_board(int ll, int m, int n, int row)
-{
- int i2, j2;
-
- i2 = DFA_MAX_BOARD + m + spiral[ll][row].i;
- j2 = DFA_MAX_BOARD + n + spiral[ll][row].j;
-
-#ifdef DFA_TRACE
- gg_assert(row < MAX_ORDER);
- gg_assert(i2 < DFA_MAX_BOARD*4 && j2 < DFA_MAX_BOARD*4);
- gg_assert(i2 >= 0 && j2 >= 0);
- fprintf(stderr, "(%d,%d)=%c ", m, n, VAL2ASC(dfa_p[i2][j2]));
-#endif
-
- return dfa_p[i2][j2];
-}
-
-
#if 0
/* debug function */
static void
@@ -769,7 +743,7 @@
for (i = DFA_MAX_BOARD / 2; i < DFA_MAX_BOARD*1.5 ; i++) {
for (j = DFA_MAX_BOARD / 2 ; j < DFA_MAX_BOARD*1.5 ; j++)
if (i != (m+DFA_MAX_BOARD) || j != (n+DFA_MAX_BOARD))
- fprintf(stderr, "%1d", dfa_p[i][j]);
+ fprintf(stderr, "%1d", dfa_p[DFA_PSO(i, j)]);
else
fprintf(stderr, "*");
fprintf(stderr, "\n");
@@ -788,7 +762,9 @@
scan_for_patterns(dfa_t *pdfa, int l, int m, int n, int *pat_list)
{
int state, att, id, row;
+ int dfa_pos;
+ dfa_pos = DFA_POS(m, n) + DFA_OFFSET;
state = 1; /* initial state */
row = 0; /* initial row */
id = 0; /* position in id_list */
@@ -803,13 +779,14 @@
}
/* go to next state */
- state = pdfa->states[state].next[read_board(l, m, n, row)];
+ state = pdfa->states[state].next[dfa_p[dfa_pos + spiral[l][row]]];
row++;
}
ASSERT2(row < MAX_ORDER, m, n);
return id;
}
+
#if DFA_SORT
/* used to sort patterns */
Index: patterns/dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.12
diff -u -r1.12 dfa.c
--- patterns/dfa.c 31 Jan 2002 08:22:00 -0000 1.12
+++ patterns/dfa.c 2 Feb 2002 18:20:06 -0000
@@ -69,8 +69,7 @@
*********************/
/* the private board */
-int dfa_p[DFA_MAX_BOARD * 4][DFA_MAX_BOARD * 4];
-int reverse_spiral[8][DFA_MAX_BOARD * 4][DFA_MAX_BOARD * 4];
+int dfa_p[DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4];
/* auxiliary dfa's for high level functions */
static dfa_t aux_dfa1; /* used to store strings */
@@ -121,7 +120,7 @@
* 6 dfa.
*/
-order_t spiral[8][MAX_ORDER];
+int spiral[8][MAX_ORDER];
/*
* Build the spiral order for each
@@ -142,17 +141,18 @@
*
*/
-static const order_t generator[4] =
- { { 1, 0}, { 0, 1}, {-1, 0}, {0, -1} };
+static const int generator[4] =
+ { 4 * DFA_MAX_BOARD, 1, -4 * DFA_MAX_BOARD, -1 };
void
-buildSpiralOrder(order_t order[8][MAX_ORDER])
+buildSpiralOrder(int order[8][MAX_ORDER])
{
- int Mark[DFA_MAX_BOARD * 4][DFA_MAX_BOARD * 4];
- order_t fifo[8 * MAX_ORDER];
+ int Mark[DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4];
+ int fifo[8 * MAX_ORDER];
int top = 0, end = 0;
- int i, j, k, ll;
- int di, dj;
+ int i, j, i0, j0;
+ int k, ll;
+ int ii;
int delta;
@@ -164,40 +164,30 @@
/* initialization */
- for (i = 0; i != DFA_MAX_BOARD * 4; i++)
- for (j = 0; j != DFA_MAX_BOARD * 4; j++) {
- for (ll = 0; ll != 8; ll++)
- reverse_spiral[ll][i][j] = MAX_ORDER;
- Mark[i][j] = 1;
- }
+ for (ii = 0; ii < DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4; ii++)
+ Mark[ii] = 1;
- for (i = DFA_MAX_BOARD; i != DFA_MAX_BOARD * 3; i++)
- for (j = DFA_MAX_BOARD; j != DFA_MAX_BOARD * 3; j++)
- Mark[i][j] = 0;
+ for (i = DFA_MAX_BOARD; i < DFA_MAX_BOARD * 3; i++)
+ for (j = DFA_MAX_BOARD; j < DFA_MAX_BOARD * 3; j++)
+ Mark[DFA_POS(i, j)] = 0;
end = 0;
top = 1;
- fifo[end].i = DFA_MAX_BOARD * 2;
- fifo[end].j = DFA_MAX_BOARD * 2;
- Mark[fifo[end].i][fifo[end].j] = 1;
+ fifo[end] = 2 * DFA_OFFSET;
+ Mark[fifo[end]] = 1;
/* generation */
while (end < MAX_ORDER) {
- i = fifo[end].i;
- j = fifo[end].j;
- order[0][end].i = i - DFA_MAX_BOARD * 2;
- order[0][end].j = j - DFA_MAX_BOARD * 2;
- reverse_spiral[0][i][j] = end;
+ ii = fifo[end];
+ order[0][end] = ii - 2 * DFA_OFFSET;
end++;
for (k = 0; k != 4; k++) {
- di = generator[k].i;
- dj = generator[k].j;
+ delta = generator[k];
- if (!Mark[i + di][j + dj]) {
- fifo[top].i = i + di;
- fifo[top].j = j + dj;
- Mark[i + di][j + dj] = 1;
+ if (!Mark[ii + delta]) {
+ fifo[top] = ii + delta;
+ Mark[ii + delta] = 1;
top++;
}
}
@@ -205,13 +195,18 @@
/* Then we compute all the geometric transformations
on this order */
- for (ll = 1; ll != 8; ll++)
- for (k = 0; k != MAX_ORDER; k++) {
- delta = DFA_MAX_BOARD * 2;
- TRANSFORM(order[0][k].i, order[0][k].j,
- &(order[ll][k].i), &(order[ll][k].j), ll);
- reverse_spiral[ll][order[ll][k].i + delta][order[ll][k].j + delta] = k;
+ for (k = 0; k < MAX_ORDER; k++) {
+ j0 = order[0][k] % (4 * DFA_MAX_BOARD);
+ if (j0 >= 2 * DFA_MAX_BOARD)
+ j0 -= 4 * DFA_MAX_BOARD;
+ if (j0 < - 2 * DFA_MAX_BOARD)
+ j0 += 4 * DFA_MAX_BOARD;
+ i0 = (order[0][k] - j0) / (4 * DFA_MAX_BOARD);
+ for (ll = 1; ll != 8; ll++) {
+ TRANSFORM(i0, j0, &i, &j, ll);
+ order[ll][k] = DFA_POS(i, j);
}
+ }
}
@@ -792,7 +787,7 @@
void
dfa_init(void)
{
- int i, j;
+ int ii;
if (dfa_verbose > 1)
fprintf(stderr, "dfa: init\n");
@@ -802,9 +797,8 @@
new_dfa(&aux_dfa2, "copyAux ");
/* set the private board to OUT_BOARD */
- for (i =0; i!= DFA_MAX_BOARD*4; i++)
- for (j =0; j!= DFA_MAX_BOARD*4; j++)
- dfa_p[i][j] = OUT_BOARD;
+ for (ii = 0; ii < 4 * DFA_MAX_BOARD * 4 * DFA_MAX_BOARD; ii++)
+ dfa_p[ii] = OUT_BOARD;
}
void
@@ -980,8 +974,12 @@
for (k = 0;
(k != MAX_ORDER - 1) && ((borders > 0) || edges || to_test > 0);
k++) {
- i = spiral[trans][k].i;
- j = spiral[trans][k].j;
+ j = spiral[trans][k] % (4 * DFA_MAX_BOARD);
+ if (j >= 2 * DFA_MAX_BOARD)
+ j -= 4 * DFA_MAX_BOARD;
+ if (j < - 2 * DFA_MAX_BOARD)
+ j += 4 * DFA_MAX_BOARD;
+ i = (spiral[trans][k] - j) / (4 * DFA_MAX_BOARD);
if (i == pat->maxi)
borders &= ~SOUTH_EDGE;
Index: patterns/dfa.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.h,v
retrieving revision 1.10
diff -u -r1.10 dfa.h
--- patterns/dfa.h 14 Jan 2002 22:38:55 -0000 1.10
+++ patterns/dfa.h 2 Feb 2002 18:20:07 -0000
@@ -98,12 +98,14 @@
/* scan order */
+#if 0
typedef struct
{
int i;
int j;
}
order_t;
+#endif
/********************************
@@ -112,7 +114,7 @@
void dfa_init(void); /* Every call to a fda function must be done */
void dfa_end(void); /* between calls of those 2 functions. */
-void buildSpiralOrder(order_t order[8][MAX_ORDER]); /* Needed by matchpat */
+void buildSpiralOrder(int order[8][MAX_ORDER]); /* Needed by matchpat */
/* basic dfa manipulation */
void print_c_dfa(FILE* of, const char *name, dfa_t *pdfa);
@@ -143,16 +145,11 @@
#define ASC2VAL(c) (c < 90 ? dfa_asc2val[(int)c] : 3)
#define VAL2ASC(n) (n < 4 ? dfa_val2asc[n] : '!')
-extern int reverse_spiral[8][DFA_MAX_BOARD * 4][DFA_MAX_BOARD * 4];
-
/* incremental macro */
#define BASE DFA_MAX_BOARD * 2
-
-/* Give the row in spiral order of (i,j) when the scan start at (i0,j0) */
-#define GIVE_SPIRAL_ROW(ll, i0, j0, i, j) \
- (reverse_spiral[ll][BASE + (i) - (i0)][BASE + (j) - (j0)])
-
+#define DFA_POS(i, j) (4 * DFA_MAX_BOARD * (i) + (j))
+#define DFA_OFFSET DFA_POS(DFA_MAX_BOARD, DFA_MAX_BOARD)
/********************************
@@ -162,12 +159,5 @@
extern int dfa_verbose; /* the verbose level */
#endif /* _DFA_H_ */
-
-
-
-
-
-
-
- [gnugo-devel] arend_1_24.5: dfa 1D conversion,
Arend Bayer <=