0

我正在处理作为字符串接收的游戏状态，需要将其转换为 BitBoard。我相信我现在有一个功能可以实现这一点，但想知道如何优化它以加快执行速度？我最初是从一个带有以下想法的循环开始的：

for (i = 0; i < 23; ++i) 
{
   if     (s.at(n) == 'x') set bit[2],  // Start with x as there are more x's
   else if(s.at(n) == 'W') set bit[0],  // W next as W goes first
   else                    set bit[1]   // B last
}

但我想我可以展开循环并跳过“i”的比较和递增。这样做之后，我想我可以删除最后一个对“B”的检查，并接受 W | 的赞美。x 并从中减去 4286578688 得到 23 位。这给了我以下代码：

std::string board = "xBWxWxBWxWxxBxxxWxBxxBx";   // String to convert to bitboard 
unsigned int bit;                                // Integer used for parsing values
unsigned int boards[3] {0, 0, 0};                // W in [0], B in [1], & x in [2]
if (board.at(0)  == 'x') { boards[2] |= (1 << 22); } else if (board.at(0)  == 'W') { boards[0] |= (1 << 22); }
    ⋅ 
    ⋅
    ⋅
if (board.at(22) == 'x') { boards[2] |= (1 << 0);  } else if (board.at(22) == 'W') { boards[0] |= (1 << 0);  }
boards[1] = ~(boards[0] | boards[2]) - 4286578688;        // Take W's & x's compliment - 4286578688 to get 2163730
printf("%d | %d | %d\n",boards[0], boards[1], boards[2]); // Expected Output: "1351744 | 2163730 | 4873133"

是否有任何其他技巧可以进一步优化此过程以提高速度？我不关心文件大小。

最后，我将如何将 board[W, B, x] 转换回字符串？（例如，玩家“W”在第 22 位添加了一个棋子，结果是boards[] = {1351745, 2163730, 4873132}。如何将其转换为：board = xBWxWxBWxWxxBxxxWxBxxBW？）

编辑：我得到了恢复到板的功能，如下所示：

char state[23];
for (int i = 0, j = 22; i < 23; ++i, --j) {
    if (boards[2] & (1 << j)) { state[i] = 'x'; } else if (boards[0] & (1 << j)) { state[i] = 'W'; } else { state[i] = 'B'; }
}
4

1 回答 1

0

你提到它的评论，你是一个新手。我认为你需要有很多背景知识才能做出关于优化的明智决定。

首先，编译器是很好的优化器。它们内置了控制流分析、内联、执行重新排序等等。它们可以根据 c++ 标准提供的保证进行优化。查找未定义的行为优化和优化以及指针别名作为了解编译器可以和不能为优化做什么的起点。

其次，如果不进行基准测试，就无法知道您的更改是否真的提高了程序的速度。就像您提到的那样，分析器可以帮助您找出程序中花费的时间。

第三，您提到您听说过“字符串很慢”。您应该问的一个问题是“与什么相比？” std::string数据在堆上分配（除非它符合短字符串优化的条件，这是一些编译器可以为您做的另一件事）。我假设缓慢意味着它必须在增长字符串时从堆中加载和新分配。分配速度很慢，应尽可能避免速度。您可以做的一件事是std::string::reserve您希望字符串采用的最大大小。这将分配一次内存，而不是在您添加内存时动态增长它，这会导致一次或多次分配。查找堆栈与堆、分配成本和缓存未命中。

TL;DR：基准测试和实验，在你试图超越编译器之前增加你的知识。

于 2021-05-17T20:13:23.127 回答