C中的三位无符号整数

4
我正在建立一个深度神经网络来玩连四游戏,并且它需要与其他人工智能机器人竞争,但是我使用的计算机非常有限,只有几个核心和少量内存(我还不知道具体的限制)。因此,我希望尽可能地优化我的训练集。当前,我的训练集将棋盘状态表示为以下形式:
b表示空白(没有棋子)
x表示"x"棋子
o表示"o"棋子
win表示已获胜 loss表示输了
draw表示平局
基本上,我想将我的3位整数映射到这些占用内存较多的字符串中。我考虑使用short类型,但16位的short比char更糟糕。我想这样进行映射:
000 -> b
001 -> x
010 -> o
011 -> win
100 -> loss
101 -> draw
由于我可以用3位空间代替每个字符的8位(哎呀!),所以我想尝试这种方法。但是我不知道如何在c语言中实例化这样的变量。
训练集的长度为67557行,每行表示一个6x7的棋盘和一个赢/输/平的子句。因此,每个字符节省5位将为每行节省(5*6*7)+(5*1)=215个位,总共节省215*67557=14524755位(总共2.90 MB中的1.81 MB,整体空间减少了62%)。

2
顺便说一下,连四这个游戏已经被解决了:第一个玩家总是能赢。实现它,你就可以轻松击败竞争对手! - Bathsheba
2
那么,胜利、失败和平局状态,不应该与棋子的放置无关吗?棋子是空的、是圆形、还是叉形或胜利,这似乎很奇怪?如果你把它们分离开来,那么你只需要用两个比特就可以储存棋子状态,这样更好地适合字节(每个字节有四个棋子)。然后把平局/胜利/失败状态连接到棋盘上,而不是单独的棋子。 - Some programmer dude
@JoachimPileborg 这是我考虑过的一件事,但是我正在优化一个当前数据集,其中行类似于 x,b,b,b...o,o,x,b,b,win,并且我认为最好的起点是迭代它并用优化后的设置替换当前设置。 - asdf
2
你需要许多状态,但只有一个胜/负/平的指示器,对吧?除了更节省空间以分离状态之外,当你不必担心三个位跨越字节或字边界时,代码也会变得*更加简单。只是这么说... :) - Some programmer dude
1
像Joachim所说,仅使用2位地图坐标更有效率。这样,你需要84位地图。如果你将其放入6个16位变量中,你还剩下12位结果(胜利/失败/平局)。或者用11个8位变量,其中4位用于结果。 - user694733
3个回答

7

那如果您使用位域呢?

struct S {
    unsigned w : 3;
    unsigned x : 3;
    unsigned y : 3;
    unsigned z : 3;
};

在大多数系统中,sizeof(struct S) == 2,但你可以在其中存储4个值!

现在,你可以尝试这样做...

struct S myS;
s.w = 0; // Okay
s.x = 6; // Okay
s.y = 8; // Will overflow/wrap-around (why do the standards differentiate between those two?)

但是,如果你做类似于...

struct S first;
struct S second;

您将失去您所追求的内存效率,因为编译器必须为这两个对象提供地址,因此它们需要按字节对齐,因此它们通常一起占用32位,在其中可以保存八个值,但是,如果您有一个单独的结构体来保存所有八个变量,则内存使用量通常为24位。
请注意,包含使用所有可用空间的位域的结构(例如上面提到的8个成员结构:8 * 3 == 24; 24 % 8 == 0)更适合您的目的,因为您可以拥有它们的数组,获得位域的好处,并在此过程中不浪费任何内存。第一个结构体因为每个类型为S的对象浪费了4位,因此效率低下。
顺便说一句:不要尝试使用&s.xsizeof(s.x),由于显而易见的原因,它根本行不通。

