如何在 TeX 中实现（低级）数组

Question 1

首先我要说，这可能是我读过的研究最透彻的问题。恭喜。

我将重复使用 David 的一些评论。哈希算法将 csname 作为字节数组（XeTeX 和 LuaTeX 可能存在一些差异，让我专注于 8 位引擎）并计算总和，其中csname[i]*2^(len-i) % prime表示csname[i]csnamei中的第字节，len是字符总数，结果以哈希为模计算prime。然后将控制序列存储或检索到哈希表中的结果位置。如果从未发生过任何哈希冲突，那么存储和检索将变得简单快捷，因为计算哈希非常快（仅加法）。当发生冲突时，TeX 必须检查它在哈希表中找到的命令是否确实是所搜索的 csname：这是通过一次比较一个字符的字符串来完成的，并且比哈希算法稍慢（我认为)。TeX 可能需要比较所有具有相同哈希值的 csname（一旦找到它正在寻找的 csname，它就可以停止）。

当比较恰好不同但具有相同哈希值的字符串时，TeX 会一次检查一个字符，一旦发现差异就会停止比较：长前缀和长后缀之间存在差异。在存在许多哈希冲突的情况下（例如，使用\number），大部分时间都花在比较恰好具有相同哈希值的字符串上。如果此类字符串在早期字符上有所不同（即短前缀），那么它们很快就会被识别为不同。如果它们有很长的公共前缀，那么 TeX 将不得不扫描它们很长时间（直到第一个差异）才能将它们声明为不同。

为什么\number不利于哈希冲突？假设您的数组键是 5 位数字。与的哈希值相比00000，的哈希值abcde（其中a、等代表数字）为16*a+8*b+4*c+2*d+e。例如，具有与plus98765相同的哈希码。这很小。事实上，所有五位数字的哈希码都位于 280 个可能值之间！一个典型的哈希值对应 300 多个 csname，平均而言，TeX 必须测试其中的一半才能找到它想要的那个。0000016*9+8*8+4*7+2*6+5=253

我们如何分散哈希值？只有 280 个不同值的主要原因\number是 Knuth 选择的乘数仅等于 2。当名称或多或少是长度不等的随机字母序列时，这很合理，就像在典型的 TeX 文档中一样（添加一个字符会将整个哈希值乘以 2，因此无论内部结构如何，不同长度的字符串之间发生冲突的可能性都较小）。为了选择我的编码，我决定用替换16*a+8*b+4*c+2*d+e上面的内容16^4 * a + 16^3 * b + 16^2 * c + 16 * d + e。只需在每个十进制数字之间插入三个虚拟字符即可，变成98765。9---8---7---6---5为什么插入三个而不是更多？因为 16 是大于 10 的最小的 2 的幂。选择 8 而不是 16 仍然会导致哈希冲突：和的哈希值0--0--0--0--0仅9--9--9--9--9相隔9*8^4+9*8^3+...+9=42129，因此典型的哈希值将对应两个或三个 csname。

最后一步就是将其转换为代码：

\def\step#1{#1---\step}
\def\endstep#1\step{}
\message{\step 123 \endstep}

这里我使用一种典型的技术来优化循环：定义循环宏来执行您想要的操作并再次调用自身（这里我们想要#1->#1---），然后找出要输入的内容以#1中断循环。这避免了任何测试，因此速度尽可能快，同时支持任意长度的输入。还请注意，我在数字后面加上了破折号（#1---而不是---#1），以便将相关内容放在 csname 的早期。

对于在数字中插入内容的具体应用，我们可能可以做得更好（尚未进行基准测试）：数字不会超过 10 位（实际上 6 位可能是合理的界限，因此删除#6）#9。下面的方法应该有效，并且可能更快

\def\dashes#1#2#3#4#5#6#7#8#9{#1---#2---#3---#4---#5---#6---#7---#8---#9---}
\message{\dashes 123********}

（数字后至少有 8 个星号，以支持 1 到 10 之间的任意长度的数字）。

另一个选项是\romannumeral在每个数字上使用，这样可以减少哈希冲突，因为长度会有所不同。我不知道这样做效果如何。

有一件事是肯定的：<prefix><varying><postfix>长度恒定的 csnames 可以有256*2^(len-1)不同的哈希值（其中len是变化部分的长度），更现实的是10*2^(len-1)只有哈希值。获取10^5不同的哈希值绝对需要 10 个变化字节，或者前缀、变化或后缀部分的长度有所变化。在实际设置中（考虑到密钥编码，因此很难获得超过 10 个不同的前导字节），需要大约 15 个字节的变化材料。我的\step方法使用 20（或 17，取决于是否计算尾随---）。我的\dashes方法可能会使用各种数字，具体取决于它是否针对特定数字长度进行定制。

