[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Eliot-dev] eliot/game board_search.cpp [multibyte]
From: |
eliot-dev |
Subject: |
[Eliot-dev] eliot/game board_search.cpp [multibyte] |
Date: |
Sat, 14 Jan 2006 21:02:14 +0000 |
CVSROOT: /sources/eliot
Module name: eliot
Branch: multibyte
Changes by: Olivier Teulière <address@hidden> 06/01/14 21:02:14
Modified files:
game : board_search.cpp
Log message:
Optimization over the original algorithm: ignore the current anchor
if none of the letters in the rack matches the cross set.
This optimization saves more than 6% of the total regression time
(measured on the total time needed for 100 successive runs of the
regression)
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/eliot/eliot/game/board_search.cpp.diff?only_with_tag=multibyte&tr1=1.9.2.1&tr2=1.9.2.2&r1=text&r2=text
Patches:
Index: eliot/game/board_search.cpp
diff -u eliot/game/board_search.cpp:1.9.2.1 eliot/game/board_search.cpp:1.9.2.2
--- eliot/game/board_search.cpp:1.9.2.1 Tue Jan 3 20:42:13 2006
+++ eliot/game/board_search.cpp Sat Jan 14 21:02:13 2006
@@ -219,6 +219,12 @@
{
int row, col, lastanchor;
Round partialword;
+
+ list<Tile> rackTiles;
+ iRack.getTiles(rackTiles);
+ list<Tile>::const_iterator it;
+ bool match;
+
for (row = 1; row <= BOARD_DIM; row++)
{
partialword.init();
@@ -233,20 +239,35 @@
!iTilesMx[row - 1][col].isEmpty() ||
!iTilesMx[row + 1][col].isEmpty()))
{
- if (!iTilesMx[row][col - 1].isEmpty())
+ // Optimization compared to the original Appel & Jacobson
+ // algorithm: skip Leftpart if none of the tiles of the rack
+ // matches the cross mask for the current anchor
+ match = false;
+ for (it = rackTiles.begin();
+ !match && it != rackTiles.end(); it++)
{
- partialword.accessCoord().setCol(lastanchor + 1);
- ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
- iJokerMx, iRack, partialword, iResults,
- Dic_root(iDic), row, lastanchor + 1, col);
+ if (iCrossMx[row][col].check(*it))
+ {
+ match = true;
+ }
}
- else
+ if (match)
{
- partialword.accessCoord().setCol(col);
- LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
- iJokerMx, iRack, partialword, iResults,
- Dic_root(iDic), row, col, col -
- lastanchor - 1);
+ if (!iTilesMx[row][col - 1].isEmpty())
+ {
+ partialword.accessCoord().setCol(lastanchor + 1);
+ ExtendRight(iBoard, iDic, iTilesMx, iCrossMx,
iPointsMx,
+ iJokerMx, iRack, partialword, iResults,
+ Dic_root(iDic), row, lastanchor + 1, col);
+ }
+ else
+ {
+ partialword.accessCoord().setCol(col);
+ LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, partialword, iResults,
+ Dic_root(iDic), row, col, col -
+ lastanchor - 1);
+ }
}
lastanchor = col;
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Eliot-dev] eliot/game board_search.cpp [multibyte],
eliot-dev <=