1
请注意,这可能会(取决于编译器)导致意外的扩展,结果是 s.y = 6; 如果 (s.y == 6) 将失败,因为 s.y 现在是一个小的负数。 - Tom Tanner
我真诚地希望在大多数系统上,sizeof(struct S)更像是2。 - Tom Tanner
@TomTanner:抱歉,sizeof(struct S) == 16 是一个打字错误。 - 3442
2
@TomTanner,可以通过使用“unsigned”来避免这种情况,从而达到更好的效果。 - Jens Gustedt
1
不,我希望这部分不依赖于具体实现。如果一个位域是无符号的,它应该具有所有正值,并且隐式转换为 int 永远不会改变它为负数。 - Jens Gustedt
显示剩余3条评论

3
你在这里混淆了两三件不同的事情。
  • 训练文件格式
  • 解析后训练集的内存存储格式(如果您需要保留已解析状态以供将来参考)
  • 单个棋盘状态的未打包表示+可选的W/L/D标志
这三种格式都可以不同。训练文件可以是文本,便于编辑。当然,即使您的主程序以二进制格式读取训练集,该二进制也可以由单独的工具从易于编辑的文本格式“编译”而成。
用于处理单个棋盘位置的内部表示:

这需要快速访问和循环。由于您正在训练神经网络,而不是直接编写人工智能,因此您可能不需要经常使用此表示。如果您只需要将每个元素应用于神经网络输入,则没有必要使用单独的格式:直接从更紧凑的表示中解压缩到神经网络输入。

然而,如果您需要多次循环单个棋盘状态,则有一些有趣的选择。正如许多人指出的那样,胜利/失败/平局/未决标志应该与棋盘状态分开考虑。因此,每个棋盘将有一个标志,而不是在每个棋盘位置存储标志。
  • 位棋盘: 我已经阅读了有关国际象棋引擎(例如Crafty)使用64位无符号整数存储所有白色兵的位置的文章。例如,您可以对位图进行按位或运算,以找到任何种类的白色棋子在哪里。

    位图(一个用于o,一个用于x)将记录整个状态。 连接4个棋盘具有6 * 7网格位置,因此每个位图可以为64位,但32b太小。popcount(board.o)告诉您棋盘上有多少个 o assert(o&x == 0)将是一个很好的健全检查,因为同一位置上永远不可能有 o x

    在结构体中使用两个打包的42b字段是一个坏主意,因为加载/存储速度较慢。 即使将它们打包成48位字段(因此它们以字节边界结束)也会导致加载/存储速度变慢。 记住,这是我们的快速格式。 我们可以使用打包格式进行长期存储。

    board [0] [0] && board [0] [1] && board [0] [2] && board [0] [3]这样的内容(虽然不使用该语法)在位棋盘上非常快。 一个按位与仅留下可能设置的那些位,然后您可以与掩码进行比较,以查看是否所有位都已设置。 要测试 || 而不是&&,请省略第二步。 您可以对 o x 位图或 o | x 进行这些测试,以检查任一类型的棋子。 但是,如果必须从变量位置运行时构建掩码,则效率不高。

    要扫描获胜的棋盘,您可以检查左列,然后将掩码向左移,以便检查下一列。 实际上,像这样暴力地检查所有列可能比检查标记的邻居,寻找2个连续的候选项更慢。

    如果位图完全为64位,并表示8x8板,则某些操作可能更容易,但您实际上只使用其左下角的7x6。 这样,单独的列在64位整数的单独字节中。 每列在单独的字节中可能比行更有用,因为您可能想要查找列中使用的最高位置。 这只是在列上进行查找第一个设置位操作。 从位图中提取8位块速度更快(不需要屏蔽)。 您可以将42位位图解包到每个列的单独变量中。 在x86上,前4个寄存器对于第一个和第二个8位块是字节可寻址的(AX(RAX的低16位)由AL和AH组成),您(或编译器,但他们可能不会这么聪明)仍然可以将7列存储在4个寄存器中,并能够单独bsr(位扫描反转)任何列。