以下是根据您的用例实现数组的方法。首先，让我们关注可以包含任意标记的数组。

\toks寄存器。如果您在受控环境中定义和使用数组，请使用\toks组中的寄存器。这限制为 32768 个寄存器（我认为 LuaTeX 为 65536 个）。访问速度比 csnames 更快，并且不需要技巧。事实上，如果您的数组以另一种形式在其他地方定义，但您需要在给定位置（在受控代码内）大量访问它，也可以使用此技术。这（是|已经）用于l3sort合并排序。
多种\csname方法。这就是您要做的，并且已在此处详细讨论过。插槽数量没有限制，键可以是数字以外的其他键，但对于数字键，需要一些技巧来避免哈希冲突。此外，您不能同时在内存中拥有许多这样的数组，否则您的哈希表会完全填满。
包含所有内容的单个数组\csname。这基本上就是l3prop本文写作时所做的。映射所有键非常简单且快速（每个元素）。以任意顺序访问单个元素将非常慢，因为每次我们想要访问一个元素时都需要从宏中扩展整个数组。
如果您对给定项目的访问发生在集群中（例如，您想要查看键 1-2000，然后是 1000-3000，然后是 2000-4000），则混合方法可能更好：您可以\toks为此特定目的分配一定范围的寄存器，并偶尔更新存储在此范围内的项目。您还可以将大多数内容存储在单个 csname 中，并仅将一些项目发送到单个 csname 或 toks 寄存器。

另一种类型的数组具有数值，可以是整数、维度等。

各种寄存器的使用方式与\toks上述寄存器相同。一个典型的例子是l3regex，在撰写本文时，它广泛滥用toks、、和寄存器来存储各种信息。不要使用整数寄存器，因为像的东西dim会损坏，但其他东西也会损坏（，...）。当需要从一个寄存器转换为另一个寄存器时，使用维度或跳过或 muskip 寄存器可能会变得混乱：当然，我们也使用拉伸和收缩组件，这会导致-类型构造。skipmuskip\m@ne\maxdimen\number\glueshrink\mutoglue\muskip3\relax
字体的参数给出了一组更实用的数字\fontdimen。实际上，它们的行为就像通常的 C 数组，其大小必须在开始使用之前声明，并且其项是 TeX 尺寸，即大小小于 2^30 的整数。所有分配都是全局的。检索速度与其他寄存器相当，可能稍慢一些。参见我在这个话题上问过一个问题其他一些评论。

当然，前面描述的toks、和csname方法对于数值数据也同样适用，但与相比似乎效率较低\fontdimen，特别是在内存使用方面（每个\fontdimen参数仅使用几个字节的内存，而 csname 则使用许多字节，表示值的标记则使用更多字节）。

关于优化数据结构的类似主题：

与作为标记列表相比，将长字符串存储为 csname 更有效。这在中的某个时候被使用l3fp，将的 10000 个小数存储1/(2pi)为，以便在需要时\159154943091895...传递给。\string
仅包含数字数据且仅需要非扩展访问的树可以作为嵌套框进行存储和操作，例如将数据存储为各种 kern 节点。我前段时间用这个来实现排序算法，但代码比当前的更乱，l3sort而且速度也没有明显加快。我以后会再看看的。也许可以将其重用于文档元素之间的关系。

Answer

首先我要说，这可能是我读过的研究最透彻的问题。恭喜。

我将重复使用 David 的一些评论。哈希算法将 csname 作为字节数组（XeTeX 和 LuaTeX 可能存在一些差异，让我专注于 8 位引擎）并计算总和，其中csname[i]*2^(len-i) % prime表示csname[i]csnamei中的第字节，len是字符总数，结果以哈希为模计算prime。然后将控制序列存储或检索到哈希表中的结果位置。如果从未发生过任何哈希冲突，那么存储和检索将变得简单快捷，因为计算哈希非常快（仅加法）。当发生冲突时，TeX 必须检查它在哈希表中找到的命令是否确实是所搜索的 csname：这是通过一次比较一个字符的字符串来完成的，并且比哈希算法稍慢（我认为)。TeX 可能需要比较所有具有相同哈希值的 csname（一旦找到它正在寻找的 csname，它就可以停止）。

当比较恰好不同但具有相同哈希值的字符串时，TeX 会一次检查一个字符，一旦发现差异就会停止比较：长前缀和长后缀之间存在差异。在存在许多哈希冲突的情况下（例如，使用\number），大部分时间都花在比较恰好具有相同哈希值的字符串上。如果此类字符串在早期字符上有所不同（即短前缀），那么它们很快就会被识别为不同。如果它们有很长的公共前缀，那么 TeX 将不得不扫描它们很长时间（直到第一个差异）才能将它们声明为不同。

