代码之家 › 专栏 › 技术社区 › kirbo

C++,使用一个字节来存储两个变量

chess pointers performance c++

kirbo · 技术社区 · 15 年前

我正在研究象棋棋盘的表示,我计划将其存储在32字节数组中,每个字节将用于存储两个棋子。(这样每片只需要4位)

这样做会导致访问板的特定索引的开销。您认为这段代码是可以优化的还是可以使用完全不同的访问索引的方法?

C++

char getPosition(unsigned char* c, int index){
    //moving pointer
    c+=(index>>1);

    //odd number
    if (index & 1){
        //taking right part
        return *c & 0xF;
    }else
    {
        //taking left part
        return *c>>4;
    }
}


void setValue(unsigned char* board, char value, int index){
    //moving pointer
    board+=(index>>1);

    //odd number
    if (index & 1){
        //replace right part
                 //save left       value only 4 bits
        *board = (*board & 0xF0) + value;
    }else
    {
        //replacing left part
        *board  = (*board & 0xF) + (value<<4);
    }
}


int main() {

    char* c = (char*)malloc(32);

    for (int i = 0; i < 64 ; i++){
        setValue((unsigned char*)c, i % 8,i);
    }

    for (int i = 0; i < 64 ; i++){
        cout<<(int)getPosition((unsigned char*)c, i)<<" ";

        if (((i+1) % 8 == 0) && (i > 0)){
            cout<<endl;
        }


    }


    return 0;
}

我同样感兴趣的是你对象棋表示的看法,以及对上述方法的优化,作为一个独立的问题。

谢谢

编辑

谢谢你的回复。不久前,我创建了棋盘游戏,在那里我使用64字节的板表示。这次我尝试了一些不同的方法,只是想看看我喜欢什么。记忆不是什么大问题。比特板肯定在我的名单上。谢谢

6 回复 | 直到 15 年前

Edward Strange 15 年前

这就是过早优化的问题。你的棋盘本来需要64个字节来存储,现在需要32个字节。这到底给你带来了什么?你真的分析过这种情况,看看是否需要保存这些记忆吗?

假设你使用了一种最不理想的搜索方法,直接AB搜索到深度D,没有启发式,并且你在搜索之前在一个位置上生成了所有可能的移动,那么你的电路板所需的绝对最大内存将是Sizeof(Board)*W*D。e w=100,大的d=30,那么在深度d,64k和32k,内存中会有3000块板……真的值得吗?

另一方面,你增加了访问board[位置]所需的操作量,每次搜索将被称为数百万次。

当建立国际象棋人工智能的主要事情,你将最终寻找的是CPU周期,而不是内存。如果你的目标是手机或其他东西,这可能会有一些变化,但即便如此,在你达到足够的深度导致任何内存问题之前,你会更加担心速度。

至于我更喜欢哪种表示法…我喜欢bitboard。我没有做过很多认真的测量,但是我比较了我做的两个引擎,一个是bitboard和一个数组,bitboard一个更快,可以达到比另一个更大的深度。

tony 15 年前

让我首先指出一个潜在的bug(取决于编译器和编译器设置)。而错误就是为什么过早优化是邪恶的:

   //taking left part
    return *c>>4;

如果*C为负,则>>可能会重复负高位。二进制IE:

0b10100000 >> 4 == 0b11111010

对于某些编译器(即C++标准将它留给编译器来决定是否携带高位,以及CHARR是签名还是未签名)。

如果您确实想继续使用压缩位(让我说,您可能不必费心,但这取决于您自己),我建议将压缩位包装到一个类中,并重写[],以便

board[x][y]

给你未包装的零件。然后您可以轻松地打开和关闭包装,并且在任何情况下都具有相同的语法。如果内联运算符重载,那么它应该和现在的代码一样高效。

Joey Adams 15 年前

好吧,64字节是一个非常小的内存量。你最好只用一个字符[8][8]。也就是说,除非你打算吨棋盘的。使用char[8][8]可以更容易(更快)地访问电路板并对其执行更复杂的操作。

如果您仍然有兴趣将电路板存储为打包表示(无论是用于实践还是存储大量电路板),我认为您在位操作方面“做得很好”。如果要使用 inline 关键字。

Mark B 15 年前

如果不能用一个完整的字节来表示一个正方形,空间是否足够考虑?这将使访问更容易跟踪程序,而且由于不需要位操作,访问速度可能更快。

否则,为了确保一切顺利进行,我将确保所有类型都是无符号的:getposition返回无符号字符,并用“u”(例如0xf0u)限定所有数字文本,以确保它们始终被解释为无符号。很可能您不会对签名ness有任何问题,但是为什么要冒险使用一些行为出乎意料的架构呢?

Pavel Radzivilovsky 15 年前

代码不错,但如果您真的对性能优化有那么深入的了解,那么您可能应该了解更多关于您的特定CPU体系结构的信息。

afaik,您可能会发现将一个棋子存储在8个字节内会更有效。即使递归15次深移动,二级缓存大小也很难成为一个约束条件,但是ram不对齐 可能是 . 我想象棋棋盘的正确处理应该包括expand()和reduce()函数,以便在算法的不同部分中在棋盘表示之间进行转换:有些在紧凑表示上可能更快,有些则相反。例如,缓存和通过两个相邻单元格的组合进行散列的算法可能对紧凑结构有好处,其他的都没有。

如果性能非常重要,我也会考虑开发一些辅助硬件,比如一些fpga板,或者一些gpu代码。

isekaijin 15 年前

作为一个棋手,我可以告诉你:一个位置不仅仅是每一个棋子的位置。你必须考虑到其他一些事情:

下一步必须移动哪一边?
白色和/或黑色城堡可以是国王和/或皇后区吗?
一个卒子能被带走吗?
从上一次棋子移动和/或捕捉移动以来,已经过了多少次移动?

如果你用来表示职位的数据结构没有反映出这些信息,那么你就有大麻烦了。