// Sample bitboard implementation:
struct game_state {
    struct board_state {
       uint64_t o, x;
    } board;
    enum winlose { GAME_UNDECIDED=0, GAME_WIN_O, GAME_WIN_X, GAME_DRAW } victory;
};

  • 2位字段数组:不要使用。类似的实现方式会为每个位置使用一个2位比特位。在C语言中,无法使用漂亮的board[row][col]语法,并且42 * 2位无法放入单个寄存器中。交织位板没有优势,并且使一些事情变得更糟,尤其是因为整个东西无法适应64位。(如果您想在位板版本中查找未占用的空间,则需要在o|x中查找零位。在这里,您必须检查每对2位,而不能使用一个位来将整个问题适合到一个寄存器中。尽管如此,您可以创建一个宏来移动/屏蔽表示给定行/列的2位。它不会生成高效的代码。

  • 字节数组:对于循环检查给定棋盘位置的邻居,使用此格式可能会更快。在位板中,通过位移棋盘以使两个感兴趣的位排成一行,然后进行按位与运算,最后测试该位,即可测试board[i][j] && board[i][j+1]。至少在x86上,有小字节偏移的寻址模式,因此,给定一个棋盘位置的地址,与另一个棋盘位置进行按位与运算可能只需要一条指令。

    在每个字节中,一个位表示x,另一个位表示o,另一个位应设置为如果位置是xo。这允许检查多个位置是否都被占用,并检查已占用的位。否则,您必须检查每个网格中的xo位是否已设置。

// Sample byte-array implementation:
enum boardpos {
    POS_EMPTY = 0,
    POS_O = 1<<0,
    POS_X = 1<<1,
    POS_OCCUPIED = 1<<3
};
// maybe #define for these constants instead?

struct game_state {
    struct board_state {
       uint8_t pos[6][7];
    } board;
    enum winlose { GAME_UNDECIDED=0, GAME_WIN_O, GAME_WIN_X, GAME_DRAW } victory;
    // or maybe stuff the winlose info into the high bits of board.pos[0][0]?
    // Not much point, since the struct will probably be the same size after padding anyway.
};

文件格式表示:

一种更紧凑但仍易于使用的格式是xbbb...ooxbbw。然后,您不需要将行解析为字符串,只需作为大小为43个字符(如果每个记录由换行符分隔,则为43)的恒定大小块进行解析。如果有任何不是胜利、失败或平局的棋盘位置,请使用另一个字符来标记。空格或'n'

省略逗号可以将大小减少近一半。您不想在逗号和其他东西上解析输入。从简单的运行长度编码符号中可能会有潜在的进一步收益,例如xb2o1xb1w。看到数字意味着重复最后一个字符那么多次。也许x表示一个x,大写X表示两个x。这已经到了人类难以阅读的地步。LZOP或LZ4压缩可能能够很好地压缩。

二进制文件格式

显然,文本表示有其限制。 固定大小的二进制记录可以非常小,因为需要存储的信息不多。每个网格位置使用2位可能已经足够紧凑,但仍存在冗余,因为它可以表示xo同时出现在同一位置的不可能状态。为了做得更好,您需要将整个棋盘或整行或整列的状态映射到多位表示中。维基百科说,所有棋盘上填充0至42个棋子的合法位置总共有4,531,985,219,092个。这只是2 ^ 42的稍微超过。因此,43位应该足以表示任何有效的棋盘状态,包括所有未决定的位置。我不知道如何将游戏编码为43位整数,至少没有可用的方法(即比枚举所有可能的游戏并在匹配的那个停止更快的方法)。

如果您使用位棋盘作为内部快速表示,请将它们紧密存储在文件格式中,使得ox棋盘以及w/d/d状态只占用12个字节,或者如果您喜欢整数,则为16个字节。
// do some pre-processor stuff to choose between GNU C __attribute__ ((__packed__))
// and the MSVC #pragma pack
struct __attribute__ ((__packed__)) compact_game_state {
    struct __attribute__ ((__packed__)) compact_board_state {
       uint64_t o:42, x:42;
    } board; // sizeof = 11
    uint8_t victory;
}; // sizeof = 12

struct semi_compact_game_state {
    struct __attribute__ ((__packed__)) semi_compact_board_state {
       uint64_t o:48, x:48;
    } board; // 96 bits = 12 bytes
    enum winlose victory; // another 4 bytes
};

这些代码可以通过g++编译: 在godbolt上查看
使用端无关代码进行I/O,这样就不会在大端机器上出现问题。这是一个文件格式,因此实际上访问方式并不重要,只要正确的字节放在正确的位置即可。对于文件格式,小端可能是一个好选择,在小端机器上,load/store代码是一个空操作。或者只需懒惰地对一组结构进行二进制I/O,并仅在与训练数据集具有相同字节序的机器上使用您的代码。
如果您不使用位棋盘,最好使用一个由2位字段组成的数组。随机访问可能很慢,但将其转换为字节数组可能比分别用于两个位字段更快。屏蔽掉低2位,将其用作索引进入查找表{POS_EMPTY,POS_O | POS_OCCUPIED,POS_X | POS_OCCUPIED}。然后按2位进行位移,将下一个字段带入低位。棋盘占用84位,因此可以在单独的32位或64位块中执行操作。不需要进行128位双重移位。胜利/失败/平局信息可以放在最后的2位块中。
将此打包成一个12字节的三个uint32_t结构,或一个uint64_t和一个uint32_t结构。或者只是一个uint8_t数组,但这样更难让编译器执行一次宽加载。你可以将东西打包到一个11字节的结构中,但对齐更成问题。如果节省1/12的内存大小对缓存有用的话,请去做。在x86 CPU上,跨越高速缓存线的负载只会多花费几个周期,并且您不会经常进行加载。(使用12B结构,第一块的64位加载不会对齐到64b,但至少会分成两半,这是一种特殊情况,在某些CPU上比不平衡的高速缓存线分裂更快。)
将单独的位板解码为字节数组需要分别移动每个位板,我想。它仍然可以是无分支的,但不太好看。
棋谱数据库的内存存储
在表示之间进行转换需要CPU时间,因此如果没有用处,就从文件格式转换为内部格式。

如果您使用的是文本文件格式,并且使用非紧凑快速格式,则为此单独创建格式可能仅有用。在这种情况下,将文件解析为打包的2位位置(例如该文件格式,请参见上文)。

如果您的文件格式是二进制的,请保留它。(甚至只需内存映射文件。)


@asdf:我有另一个有趣的想法:对于位棋盘,列主存储意味着您可以使用位扫描函数(转换为单个指令)而不是循环来查找列中最高的占用位置。我知道你说你正在使用神经网络,所以我不知道高效的位棋盘搜索功能是否有任何用处。 - Peter Cordes

2
如果机器有限并且你必须在时间上竞争,那么你不想在位域宽整数上进行CPU密集型操作。最好使用本机字大小。其次是使用字节大小的整数,因为许多机器对字节大小的实体具有高效的操作。
这总是一个优化速度或内存使用的问题。

2
这是不正确的。你有注意到OP提供的(以兆字节为单位的嵌入式系统)测量值吗?这对他来说根本不可行。 - 3442
1
几乎所有的 CPU 都拥有足够高效的字节操作能力(或者至少能够将一个字节零扩展到整个寄存器),因此建议使用一个由 32 位整数表示的板子并没有意义。一个由 8 位整数组成的数组是处理游戏状态的好选择,但这并不意味着它是存储多个游戏的好文件格式或内存格式,因为 @Kemy 提出了一个很好的观点。请参考我的答案。顺便说一下,象 crafty 这样的国际象棋引擎实际上会大量使用适合于 64 位寄存器的比特棋盘。比特测试可以检查整个对角线等等。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接