为什么\number不利于哈希冲突？假设您的数组键是 5 位数字。与的哈希值相比00000，的哈希值abcde（其中a、等代表数字）为16*a+8*b+4*c+2*d+e。例如，具有与plus98765相同的哈希码。这很小。事实上，所有五位数字的哈希码都位于 280 个可能值之间！一个典型的哈希值对应 300 多个 csname，平均而言，TeX 必须测试其中的一半才能找到它想要的那个。0000016*9+8*8+4*7+2*6+5=253

我们如何分散哈希值？只有 280 个不同值的主要原因\number是 Knuth 选择的乘数仅等于 2。当名称或多或少是长度不等的随机字母序列时，这很合理，就像在典型的 TeX 文档中一样（添加一个字符会将整个哈希值乘以 2，因此无论内部结构如何，不同长度的字符串之间发生冲突的可能性都较小）。为了选择我的编码，我决定用替换16*a+8*b+4*c+2*d+e上面的内容16^4 * a + 16^3 * b + 16^2 * c + 16 * d + e。只需在每个十进制数字之间插入三个虚拟字符即可，变成98765。9---8---7---6---5为什么插入三个而不是更多？因为 16 是大于 10 的最小的 2 的幂。选择 8 而不是 16 仍然会导致哈希冲突：和的哈希值0--0--0--0--0仅9--9--9--9--9相隔9*8^4+9*8^3+...+9=42129，因此典型的哈希值将对应两个或三个 csname。

最后一步就是将其转换为代码：

\def\step#1{#1---\step}
\def\endstep#1\step{}
\message{\step 123 \endstep}

这里我使用一种典型的技术来优化循环：定义循环宏来执行您想要的操作并再次调用自身（这里我们想要#1->#1---），然后找出要输入的内容以#1中断循环。这避免了任何测试，因此速度尽可能快，同时支持任意长度的输入。还请注意，我在数字后面加上了破折号（#1---而不是---#1），以便将相关内容放在 csname 的早期。

对于在数字中插入内容的具体应用，我们可能可以做得更好（尚未进行基准测试）：数字不会超过 10 位（实际上 6 位可能是合理的界限，因此删除#6）#9。下面的方法应该有效，并且可能更快

\def\dashes#1#2#3#4#5#6#7#8#9{#1---#2---#3---#4---#5---#6---#7---#8---#9---}
\message{\dashes 123********}

（数字后至少有 8 个星号，以支持 1 到 10 之间的任意长度的数字）。

另一个选项是\romannumeral在每个数字上使用，这样可以减少哈希冲突，因为长度会有所不同。我不知道这样做效果如何。

有一件事是肯定的：<prefix><varying><postfix>长度恒定的 csnames 可以有256*2^(len-1)不同的哈希值（其中len是变化部分的长度），更现实的是10*2^(len-1)只有哈希值。获取10^5不同的哈希值绝对需要 10 个变化字节，或者前缀、变化或后缀部分的长度有所变化。在实际设置中（考虑到密钥编码，因此很难获得超过 10 个不同的前导字节），需要大约 15 个字节的变化材料。我的\step方法使用 20（或 17，取决于是否计算尾随---）。我的\dashes方法可能会使用各种数字，具体取决于它是否针对特定数字长度进行定制。

以下是根据您的用例实现数组的方法。首先，让我们关注可以包含任意标记的数组。

\toks寄存器。如果您在受控环境中定义和使用数组，请使用\toks组中的寄存器。这限制为 32768 个寄存器（我认为 LuaTeX 为 65536 个）。访问速度比 csnames 更快，并且不需要技巧。事实上，如果您的数组以另一种形式在其他地方定义，但您需要在给定位置（在受控代码内）大量访问它，也可以使用此技术。这（是|已经）用于l3sort合并排序。
多种\csname方法。这就是您要做的，并且已在此处详细讨论过。插槽数量没有限制，键可以是数字以外的其他键，但对于数字键，需要一些技巧来避免哈希冲突。此外，您不能同时在内存中拥有许多这样的数组，否则您的哈希表会完全填满。
包含所有内容的单个数组\csname。这基本上就是l3prop本文写作时所做的。映射所有键非常简单且快速（每个元素）。以任意顺序访问单个元素将非常慢，因为每次我们想要访问一个元素时都需要从宏中扩展整个数组。
如果您对给定项目的访问发生在集群中（例如，您想要查看键 1-2000，然后是 1000-3000，然后是 2000-4000），则混合方法可能更好：您可以\toks为此特定目的分配一定范围的寄存器，并偶尔更新存储在此范围内的项目。您还可以将大多数内容存储在单个 csname 中，并仅将一些项目发送到单个 csname 或 toks 寄存器。

另一种类型的数组具有数值，可以是整数、维度等。

