类似俄罗斯方块的游戏

Question

我正在考虑将我的Python代码重写为C++，因为它包含了相当多的简单循环。我惊讶地发现，代码的这个关键部分(下面的代码)比Python代码慢5倍，我希望您能帮助我找出原因。

上下文是一种类似于俄罗斯方块的游戏，在这种游戏中，我通过黑板递归，在遍历过程中访问每个瓷砖(如果还没有访问它的邻居的话)。

C++

void Board::traverse (Tile *t, Neighbours neighbours)
  {
    t->visited = true;
    COO coo = make_pair(t->i, t->j);
    Buddies buddies = neighbours[coo];
    if (t->color != '0' && t->color != '.')
      {
        for (uint i = 0; i < buddies.size(); i++)
          {
            Tile *buddy = &this->field[buddies[i]];
            if (buddy->visited && buddy->color == t->color)
              {
                if (buddy->chainId == -1)
                  {
                    buddy->chainId = this->chains.size();
                    this->chains[buddy->chainId].push_back(*buddy);
                  }
                t->chainId = buddy->chainId;
                this->chains[t->chainId].push_back(*t);
                break;
              }
          }
        if (t->chainId == -1)
          {
            t->chainId = this->chains.size();
            this->chains[t->chainId].push_back(*t);
          }
      }

    for (uint i = 0; i < buddies.size(); i++)
      {
        if (!this->field[buddies[i]].visited)
          {
            this->traverse(&this->field[buddies[i]], neighbours);
          }
      }
  }

Python

class Board():

    def __init__(self, s):
        self.field = []
        self.chains = {}
        self.heights = None
        self.score = 0
        self.step = 1

    def traverse(self, t=None):
        t.visited = True
        buddies = neighbours[(t.i, t.j)]
        if t.color != '0' and t.color != '.':
            for i, j in buddies:
                if self.field[i][j].visited and self.field[i][j].color == t.color:
                    if self.field[i][j].chain_id is None:
                        self.field[i][j].chain_id = len(self.chains)
                        self.chains[self.field[i][j].chain_id] = [self.field[i][j]]
                    t.chain_id = self.field[i][j].chain_id
                    self.chains[t.chain_id].append(t)
                    break
            if t.chain_id is None:
                t.chain_id = len(self.chains)
                self.chains[t.chain_id] = [t]

        for i, j in buddies:
            if not self.field[i][j].visited:
                self.traverse(self.field[i][j])

**这种递归的原因是，我们不是在寻找简单的直线清晰，而是一条“线”可以被看作相邻的4个或更多块；使通过连接节点进行的递归更符合逻辑。此上下文中的链是一组颜色相同的连接节点。

Answer 1

第一关：

void Board::traverse (Tile *t, Neighbours neighbours)
                          ^^^^ Pointers are bad idea.
                               They make resource management hard to 
                               reason about as pointers have no
                               ownership semantics. Prefer a reference
                               if it can not be nullptr.

void Board::traverse (Tile *t, Neighbours neighbours)
                               ^^^^^^^^^^^^^^^^^^^^^ 
                              Here you are passing neighbours by value.
                              This means you are making a copy of the
                              object. Prefer const reference.

    // What is the type of COO
    // is there a better way to create it?
    COO coo = make_pair(t->i, t->j);


    // Here you are copy the content of `neighbours[coo]`
    // into buddies. Do you need a copy or can we just
    // use a reference to the original value.
    Buddies buddies = neighbours[coo];


            // Prefer a reference to a pointer.
            Tile *buddy = &this->field[buddies[i]];



                    // Here you are making a copy of buddy.
                    // Do you really need another copy?
                    this->chains[buddy->chainId].push_back(*buddy);


                // Again you are copy the value of tile into chains.
                this->chains[t->chainId].push_back(*t);

            // Another copy of tiles is being put here.
            this->chains[t->chainId].push_back(*t);


            // And you are copying neighbours into the
            // recursive call here.
            this->traverse(&this->field[buddies[i]], neighbours);

使用此

您对this的使用不是惯用的。

this->chains[t->chainId].push_back(*t);

写起来容易得多：

chains[t->chainId].push_back(*t);

使用this的唯一原因是消除使用隐藏变量的歧义。但是，隐藏变量是一个等待发生的错误。因此，最好完全避免隐藏变量(甚至打开错误以确保它们不会发生)。

-Wall -Wextra -Wshadow -Werror