来源https://root-11.codeberg.page/intro-book-python/5 — 身份是一个整数给一个 Python 程序员五十二张牌告诉他们编写能洗牌、排序和发牌的代码。问问需要多长时间。大多数人会开始设计类。“官方”Python 教程路径会导向这里定义带有__init__(self, suit, rank)的class Card然后是持有一个list[Card]的class Deck然后是class Hand然后可能是class Player和class Game。等到类型提示正确并且__repr__方法打印得漂亮时一个晚上已经过去了。关于Hand应该包含Card实例还是持有对共享Deck的引用Deck.shuffle()应该改变自身还是返回一个新牌堆Card是否应该为了可哈希性而成为dataclass(frozenTrue)等问题都会引发争论。这些争论都没有错但它们都是与牌本身无关的工作。整个问题可以用三行 numpy 代码解决。解决的方式就是本节要讲的道理。一副牌包含每张牌的三条信息它的花色♠ ♥ ♦ ♣、它的点数A 2 … K以及它当前的位置在牌堆中、在某人手中、在弃牌堆中。这就是三列。牌堆本身有五十二行。importnumpyasnp suitsnp.zeros(52,dtypenp.uint8)# 0..3ranksnp.zeros(52,dtypenp.uint8)# 0..12locationsnp.zeros(52,dtypenp.uint8)# 0牌堆, 1..N手牌, 255弃牌这就是牌堆。整个结构只有156 字节——三个连续的列每列 52 个无符号字节。没有Card类。没有Deck类。索引为17的牌它的花色在suits[17]点数在ranks[17]当前位置在locations[17]。这张牌就是这个索引。用一副崭新的、有序的牌填充这些列每列只需要一次赋值suits[:]np.repeat(np.arange(4,dtypenp.uint8),13)ranks[:]np.tile(np.arange(13,dtypenp.uint8),4)locations[:]0将第 17 张牌发给玩家 1 就是一次元素写入locations[17]1询问玩家 1 的手牌里有什么也是一个 numpy 原语handnp.where(locations1)[0]hand是一个指向牌堆索引的 numpy 数组——一个牌身份标识的列表——而不是任何牌数据的副本。询问每个位置有多少张牌同样是一个原语countsnp.bincount(locations,minlength2)# counts[0] 牌堆, counts[1] 玩家 1, ...洗牌——学生们认为会很困难的操作——就是对索引顺序的洗牌。0..52变成了[7, 32, 1, 19, ...]然后你按这个顺序读取牌ordernp.random.permutation(52)看看刚刚发生了什么。牌本身没有任何变化。suits[17]、ranks[17]和locations[17]的值和之前完全一样。洗牌移动的是索引而不是数据。排序的工作方式相同。要按花色然后按点数排序你可以按(suits[i], ranks[i])对索引进行排序ordernp.lexsort((ranks,suits))# 最后一个键是主键先按花色排序再按点数排序牌没有移动。它们的标识符被重新排序了。这就是大约十五行 Python 代码中的一副牌。它包含了洗牌、排序、发牌和几种查询。这不是一种风格上的捷径它就是一副牌本来的样子。基于类层次结构的版本需要一晚上的工作那是把牌当作拥有其花色和点数的对象来假装的代价而实际上一张牌就是一个数字——一个索引——而其花色和点数是存储在该索引处数组中的值。我们称此为身份即整数这是本书后续为你带来所有收益的前提条件。持久化之所以有效是因为表很容易序列化——三次np.save调用。并行化之所以有效是因为索引很容易分区。回放之所以有效是因为一副牌就是一个状态中的三个数组。如果你使用class Card这些都不会有效。甚至哪个整数也很重要并非每个整数在性能上都是相同的整数。根据code/measurement/float_or_int_tuple.py在一个包含 10,000 条记录的 Pythondict中查找键键的形状查找次数 / 秒(int, int)42,800,637(int, int, int)39,625,273(float, float)26,461,898(float, float, int)26,115,850(float, float, float)17,630,435一个两个整数的元组哈希和比较的速度是三个浮点数元组的2.4 倍。身份即整数不仅仅是“使用一个数字”它是“使用一个小型无符号整数理想情况下放在一个连续的类型化数组中”。一个np.uint8索引在一个缓存行中可以容纳 64 个并且可以用一个 CPU 指令进行哈希。一个(float, float, float)“身份”——Python 教程可能建议用于字典中 3D 点的那种——需要付出三倍的代价更多的字节更慢的哈希更慢的比较。上面的牌堆列有意识地使用了np.uint80…255 覆盖了一切4 种花色13 种点数最多 254 个位置每个值一个字节每个缓存行 64 张牌。来自 §2 的宽度预算与来自 §5 的身份选择相遇np.uint8列是最廉价的身份最廉价的存储以及最廉价的查找所有这些都集中在一个决策中。[!NOTE]强形式我们稍后会再回来讨论有时你甚至不需要索引。对于一副扑克牌(suit, rank)对已经唯一地标识了一张牌——只有五十二种这样的对。索引是一个代理键这个对是一个自然键。对于数量可变的表来来去去的生物你通常需要一个代理键因为两个生物可能是相同的。对于数量恒定的 52 张牌的牌堆你不需要。全书都使用代理键因为模拟器是数量可变的但知道何时可以省略索引本身也是一门学问。练习第一次练习时在deck.py中从头开始编写所有内容。抵制添加Card类或辅助方法的冲动。就三个 numpy 数组。构建牌堆。编写def new_deck() - tuple[np.ndarray np.ndarray np.ndarray]返回一副崭新的、有序的牌堆的花色、点数和位置所有 52 张都在location 0 牌堆中。所有三个数组的类型都是dtypenp.uint8。打印一张牌。编写def card_to_string(suit: int, rank: int) - str返回像A♠、10♥、K♦这样的字符串。用它来打印整副牌。洗牌。使用np.random.default_rng(seed).permutation(52)产生一个洗牌后的顺序。按洗牌后的顺序打印牌堆。通过检查确认suits、ranks和locations数组没有改变。按花色然后点数排序。使用np.lexsort((ranks, suits))产生一个order使得花色分组输出每种花色内点数升序。再次打印。同样牌堆数组没有改变。发一手牌。将前 5 张牌从牌堆位置 0移动到玩家 1位置 1。使用card_to_string打印玩家 1 的手牌。手牌查询。编写def cards_held_by(locations: np.ndarray player: int) - np.ndarray返回给定玩家当前持有的所有牌索引。函数体只有一行。按位置计数。编写一个使用np.bincount返回按位置分组计数的函数。确认counts[0] counts[1:].sum() 52。发四手牌。向玩家 1、2、3、4 各发 5 张牌。打印所有四手牌。挑战移除索引。重写cards_held_by使其直接返回一个(N, 2)的 numpy 数组包含(suit, rank)对——不返回索引。这会让什么变得更容易又会带来什么困难提示如果不知道它们原来的i你就无法将牌移回牌堆。挑战排序的危害。当玩家 1 持有索引[3 17, 21, 28, 41]时就地按花色对牌堆数组本身进行排序order np.argsort(suits); suits[:] suits[order]; ranks[:] ranks[order]; locations[:] locations[order]。现在玩家 1 认为他们持有的是什么排序后打印索引[3 17, 21, 28, 41]处的牌。这就是 §9 — 排序会破坏索引 要解决的问题。现在先不要修复它——只观察它。练习 1-3 的参考答案见 05_identity_is_an_integer_solutions.md。其余练习的解决方案遵循相同的模式。接下来是什么练习 10 给你留下了一个错误。接下来的几节将构建防止该错误的规范§6 — 一行是一个元组 是下一个词汇课而 §9 — 排序会破坏索引 是修复方法——保持一个稳定的 ID 与位置并列以便外部引用能够幸存的重新排序。6 — 一行是一个元组在 §5 中你将一副 52 张牌构建为三个 numpy 列。索引 17 处的牌是三元组(suits[17], ranks[17], locations[17])。这三个值一起构成了这一行。没有Card类。甚至没有一个元组对象——这一行隐式地存在于对齐关系中相同的索引在每一列中使用可以恢复关于一张牌的所有数据。这就是我们在本书其余部分所说的行——一组属于同一实体的连贯值。在creature表中一行是(pos[i], vel[i], energy[i], birth_t[i], id[i], gen[i])。在food表中一行是(pos[i], value[i], id[i])。这些字段由于共享相同的索引i而属于同一实体。没有dataclass持有它们没有NamedTuple实例没有dict。只有这样的规范无论你使用哪个索引i来读取一列你也必须使用同一个索引来读取同一张表的所有其他列。为什么“隐式”在 Python 中很重要当 Python 的教程看到行这个词时第一反应是使用类——dataclass class Row或class Row(NamedTuple)或者如果提到性能则使用class Row: __slots__ (...)。这些构造中的每一个都将行构建为一个对象带有头部、引用计数和字段指针。它们都不是免费的。根据code/measurement/classes_or_tuples.py在这台机器上构建 1,000,000 个两字段“行”的时间按速度从快到慢排列行的构建方式1M 行的时间numpy SoA — 两个np.full(N, value)列批量0.005 秒(x, y)— 裸元组1M 次单独构建0.007 秒带有__slots__的class0.109 秒collections.namedtuple(...)0.146 秒typing.NamedTuple子类0.151 秒dataclass(frozenTrue, slotsTrue)0.164 秒对这个表有两种解读。第一种解读对于每行的构建裸元组比带槽的类快约16 倍比 frozenslots 的 dataclass 快约23 倍。命名的替代方案都需要支付对象头和每字段描述符查找的成本而元组则不需要。根据code/measurement/simple_namespace.py即使是一个dict{x: 10.0, y: 20.0}的构建速度也比任何命名类的选项都要快——对于同样的一百万行大约为 0.036 秒。命名这一行就是成本元组是仍然可识别为行的最廉价的行。第二种解读——也是本书关心的一种——是顶行两次批量 numpy 列分配构建 1,000,000 行的数据比一百万个单独的元组字面量更快。批量分配大约比命名的替代方案快 30 倍并且甚至不比最廉价的逐行选项慢。允许你这样做的方式——预先分配一个列一次用值填充它并将行i视为隐式元组(col0[i], col1[i], ...)——根本没有每行构建的成本。索引i处的元组只有在你显式请求时才存在在此之前它作为连续的字节存在于 numpy 列内部。从 §3 的占用示例来看一百万行十字段的行作为 numpy SoA 列占用 99 MB作为元组列表占用 437 MB——并且 SoA 版本在此之上支付零每行构建成本因为没有行对象。一行是一个元组但在 Python 中这个说法最有用的版本是一行是你不需要构建的元组。对齐是规范隐式绑定的成本在于你必须保持索引对齐。如果你对suits进行了排序而没有同时对ranks和locations进行排序那么每个索引处的行都将被破坏——牌堆仍然在 52 个槽位中有 52 个条目但每个槽位现在包含一张牌的花色、另一张牌的点数、第三张牌的位置。这不是一个假设性的错误你在 §5 练习 10 中故意制造了它而 §9 将给你结构性的修复方法。规则很简单对表的任何列进行重新排序的每个操作都必须一起对该表的所有列进行重新排序。使对齐可维护的规范是每列单一写入者。如果只有一个函数写入locations并且该函数一致地写入那么对齐就永远不会被违反。多个写入者写入同一列会相互竞争并产生不一致的行。这就是 §25表的所有权 所强制执行的每个表正好有一个写入者而一行是一个元组正是因为那个单一写入者使其所有列保持同步。一行是一个元组——由相同实体索引的列组装而成通过规范而非任何将它们结合在一起的容器来保持对齐。练习这些练习扩展了你在 §5 中的deck.py。打印第 17 行。编写def row(suits, ranks, locations, i)返回(int(suits[i]), int(ranks[i]), int(locations[i]))。用它来打印第 17 张牌的花色、点数和位置。错误地处理对齐。仅就地排序suitssuits.sort()。再次打印第 17 行。现在这些值来自三张不同的牌——这正是那个 bug。步调一致的排序。重置牌堆。现在使用一个顺序数组一起对所有三列进行排序order np.argsort(suits); suits[:] suits[order]; ranks[:] ranks[order]; locations[:] locations[order]。再次打印第 17 行。这些值来自一张牌。[:]很重要——它是一个就地赋值保持相同的底层数组suits suits[order]会将名称重新绑定到一个新数组并破坏其他地方持有的别名。添加第四列。添加dealt_at np.full(52, 255, dtypenp.uint8)当一张牌在滴答t时被发出将t写入dealt_at[i]哨兵值 255 表示“尚未发出”。修改你的步调一致的排序也对此列重新排序。通过抽查验证一行在排序后仍然一致。单一写入者规则。编写def reorder_deck(suits, ranks, locations, dealt_at, order)。此函数应该是唯一一个对牌堆的任何列进行重新排序的函数。在函数的文档字符串中记录该契约。重构你的洗牌和排序函数以调用它。在你机器上的构建成本。在你的机器上运行uv run code/measurement/classes_or_tuples.py。注意其比率。确认带槽的 dataclass 行现代 Python 中规范的“正确”答案在构建时是命名选项中最慢的。挑战当对齐不重要时。一个仅使用(suits[i], ranks[i])来识别牌的查询——例如“这是黑桃 A 吗”——不依赖于locations或dealt_at。编写这样一个查询一行使用np.where。来自 §5 强形式的自然键视图意味着此查询在无关列重新排序后仍然有效只有suits和ranks需要彼此对齐。接下来是什么§7 — 数组结构 为你一直在隐式做出的布局选择命名每个字段一个列。下一节将为其辩护以对抗其替代方案。