各种寄存器的使用方式与\toks上述寄存器相同。一个典型的例子是l3regex，在撰写本文时，它广泛滥用toks、、和寄存器来存储各种信息。不要使用整数寄存器，因为像的东西dim会损坏，但其他东西也会损坏（，...）。当需要从一个寄存器转换为另一个寄存器时，使用维度或跳过或 muskip 寄存器可能会变得混乱：当然，我们也使用拉伸和收缩组件，这会导致-类型构造。skipmuskip\m@ne\maxdimen\number\glueshrink\mutoglue\muskip3\relax
字体的参数给出了一组更实用的数字\fontdimen。实际上，它们的行为就像通常的 C 数组，其大小必须在开始使用之前声明，并且其项是 TeX 尺寸，即大小小于 2^30 的整数。所有分配都是全局的。检索速度与其他寄存器相当，可能稍慢一些。参见我在这个话题上问过一个问题其他一些评论。

当然，前面描述的toks、和csname方法对于数值数据也同样适用，但与相比似乎效率较低\fontdimen，特别是在内存使用方面（每个\fontdimen参数仅使用几个字节的内存，而 csname 则使用许多字节，表示值的标记则使用更多字节）。

关于优化数据结构的类似主题：

与作为标记列表相比，将长字符串存储为 csname 更有效。这在中的某个时候被使用l3fp，将的 10000 个小数存储1/(2pi)为，以便在需要时\159154943091895...传递给。\string
仅包含数字数据且仅需要非扩展访问的树可以作为嵌套框进行存储和操作，例如将数据存储为各种 kern 节点。我前段时间用这个来实现排序算法，但代码比当前的更乱，l3sort而且速度也没有明显加快。我以后会再看看的。也许可以将其重用于文档元素之间的关系。

Question 2

相应的 TeX 代码是

@<Compute the hash code |h|@>=
h:=buffer[j];
for k:=j+1 to j+l-1 do
  begin h:=h+h+buffer[k];
  while h>=hash_prime do h:=h-hash_prime;
  end

因此基本上每个数字都会映射到某个 2^k mod p。前缀和后缀实际上不会使散列变得更糟，但哈希表的某些特殊结构意味着它们会占用更多空间。

Answer

相应的 TeX 代码是

@<Compute the hash code |h|@>=
h:=buffer[j];
for k:=j+1 to j+l-1 do
  begin h:=h+h+buffer[k];
  while h>=hash_prime do h:=h-hash_prime;
  end

因此基本上每个数字都会映射到某个 2^k mod p。前缀和后缀实际上不会使散列变得更糟，但哈希表的某些特殊结构意味着它们会占用更多空间。

Question 3

关于上述一些评论/答案的一些说明。

即使在 LuaTeX 中，乘数仍然是 2。

从LuaTeX源代码中可以看出。

compute_hash()功能对应于中的第 261 节tex.pdf，例如从id_lookup()功能在哈希表中查找一个条目。

另外，您可以看到长公共前缀仍然会减慢哈希冲突解决的速度。

其他几点。这些与 TeX 数组没有直接关系。

Lua 哈希函数仅使用字符串中的 32 个字符

正如在上面链接的 Lua 5.2 源代码

/*
** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
** compute its hash
*/
#if !defined(LUAI_HASHLIMIT)
#define LUAI_HASHLIMIT          5
#endif

但是，它不是 32 个第一个/最后一个字符，而是均匀分布在整个字符串上的 32 个字符；因此即使有一个较长的公共前缀/后缀，性能也不会下降太多。

基本上，如果您使用 Lua 散列，您就不需要太担心。

显然从 Lua 5.4 开始，这种情况不再存在，所有字节均被使用。

Answer

关于上述一些评论/答案的一些说明。

即使在 LuaTeX 中，乘数仍然是 2。

从LuaTeX源代码中可以看出。

compute_hash()功能对应于中的第 261 节tex.pdf，例如从id_lookup()功能在哈希表中查找一个条目。

另外，您可以看到长公共前缀仍然会减慢哈希冲突解决的速度。

其他几点。这些与 TeX 数组没有直接关系。

Lua 哈希函数仅使用字符串中的 32 个字符

正如在上面链接的 Lua 5.2 源代码

/*
** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
** compute its hash
*/
#if !defined(LUAI_HASHLIMIT)
#define LUAI_HASHLIMIT          5
#endif

但是，它不是 32 个第一个/最后一个字符，而是均匀分布在整个字符串上的 32 个字符；因此即使有一个较长的公共前缀/后缀，性能也不会下降太多。

基本上，如果您使用 Lua 散列，您就不需要太担心。

显然从 Lua 5.4 开始，这种情况不再存在，所有字节均被使用。

如何在 TeX 中实现（低级）数组

我目前所知道的

测试原始哈希性能

发动机比较

一切都变慢了吗？

我们甚至还没有讨论数组……

还有其他方法吗？

最后的问题

答案1

答案2

答案3

相关内容