c中的3位无符号整数
3 bit unsigned integer in c
我正在建立一个深度神经网络来玩 connect-4，它必须在非常有限的机器上与其他 AI 机器人竞争（还不知道具体的限制，只是我只有几个核心和少量内存）。因此，我希望以任何可能的方式优化我的训练集。它目前代表董事会上的州：
b 为空白（无片）
x "x" 件礼物
o "o" 件礼物
win 获胜设置
loss 丢失设置
draw 绘制设置
本质上，我正在尝试对其进行映射，以便我的 3 位整数可以代替这些占用大量内存的字符串。我考虑过使用 short，但在 16 位时它比 char 差。我想这样映射它：
000 -> b
001 -> x
010 -> o
011 -> win
100 -> loss
101 -> draw
因为我可以用 space 的 3 位而不是字符来表示这些状态（每个字符 8 位，哎呀！）我想尝试一下。但是我不确定如何在 c.
中实例化这样的变量
训练集有 67557 行，每行代表一个 6x7 的棋盘，后面跟着一个 win/loss/draw 子句。因此，每个字符节省 5 位将每行节省 (5*6*7)+(5*1) = 215 位，整体节省 215*67557 = 14524755 位（总共 2.90 MB 中的 1.81 MB，整体减少 62% space）。
如果你使用 bitfields 呢？
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 位。
请记住，包含使用所有可用 space 的位域的结构（例如上面提到的 8 成员结构：8 * 3 == 24; 24 % 8 == 0）更适合您的目的，因为您可以拥有它们的数组，获得位域的好处，并且在此过程中不浪费内存。因此第一个结构是低效的，因为它为每个 S.
类型的对象浪费了 4 位
顺便说一句：不要尝试使用 &s.x 或 sizeof(s.x)，因为显而易见的原因，它根本不起作用。
如果机器有限并且您必须（按时）竞争，那么您不想对位域范围的整数进行 CPU 繁重的操作。最好是使用本机机器字大小。其次最好是使用字节大小的整数，因为许多机器对字节大小的实体都有高效的操作。
优化速度或内存使用总是一个问题。
您将这里的两个或三个不同的东西混为一谈。
- 训练文件格式
- 解析后训练集的内存存储格式（如果您需要保留解析后的状态以供将来参考）
- 单板状态的解包表示+可选？ W/L/D 标志
这三种格式都可以不同。训练文件可以是文本以便于编辑。当然，即使您的主程序以二进制格式读取训练集，该二进制文件也可能 "compiled" 来自单独工具易于编辑的文本格式。
使用单板位置的内部表示：
这需要快速访问和循环。由于您正在训练神经网络，而不是直接编写 AI，因此您可能不需要太多地使用这种表示。如果除了将每个元素应用于神经网络输入之外不需要做更多的事情，那么使用单独的格式是没有意义的：只需直接从更紧凑的表示形式解压缩到神经网络输入。
但是，如果您必须多次遍历单个棋盘状态，您有一些有趣的选择。正如多人指出的那样， win/loss/draw/undecided 标志应该与棋盘状态分开考虑。所以你会在每个板上有一个标志，而不是在每个板位置存储标志。
bit-board：例如，我读过有关国际象棋引擎（例如 crafty）使用 64 位 unsigned int 来存储所有白色棋子所在位置的信息。您可以将位图按位或运算在一起，找出所有白色块的位置。
位图（一张用于 o，一张用于 x）将记录整个状态。 connect-4 板有 6*7 个网格位置，因此每个位图可以是 64 位，但是 32b 太小了。 popcount(board.o) 告诉你棋盘上有多少 o。 assert(o & x == 0) 将是一个很好的完整性检查，因为在同一位置永远不会有 o 和 x。
在一个结构中使用两个打包的 42b 字段不是一个好主意，因为 load/store 会很慢。即使将它们打包成 48 位字段（因此它们以字节边界结束）也会导致速度变慢 loading/storing。请记住，这是我们的快速格式。我们可以使用打包格式进行长期存储。
像 board[0][0] && board[0][1] && board[0][2] && board[0][3] 这样的东西（尽管不是那种语法）在位板上的编译时常量位置非常快。一个按位 AND 只留下那些可能设置的位，然后您可以与掩码进行比较以查看是否设置了 all 这些位。要测试 || 而不是 &&，请省略第二步。您可以针对 o 或 x 位图或 o|x 进行这些测试以检查任何一种片段。但是，如果您必须在 运行 时间从可变位置构建掩码，则效率不高。
要扫描棋盘以确定是否获胜，您可以检查左列，然后对您的掩码进行位移，使其检查下一列。实际上像这样强力检查所有列可能比检查标记的邻居慢，寻找连续 2 个候选者。
如果位图是完全64位的，一些操作可能会更容易，代表一个8x8的板，但你实际上只使用它的左下角的7x6。这样，单独的列位于 64 位整数的单独字节中。将每一列放在一个单独的字节中可能比行更有用，因为找到一列中使用次数最多的位置是您可能想要做的事情。这只是对列的 find first set bit 操作。从位图中提取 8 位块更快（不需要屏蔽）。不过，您可以解压缩 42 位位图以分隔每列的变量。在 x86 上，前 4 个寄存器对于第一个 和第二个 8 位块（AX（RAX 的低位 16）由 AL 和 AH 组成）是字节可寻址的，您（或编译器，但他们可能没那么聪明）可以在 4 个寄存器中存储 7 列，并且仍然能够分别 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 位位域。 It's impossible to use with nice board[row][col] syntax in C，并且 42*2 位不适合单个寄存器。交错位板没有任何优势，并且使某些事情变得更糟，尤其是。因为整个东西不适合 64 位。 （如果你想在 bitboard 版本中寻找未占用的空间，你在 o|x 中寻找零位。在这里，你必须检查每一对 2 位，而不是能够使用一个位来适应整个问题到寄存器中。不过，您可以为 shift/mask 表示给定 row/column 的 2 位创建一个宏。它不会生成有效的代码。
字节数组：使用这种格式循环检查给定棋盘位置的邻居可能会更快。在位板中，测试 board[i][j] && board[i][j+1] 可以通过对板进行位移来完成，这样感兴趣的两位就可以排成一行，然后按位与，然后对该位进行位测试。至少在 x86 上，存在具有小字节偏移的寻址模式，因此给定一个板位置的地址，与另一个板位置可能只需要一条指令。
在每个字节中，一位代表x，另一位代表o，如果位置是x 或 o。这允许通过将它们与在一起并检查占用的位来检查多个位置是否都被占用。否则，您必须检查每个网格中是否设置了 x 或 o 位。
// 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 个）。如果您有任何不是赢、输或平局的棋盘位置，请使用另一个字符来标记它。 Space 或 'n'.
只要省略逗号，您的尺码就会减半。您不想解析逗号之类的输入。简单的 运行 长度编码符号（如 xb2o1xb1w）可能会带来更多收益。看到一个数字意味着重复最后一个字符多次。也许 x 表示一个 x，大写 X 表示两个 x。这已经到了人类难以阅读的地步。 LZOP 或 LZ4 压缩可能可以很好地压缩东西。
二进制文件格式:
显然文本表示是有限制的。固定大小的二进制记录可以非常小，因为要存储的信息不多。每个网格位置使用 2 位可能足够紧凑，但仍然存在冗余，因为它可以表示同一位置的 x 和 o 的不可能状态.为了做得更好，您需要将整个板或整行或整列的状态映射到多位表示。 Wikipedia says 0 到 42 块的所有游戏板有 4,531,985,219,092 个合法位置。那刚好超过 2^42。所以 43 位应该足以表示任何有效的板状态，包括所有尚未确定的位置。 IDK 如何将游戏编码为 43 位整数，至少没有任何可用的（即比实际枚举所有可能的游戏并在匹配的游戏处停止更快。）
如果您使用位板作为内部快速表示，将它们以您的文件格式打包存储，因此 o 和 x 板加上 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++ 编译的：see on godbolt.
用endian-agnostic code做你的I/O，所以它不会在大端机器上中断。它是一种文件格式，所以实际上您如何访问它并不重要，只要正确的字节位于正确的位置即可。 Little-endian 可能是文件格式的不错选择，因此在 little-endian 机器上 load/store 代码是空操作。或者只是懒惰，在结构数组上执行二进制 I/O，并且只在与训练数据集字节顺序相同的机器上使用你的代码。
如果不使用位板，最好使用 2 位字段数组。随机访问可能很慢，但将其转换为字节数组可能比两个单独的位域更快。屏蔽掉低 2 位，将其用作查找 { POS_EMPTY, POS_O|POS_OCCUPIED, POS_X|POS_OCCUPIED } 的 table 的索引。然后位移两位，使下一个字段进入低位。该板需要 84 位，所以在单独的 32 或 64 位块中进行。不需要进行 128 位双移位。 win/lose/draw 信息可以放在最后的 2 位块中。
将其打包成一个由三个 uint32_t 或一个 uint64_t 和一个 uint32_t 组成的 12 字节结构。或者只是一个 uint8_t 的数组，但这样就更难让编译器执行一次广泛的加载。您可以将内容打包到一个 11 字节的结构中，但是这样对齐就更成问题了。如果节省 1/12 的内存大小会对缓存产生有用的影响，那就去做吧。跨高速缓存行的加载在 x86 CPUs 上只会花费几个额外的周期，而且您不会经常加载。 （无论如何，第一个块的 64 位加载不会与 64b 对齐，具有 12B 结构，但它至少会在中间分裂，这是一种特殊情况，比某些 CPUs.)
我认为将单独的位板解码为字节数组需要分别移动每个位板。它仍然可以是无分支的，但没有那么好。
游戏数据库的内存存储
表示之间的转换需要 CPU 时间，所以如果没有用，就从文件格式转换为内部格式。
如果您保留文本文件格式并使用非紧凑的快速格式，那么为此设置单独的格式可能才有用。在这种情况下，将文件解析为压缩的 2 位位置（如该文件格式，见上文）。
如果您的文件格式是二进制的，请保留它。 （或者甚至只是内存映射文件。）
我正在建立一个深度神经网络来玩 connect-4，它必须在非常有限的机器上与其他 AI 机器人竞争（还不知道具体的限制，只是我只有几个核心和少量内存）。因此，我希望以任何可能的方式优化我的训练集。它目前代表董事会上的州：
b 为空白（无片）
x "x" 件礼物
o "o" 件礼物
win 获胜设置
loss 丢失设置
draw 绘制设置
本质上，我正在尝试对其进行映射，以便我的 3 位整数可以代替这些占用大量内存的字符串。我考虑过使用 short，但在 16 位时它比 char 差。我想这样映射它：
000 -> b
001 -> x
010 -> o
011 -> win
100 -> loss
101 -> draw
因为我可以用 space 的 3 位而不是字符来表示这些状态（每个字符 8 位，哎呀！）我想尝试一下。但是我不确定如何在 c.
中实例化这样的变量训练集有 67557 行，每行代表一个 6x7 的棋盘，后面跟着一个 win/loss/draw 子句。因此，每个字符节省 5 位将每行节省 (5*6*7)+(5*1) = 215 位，整体节省 215*67557 = 14524755 位（总共 2.90 MB 中的 1.81 MB，整体减少 62% space）。
如果你使用 bitfields 呢？
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 位。
请记住，包含使用所有可用 space 的位域的结构（例如上面提到的 8 成员结构：8 * 3 == 24; 24 % 8 == 0）更适合您的目的，因为您可以拥有它们的数组，获得位域的好处，并且在此过程中不浪费内存。因此第一个结构是低效的，因为它为每个 S.
顺便说一句：不要尝试使用 &s.x 或 sizeof(s.x)，因为显而易见的原因，它根本不起作用。
如果机器有限并且您必须（按时）竞争，那么您不想对位域范围的整数进行 CPU 繁重的操作。最好是使用本机机器字大小。其次最好是使用字节大小的整数，因为许多机器对字节大小的实体都有高效的操作。
优化速度或内存使用总是一个问题。
您将这里的两个或三个不同的东西混为一谈。
- 训练文件格式
- 解析后训练集的内存存储格式（如果您需要保留解析后的状态以供将来参考）
- 单板状态的解包表示+可选？ W/L/D 标志
这三种格式都可以不同。训练文件可以是文本以便于编辑。当然，即使您的主程序以二进制格式读取训练集，该二进制文件也可能 "compiled" 来自单独工具易于编辑的文本格式。
使用单板位置的内部表示：
这需要快速访问和循环。由于您正在训练神经网络，而不是直接编写 AI，因此您可能不需要太多地使用这种表示。如果除了将每个元素应用于神经网络输入之外不需要做更多的事情，那么使用单独的格式是没有意义的：只需直接从更紧凑的表示形式解压缩到神经网络输入。
但是，如果您必须多次遍历单个棋盘状态，您有一些有趣的选择。正如多人指出的那样， win/loss/draw/undecided 标志应该与棋盘状态分开考虑。所以你会在每个板上有一个标志，而不是在每个板位置存储标志。
bit-board：例如，我读过有关国际象棋引擎（例如 crafty）使用 64 位 unsigned int 来存储所有白色棋子所在位置的信息。您可以将位图按位或运算在一起，找出所有白色块的位置。
位图（一张用于
o，一张用于x）将记录整个状态。 connect-4 板有 6*7 个网格位置，因此每个位图可以是 64 位，但是 32b 太小了。popcount(board.o)告诉你棋盘上有多少 o。assert(o & x == 0)将是一个很好的完整性检查，因为在同一位置永远不会有 o 和 x。在一个结构中使用两个打包的 42b 字段不是一个好主意，因为 load/store 会很慢。即使将它们打包成 48 位字段（因此它们以字节边界结束）也会导致速度变慢 loading/storing。请记住，这是我们的快速格式。我们可以使用打包格式进行长期存储。
像
board[0][0] && board[0][1] && board[0][2] && board[0][3]这样的东西（尽管不是那种语法）在位板上的编译时常量位置非常快。一个按位 AND 只留下那些可能设置的位，然后您可以与掩码进行比较以查看是否设置了 all 这些位。要测试||而不是&&，请省略第二步。您可以针对 o 或 x 位图或o|x进行这些测试以检查任何一种片段。但是，如果您必须在 运行 时间从可变位置构建掩码，则效率不高。要扫描棋盘以确定是否获胜，您可以检查左列，然后对您的掩码进行位移，使其检查下一列。实际上像这样强力检查所有列可能比检查标记的邻居慢，寻找连续 2 个候选者。
如果位图是完全64位的，一些操作可能会更容易，代表一个8x8的板，但你实际上只使用它的左下角的7x6。这样，单独的列位于 64 位整数的单独字节中。将每一列放在一个单独的字节中可能比行更有用，因为找到一列中使用次数最多的位置是您可能想要做的事情。这只是对列的 find first set bit 操作。从位图中提取 8 位块更快（不需要屏蔽）。不过，您可以解压缩 42 位位图以分隔每列的变量。在 x86 上，前 4 个寄存器对于第一个 和第二个 8 位块（AX（RAX 的低位 16）由 AL 和 AH 组成）是字节可寻址的，您（或编译器，但他们可能没那么聪明）可以在 4 个寄存器中存储 7 列，并且仍然能够分别
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 位位域。 It's impossible to use with nice
board[row][col]syntax in C，并且 42*2 位不适合单个寄存器。交错位板没有任何优势，并且使某些事情变得更糟，尤其是。因为整个东西不适合 64 位。 （如果你想在 bitboard 版本中寻找未占用的空间，你在o|x中寻找零位。在这里，你必须检查每一对 2 位，而不是能够使用一个位来适应整个问题到寄存器中。不过，您可以为 shift/mask 表示给定 row/column 的 2 位创建一个宏。它不会生成有效的代码。字节数组：使用这种格式循环检查给定棋盘位置的邻居可能会更快。在位板中，测试
board[i][j] && board[i][j+1]可以通过对板进行位移来完成，这样感兴趣的两位就可以排成一行，然后按位与，然后对该位进行位测试。至少在 x86 上，存在具有小字节偏移的寻址模式，因此给定一个板位置的地址，与另一个板位置可能只需要一条指令。在每个字节中，一位代表x，另一位代表o，如果位置是x 或 o。这允许通过将它们与在一起并检查占用的位来检查多个位置是否都被占用。否则，您必须检查每个网格中是否设置了 x 或 o 位。
// 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 个）。如果您有任何不是赢、输或平局的棋盘位置，请使用另一个字符来标记它。 Space 或 'n'.
只要省略逗号，您的尺码就会减半。您不想解析逗号之类的输入。简单的 运行 长度编码符号（如 xb2o1xb1w）可能会带来更多收益。看到一个数字意味着重复最后一个字符多次。也许 x 表示一个 x，大写 X 表示两个 x。这已经到了人类难以阅读的地步。 LZOP 或 LZ4 压缩可能可以很好地压缩东西。
二进制文件格式:
显然文本表示是有限制的。固定大小的二进制记录可以非常小，因为要存储的信息不多。每个网格位置使用 2 位可能足够紧凑，但仍然存在冗余，因为它可以表示同一位置的 x 和 o 的不可能状态.为了做得更好，您需要将整个板或整行或整列的状态映射到多位表示。 Wikipedia says 0 到 42 块的所有游戏板有 4,531,985,219,092 个合法位置。那刚好超过 2^42。所以 43 位应该足以表示任何有效的板状态，包括所有尚未确定的位置。 IDK 如何将游戏编码为 43 位整数，至少没有任何可用的（即比实际枚举所有可能的游戏并在匹配的游戏处停止更快。）
如果您使用位板作为内部快速表示，将它们以您的文件格式打包存储，因此 o 和 x 板加上 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++ 编译的：see on godbolt.
用endian-agnostic code做你的I/O，所以它不会在大端机器上中断。它是一种文件格式，所以实际上您如何访问它并不重要，只要正确的字节位于正确的位置即可。 Little-endian 可能是文件格式的不错选择，因此在 little-endian 机器上 load/store 代码是空操作。或者只是懒惰，在结构数组上执行二进制 I/O，并且只在与训练数据集字节顺序相同的机器上使用你的代码。
如果不使用位板，最好使用 2 位字段数组。随机访问可能很慢，但将其转换为字节数组可能比两个单独的位域更快。屏蔽掉低 2 位，将其用作查找 { POS_EMPTY, POS_O|POS_OCCUPIED, POS_X|POS_OCCUPIED } 的 table 的索引。然后位移两位，使下一个字段进入低位。该板需要 84 位，所以在单独的 32 或 64 位块中进行。不需要进行 128 位双移位。 win/lose/draw 信息可以放在最后的 2 位块中。
将其打包成一个由三个 uint32_t 或一个 uint64_t 和一个 uint32_t 组成的 12 字节结构。或者只是一个 uint8_t 的数组，但这样就更难让编译器执行一次广泛的加载。您可以将内容打包到一个 11 字节的结构中，但是这样对齐就更成问题了。如果节省 1/12 的内存大小会对缓存产生有用的影响，那就去做吧。跨高速缓存行的加载在 x86 CPUs 上只会花费几个额外的周期，而且您不会经常加载。 （无论如何，第一个块的 64 位加载不会与 64b 对齐，具有 12B 结构，但它至少会在中间分裂，这是一种特殊情况，比某些 CPUs.)
我认为将单独的位板解码为字节数组需要分别移动每个位板。它仍然可以是无分支的，但没有那么好。
游戏数据库的内存存储
表示之间的转换需要 CPU 时间，所以如果没有用，就从文件格式转换为内部格式。
如果您保留文本文件格式并使用非紧凑的快速格式，那么为此设置单独的格式可能才有用。在这种情况下，将文件解析为压缩的 2 位位置（如该文件格式，见上文）。
如果您的文件格式是二进制的，请保留它。 （或者甚至只是内存映射文件。）