如何在 TeX 中实现(低级)数组

如何在 TeX 中实现(低级)数组

更新:我已经根据以下情况修改了我的问题Bruno Le Floch 的评论以及一些进一步的研究。


有些人可能知道,我正在实现一个巨大的 TeX 宏包,它必须进行大量的内部计算,因此“每页”的整体性能会比通常的 LaTeX 文档低很多。

为了快速提高性能,我目前正在研究在 TeX 中执行一些非常基本的计算的最高效方法。

我经常使用的类数组大量值存储在主存储器中的结构,可通过一个或多个数字键访问。

所以我的问题基本上是:

在 TeX 中实现一维或多维数组的最佳方法是什么,专注于数字访问键?

我目前所知道的

目前,要用键存储<value>在数组中,我基本上是这样做<myarray><key>

\expandafter\def\csname<myarray>@<key>@DocScape\endcsname{<value>}

(假设<key>是可以放入 cs 名称中的形式)。

当然,这并不能提供真正的随机访问、紧凑的数组结构,而是使用内部哈希表,希望在插入新数组元素时获得良好的性能,并且“几乎”欧拉(1)访问以检索数组元素。

此外,我无法想象有任何其他方法可以获得与 TeX 实现相当的性能。

因此,目前我正在研究提高这项基本技术性能的方法。

测试原始哈希性能

我已经多次听说 TeXs 的 cs 名称哈希算法不太好,因此一个性能问题可能是产生大量哈希冲突,从而导致性能比欧拉(1),但我没有查看资料来源,所以我不知道它到底有什么坏处。此外,我在这个网站上没有找到有关此主题的任何精确信息。

如果哈希性能很差,我可以想象以下因素可能会影响数组构造的整体性能:

  1. cs 名称的总长度
  2. “有效部分” (即 的编码<key>) 之前的“常量”前缀的长度。
  3. 方式<key>是经过编码的。

为了测试以何种形式构造数组元素的 cs 名称可提供最佳性能,我制作了以下测试套件:

\input random

% Three different implementations of a "hash array" with numerical
% keys using different key encodings.

\input numhasharray.tex

\input hashnumhasharray.tex

\input codenumhasharray.tex

\newcount\iter
\newcount\rcount
\def\gobble#1{}



% A macro for setting up one experiment to test the "raw hash performance".

\def\mkhashexperiment#1#2#3#4#5%
{%
  \iter0

  \immediate\openout2=#1-setup.tex

  \immediate\write2{\noexpand\message{starting test "#1"; size #2; prefix "#3";}}
  \immediate\write2{\noexpand\message{postfix "#4"; coding \string\string\string#5}}%

  \loop
   \ifnum\iter<#2
    \advance\iter1
    \immediate\write2
    {%
      \noexpand\expandafter\noexpand\def
      \noexpand\csname#3#5\iter#4\noexpand\endcsname{\number\iter}%
    }%
  \repeat

  \immediate\closeout2 %

  \iter0

  \immediate\openout2=#1.tex

  \immediate\write2{\expandafter\gobble\string\\input\space#1-setup}%

  \immediate\write2{\expandafter\gobble\string\\newcount\string\mycount}%
  \loop
   \ifnum\iter<#20
    \advance\iter1
    \setrannum{\rcount}{1}{#2}
    \immediate\write2
    {%
      % What is the most performant way to "just retrieve" the array
      % value without causing any further computation cost?
      \noexpand\mycount
      \noexpand\csname#3#5\rcount#4\noexpand\endcsname\relax
    }%
  \repeat

  \immediate\write2{\expandafter\gobble\string\\bye}%
  \immediate\closeout2 %

  \immediate\write1{time tex #1;}
}


% A macro for setting up one experiment to test the performance of an
% array implementation.

\def\mkarrayexperiment#1#2#3#4#5%
{%
  \iter0

  \immediate\openout2=#1-setup.tex

  \immediate\write2{\noexpand\message{starting test "#1"; size #2;
  array implementation "#3"}}%

  \immediate\write2{\expandafter\gobble\string\\input\space#3}%

  \loop
   \ifnum\iter<#2
    \advance\iter1
    \immediate\write2
    {%
      \string#4{foo}{\number\iter}{\number\iter}%
    }%
  \repeat

  \immediate\closeout2 %

  \iter0

  \immediate\openout2=#1.tex

  \immediate\write2{\expandafter\gobble\string\\input\space#3}%

  \immediate\write2{\expandafter\gobble\string\\input\space#1-setup}%

  \immediate\write2{\expandafter\gobble\string\\newcount\string\mycount}%
  \loop
   \ifnum\iter<#20
    \advance\iter1
    \setrannum{\rcount}{1}{#2}
    \immediate\write2
    {%
      % What is the most performant way to "just retrieve" the array
      % value without causing any further computation cost?
      \noexpand\mycount\string#5{foo}{\number\rcount}\relax
    }%
  \repeat

  \immediate\write2{\expandafter\gobble\string\\bye}%
  \immediate\closeout2 %

  \immediate\write1{time tex #1;}
}


% Number of array entries to generate; 10x this number of random retrievals
% is generated.

\def\experimentsize{100000}

% Execute this sh script to run the tests.

\immediate\openout1=testhash.sh

\immediate\write1{(}


% Testing the performance of the internal hash table.

% The usual way of implementing an array: Just put the access key in
% the name directly as a \number. 

\mkhashexperiment{testhash1}{\experimentsize}{pre}{}{\number}
\mkhashexperiment{testhash2}{\experimentsize}{}{post}{\number}
\mkhashexperiment{testhash3}{\experimentsize}{verylongprefixtostresshashtable}{}{\number}
\mkhashexperiment{testhash4}{\experimentsize}{}{verylongprefixtostresshashtable}{\number}
\mkhashexperiment{testhash5}{\experimentsize}{verylong}{prefixtostresshashtable}{\number}
\mkhashexperiment{testhash6}{\experimentsize}{verylongprefixto}{stresshashtable}{\number}


% Encoding provided by Bruno le Floch to optimise number hashing.

\mkhashexperiment{testhash19}{\experimentsize}{pre}{}{\hashnumber}
\mkhashexperiment{testhash20}{\experimentsize}{}{post}{\hashnumber}
\mkhashexperiment{testhash21}{\experimentsize}{verylongprefixtostresshashtable}{}{\hashnumber}
\mkhashexperiment{testhash22}{\experimentsize}{}{verylongprefixtostresshashtable}{\hashnumber}
\mkhashexperiment{testhash23}{\experimentsize}{verylong}{prefixtostresshashtable}{\hashnumber}
\mkhashexperiment{testhash24}{\experimentsize}{verylongprefixto}{stresshashtable}{\hashnumber}


% Best performance I found so far.

\mkhashexperiment{testhash25}{\experimentsize}{pre}{}{\mynumcode}
\mkhashexperiment{testhash26}{\experimentsize}{}{post}{\mynumcode}
\mkhashexperiment{testhash27}{\experimentsize}{verylongprefixtostresshashtable}{}{\mynumcode}
\mkhashexperiment{testhash28}{\experimentsize}{}{verylongprefixtostresshashtable}{\mynumcode}
\mkhashexperiment{testhash29}{\experimentsize}{verylong}{prefixtostresshashtable}{\mynumcode}
\mkhashexperiment{testhash30}{\experimentsize}{verylongprefixto}{stresshashtable}{\mynumcode}


% Testing the performance of different array implementations.

% Hash array with simple numerical keys.

\mkarrayexperiment{testnumhasharray}{\experimentsize}{numhasharray}{\numhashstore}{\numhashretrieve}

% Hash array with encoding provided by Bruno le Floch to optimise
% number hashing. 

\mkarrayexperiment{testhashnumhasharray}{\experimentsize}{hashnumhasharray}{\hashnumhashstore}{\hashnumhashretrieve}

% Hash array with "hash spread" encoding.

\mkarrayexperiment{testcodenumhasharray}{\experimentsize}{codenumhasharray}{\codenumhashstore}{\codenumhashretrieve}


\immediate\write1{) \string&> testhash.log}

\immediate\closeout1 %

\bye

为了生成测试,您需要针对不同的基于哈希的数组变体的以下实现文件:

numhasharray.tex

% The most basic "hash array" for numeric keys: 
% just use the number as a key.

\def\numhashstore#1#2#3{\expandafter\def\csname\number#2\string_#1\string_nh\endcsname{#3}}
\def\numhashretrieve#1#2{\csname\number#2\string_#1\string_nh\endcsname}

hashnumhasharray.tex

% This encoding is by Bruno Le Floch, directly constructed to optimise
% hash performance.

\def\step#1{#1---\step}
\def\endstep#1\step{}
\def\hashnumber#1{\expandafter\step \number#1 \endstep}


\def\hashnumhashstore#1#2#3{\expandafter\def\csname\hashnumber{#2}\string_#1\string_hnh\endcsname{#3}}
\def\hashnumhashretrieve#1#2{\csname\hashnumber{#2}\string_#1\string_hnh\endcsname}

codenumhasharray.tex

% My own encoding for numerical keys, hoping to spread out hash
% codes. In particular, I'm trying to get different cs name
% lengths. I'm indepted to Bruno Le Floch for the neat way of ending
% the recursion without an \if construct.

\expandafter\def\csname numkeya0\endcsname{a1Y@}
\expandafter\def\csname numkeya1\endcsname{b}
\expandafter\def\csname numkeya2\endcsname{c2}
\expandafter\def\csname numkeya3\endcsname{dZ}
\expandafter\def\csname numkeya4\endcsname{e3'}
\expandafter\def\csname numkeya5\endcsname{f}
\expandafter\def\csname numkeya6\endcsname{g4!}
\expandafter\def\csname numkeya7\endcsname{h}
\expandafter\def\csname numkeya8\endcsname{i5-}
\expandafter\def\csname numkeya9\endcsname{j"}
\expandafter\def\csname numkeya;\endcsname\myencodeb{}

\expandafter\def\csname numkeyb0\endcsname{k6}
\expandafter\def\csname numkeyb1\endcsname{l;}
\expandafter\def\csname numkeyb2\endcsname{m7/}
\expandafter\def\csname numkeyb3\endcsname{n}
\expandafter\def\csname numkeyb4\endcsname{o8}
\expandafter\def\csname numkeyb5\endcsname{p(:}
\expandafter\def\csname numkeyb6\endcsname{q9}
\expandafter\def\csname numkeyb7\endcsname{r}
\expandafter\def\csname numkeyb8\endcsname{s0(}
\expandafter\def\csname numkeyb9\endcsname{t,}
\expandafter\def\csname numkeyb;\endcsname\myencodec{}

\expandafter\def\csname numkeyc0\endcsname{uO}
\expandafter\def\csname numkeyc1\endcsname{v)}
\expandafter\def\csname numkeyc2\endcsname{wP}
\expandafter\def\csname numkeyc3\endcsname{x<}
\expandafter\def\csname numkeyc4\endcsname{yQ=}
\expandafter\def\csname numkeyc5\endcsname{z}
\expandafter\def\csname numkeyc6\endcsname{AR}
\expandafter\def\csname numkeyc7\endcsname{B?>}
\expandafter\def\csname numkeyc8\endcsname{CS}
\expandafter\def\csname numkeyc9\endcsname{D}
\expandafter\def\csname numkeyc;\endcsname\myencoded{}

\expandafter\def\csname numkeyd0\endcsname{ET[|}
\expandafter\def\csname numkeyd1\endcsname{F}
\expandafter\def\csname numkeyd2\endcsname{GU}
\expandafter\def\csname numkeyd3\endcsname{H]}
\expandafter\def\csname numkeyd4\endcsname{IV}
\expandafter\def\csname numkeyd5\endcsname{J}
\expandafter\def\csname numkeyd6\endcsname{KW*}
\expandafter\def\csname numkeyd7\endcsname{L}
\expandafter\def\csname numkeyd8\endcsname{MX}
\expandafter\def\csname numkeyd9\endcsname{N+}
\expandafter\def\csname numkeyd;\endcsname\myencodea{}

\def\mynumcode#1{\expandafter\myencodea\number#1;}
\def\myencodea#1{\csname numkeya#1\endcsname\myencodeb}
\def\myencodeb#1{\csname numkeyb#1\endcsname\myencodec}
\def\myencodec#1{\csname numkeyc#1\endcsname\myencoded}
\def\myencoded#1{\csname numkeyd#1\endcsname\myencodea}

\def\codenumhashstore#1#2#3{\expandafter\def\csname\mynumcode{#2}\string_#1\string_cnh\endcsname{#3}}
\def\codenumhashretrieve#1#2{\csname\mynumcode{#2}\string_#1\string_cnh\endcsname}

这将生成几个 TeX 文件和一个 shell 脚本来运行一系列测试,以比较不同 cs 名称构造的性能。

\mkhashexperiment{testhash1}{100000}{pre}{post}{\number}

生成一个 TeX 文件,创建一个具有连续编号条目和随机检索的testhash1.tex数组构造,其中 cs 名称为1000001000000

\csname pre\number<key>post\endcsname

对于和<key>之间的 s 。1100000

将我在笔记本电脑上得到的测试运行时间testhash1与上面的进行比较(引用自):testhash6testhash.log

starting test "testhash1"; size 100000; prefix "pre";
postfix ""; coding \number) )
real    0m4.642s
user    0m4.296s
sys 0m0.068s

starting test "testhash2"; size 100000; prefix "";
postfix "post"; coding \number) )
real    0m3.827s
user    0m3.748s
sys 0m0.036s

starting test "testhash3"; size 100000; prefix "verylongprefixtostresshashtable
"; postfix ""; coding \number) )
real    0m16.614s
user    0m16.265s
sys 0m0.160s

starting test "testhash4"; size 100000; prefix "";
postfix "verylongprefixtostresshashtable"; coding \number) )
real    0m6.317s
user    0m6.176s
sys 0m0.072s

starting test "testhash5"; size 100000; prefix "verylong";
postfix "prefixtostresshashtable"; coding \number) )
real    0m8.971s
user    0m8.789s
sys 0m0.116s

starting test "testhash6"; size 100000; prefix "verylongprefixto";
postfix "stresshashtable"; coding \number) )
real    0m13.337s
user    0m12.753s
sys 0m0.112s

(请注意,这些是我的笔记本电脑上的简单系统计时结果,因此它们可能因系统上的其他进程而略有偏差。但这些数字在重复时基本上是可重现的。)

第一个(也许令人惊讶的)结果是,单是这种程度的变化就会导致整体表现出现巨大差异,差异高达4在运行时间上。如果可以忽略固定数量的额外处理(我使用计数器分配来访问数组值),差异可能会大得多!

现在我听说哈希性能对于数字序列特别差,因此\number对数组访问键进行编码可能不是一个好主意。

Bruno Le Floch 发表了评论其中他描述了如何优化散列的数字表示。这在宏中实现\hashnumber并通过测试用例进行测试。testhash19结果testhash24

starting test "testhash19"; size 100000; prefix "pre";
postfix ""; coding \hashnumber) )
real    0m2.395s
user    0m2.280s
sys 0m0.052s

starting test "testhash20"; size 100000; prefix "";
postfix "post"; coding \hashnumber) )
real    0m2.483s
user    0m2.260s
sys 0m0.048s

starting test "testhash21"; size 100000; prefix "verylongprefixtostresshashtabl
e"; postfix ""; coding \hashnumber) )
real    0m4.173s
user    0m3.740s
sys 0m0.056s

[剪辑]

这比使用以下方法得到的结果好得多\number

  • 最好的表现几乎是\number(所以8比最糟糕的情况要好几倍\number)。
  • 不同 cs 名称构造之间的性能“扩展”几乎可以忽略不计;即使最差的表现也\hashnumber比最好的表现要好\number

当然,我很好奇通过选择更聪明的编码可以在多大程度上增强这一点,但我不知道如何系统地做到这一点。

为了将编码数字的哈希键“分散”一点,我自己制作了一个编码函数(\mynumcode;参见上面的测试套件)。它将使用大量不同的字符,产生不同的密钥长度并避免重复,希望这能更好地分配哈希键。

使用这种编码,我得到以下运行时间:

starting test "testhash25"; size 100000; prefix "pre";
postfix ""; coding \mynumcode) )
real    0m2.194s
user    0m1.920s
sys 0m0.016s

starting test "testhash26"; size 100000; prefix "";
postfix "post"; coding \mynumcode) )
real    0m2.089s
user    0m2.020s
sys 0m0.040s

starting test "testhash27"; size 100000; prefix "verylongprefixtostresshashtabl
e"; postfix ""; coding \mynumcode) )
real    0m3.594s
user    0m3.008s
sys 0m0.036s

[剪辑]

您会发现,时间结果比 略好\hashnumber,但好得并不明显。因此,这可能已经接近最优值(对于 TeX 引擎的哈希实现而言)。

由于上面报告的测试尽可能接近测试哈希机制的“原始性能”(仅存储和检索值;不加载任何额外的宏并避免所有计算),我敢得出以下结论:

  1. 总体而言,将数组元素存储为具有构造的 cs 名称的单独宏是可行的。与 TeX 文档的通常运行时间相比,存储 100000 个数组元素并检索随机元素 1000000 次的最佳给定“原始”时间是可以接受的,并且可能与 TeX 系统在实际应用中进一步处理这 1000000 个值的方式相比相形见绌。
  2. 确实,使用\number对数字键进行编码对于数组性能来说并不是最佳的。
  3. Bruno Le Floch 给出的实现“哈希优化”数字编码的解决方案可确保以较小的计算成本实现更佳的哈希性能(另见下文)。
  4. cs 名称的总长度似乎并不重要。
  5. 当使用时\number,令人费解的是,数组实现的整体性能几乎与数组访问键前面的“静态”前缀成反比(对于任何其他数字编码来说,情况就大得多)。

发动机比较

上面引用的测试结果来自原始 TeX 引擎。我还用其他引擎运行了上面显示的测试套件。

  • pdftex总体而言,性能略有下降,但影响并不大。
  • xetex总体而言,性能略有下降,看起来更加显著(最多1.5慢几倍)。

性能上的luatex差异更加微妙:使用 TeX 运行速度很快的情况有时会慢得多(最多2倍慢),而 TeX 速度慢的情况正在变得越来越快,因此似乎 LuaTeX 更擅长处理原始引擎不好的情况(长静态前缀)。

一切都变慢了吗?

关于使用内部哈希表来存储数千个 cs 名称的数组,还有一个问题是,它会降低速度全部处理由于

  1. 事实上,对于非常大量的数据,哈希表的大小必须扩展,因此查找任何cs 名称将花费更多时间;
  2. 事实上,生成的 cs 名称“扰乱”了哈希表,从而导致常规宏名称的哈希冲突。

我通过生成上述测试套件\def\experimentsize{1000000}并使用以下测试文件进行了测试:

\documentclass{article}

%\input{testhash1-setup}
%\input{testhash25-setup}

\usepackage{pgfplots}


\let\rmdefault\sfdefault

\begin{document}

\newcommand\test[1]
{%
[can't repeat the example code here because of post length limit]
}

\test{1}

\test{2}

\test{3}

\test{4}

\test{5}

\test{6}

\end{document}

XKCD 图示例取自这个答案。使用 TikZ 示例的目的是 TikZ 加载了大量的源代码,定义并使用了大量的宏,因此如果正常宏处理的哈希性能出现任何问题,那么这是一个应该最容易观察到的应用程序。

请注意,\input语句(上面注释掉的)是before在加载时执行的pgfplots,以最大限度地增加加载 TikZ 时的潜在哈希冲突。

我必须按如下方式扩展内部表,以便编译示例文件并\input取消注释其中一个语句:

export hash_extra=1500000
export max_strings=2000000
export pool_size=30000000

首先,我们来看看更大的哈希表的效果。如果我编译示例\input注释掉这两个语句不使用time pdflatex任何扩展,我得到以下结果:

real    0m3.686s
user    0m3.628s
sys 0m0.044s

有了上述扩展,我得到

real    0m3.746s
user    0m3.684s
sys 0m0.052s

我想说这是一个明显的(也是可重现的)减速,但对于实际目的来说完全无关紧要。

现在,取消注释的计时结果为\input{testhash1-setup}

real    0m19.760s
user    0m19.585s
sys 0m0.140s

\input{testhash25-setup}取消注释:

real    0m10.710s
user    0m10.585s
sys 0m0.104s

以下是仅处理testhash1-setup以下测试文件的计时结果:

\documentclass{article}

\input{testhash1-setup}

\begin{document}
\end{document}

(请注意,由于启动两次 LaTeX,会产生少量开销。)

real    0m15.401s
user    0m15.297s
sys 0m0.084s

对于testhash25-setup

real    0m4.218s
user    0m4.104s
sys 0m0.104s

将单独计算的运行时间相加并与联合计算进行比较,我得到

  • 对于,两个“单独”的计算时间(计时)testhash1-setup的总和为usr18.981秒,而联合计算需要19.585 秒
  • 对于testhash25-setup,两个“单独”计算时间的总和为7.788秒,而联合计算需要10.585秒

有趣的是,这意味着当数组键用 编码时\number,以下计算不会明显减慢,而当使用我更快的编码方法时,速度减慢与 TikZ 示例的原始运行时间大致相同

因此,这个例子实际上可以观察到哈希表混乱的影响:当我的编码尝试将数组元素的哈希码分散到整个哈希表中时,常规宏名称的哈希冲突数量会增加,事实上性能减半

Bruno Le Floch 的编码结果具有可比性。

但请注意,实验设置实际上不太现实,因为加载数组代码TikZ 归结为在定义实际的文档宏之前设置数据结构,而通常情况是相反的:首先,加载宏包等,然后在文档处理过程中,将数据存储在动态定义的数组中。

那么当我移动\input{testhash25-setup} \usepackage{pgfplots}

real    0m8.928s
user    0m8.809s
sys 0m0.100s

因此,速度减慢的情况仍然很明显,但比反过来执行时要小得多。

因此,我从这些实验中得出的结论是:

  1. 单独扩展内部哈希表不会减慢 TeX 的速度。
  2. 用数组元素的宏来扰乱哈希表明显减慢 TeX 的速度。
  3. 定义宏时会有所不同;基本包应该先出现,而数组元素的定义应该尽可能晚出现。
  4. 在决定如何编码数组索引时,应考虑所有影响。用稍微好一点的哈希性能换取整体运行时间大幅减慢是没有意义的。

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

事实上,到目前为止,所有测试都处于“原始哈希”级别,仅执行预扩展的存储和检索命令。在实际的应用程序设置中,数组键的编码当然必须在执行时进行。

这就是上述测试套件中宏的目的\mkarrayexperiment:它将生成一个包含类似语句的测试文件

\numhashstore{foo}{1}{1}
\mycount \numhashretrieve{foo}{438549}\relax 

foo使用上面定义的访问宏来存储和检索数组中的值。

从给定的测试套件中,我得到以下结果:

starting test "testnumhasharray"; size 100000; array implementation "numhasharr
ay" (./numhasharray.tex)) )
real    0m5.472s
user    0m5.192s
sys 0m0.048s

starting test "testhashnumhasharray"; size 100000; array implementation "hashnu
mhasharray" (./hashnumhasharray.tex)) )
real    0m3.754s
user    0m3.664s
sys 0m0.032s

starting test "testcodenumhasharray"; size 100000; array implementation "codenu
mhasharray" (./codenumhasharray.tex)) )
real    0m5.114s
user    0m4.868s
sys 0m0.048s

在这里,我们可以看到,对数组键进行编码的工作量缩小了使用方法\number与 Bruno Le Floch 的哈希优化方法之间的差距。我自己的编码不合格,因为生成数组键的工作量超过了增加的哈希效率 :-(

但好消息是,即使考虑到编码所需的时间,Bruno Le Floch 的方法也胜过基于的数组索引\number

还有其他方法吗?

我感兴趣的是,除了这里研究的基于哈希的方法之外,是否还有其他具有可比性能的方法来实现数组。

l3prop软件包提供了“属性列表”的实现,可以像数组一样访问。但是,通过与上述类似的测试,我得到的性能与基于哈希的实现完全无法比拟(对于 1000 个数组条目和 10000 次检索,速度慢 100 倍;对于更大的数组大小,速度甚至可能更差)。因此,这似乎不是存储大量数据的替代方案。

我试图设计一个简单的基于宏的解决方案,其中所有条目都存储在一个宏扩展中,但不幸的是我想不出任何方法来以任何效率检索数组条目的值(我认为可以使用分隔参数来实现这一点,但不知道如何实现)。

但让我稍微猜测一下:我们来谈谈n数组条目的总内容长度为. 可以想象,米>>n

然后所有用于存储的解决方案n我可以想象的条目可以分为两类:

  1. 新的 cs 名称顺序为n创建。这是上面概述的解决方案,但也是,例如,所有类型的字典实现,其中树的节点存储为单个宏。
  2. 至少一个宏,其扩展文本的顺序为被建造。

显然,基于第一种方法的任何解决方案都不会比上面给出的简单实现更有效,因为那个解决方案只需要访问内部哈希表,并且不能低于该值。

但我认为,基于第二种方法的解决方案也不会更有效,因为无论你如何实现它,为了检索数组元素,你都必须扩展一个宏,其扩展文本的顺序为,这显然比单次访问内部哈希表要慢,所以。

但也许我只是缺乏想象力,所以请随意提出第三种解决方案,或者实际上任何比简单的基于哈希的更有效的数组实现。

最后的问题

根据我目前所知,我的基本问题可以细化如下:

  1. 查看 TeXs 哈希算法的实际实现,构造 cs 名称以实现最大数组性能的最佳方法是什么?
  2. 在 TeX 中,是否有任何根本不同的方法来实现数组,并且提供与基于哈希的方法相当(甚至更好)的性能?
  3. 我是不是研究的方向错了?也许我的实验设置存在根本缺陷,导致我得到的结果不显著?我应该换一种测试方式吗?
  4. 我使用原始 TeX 引擎进行测试,没有使用任何特定于 TeX 扩展的构造。我用其他引擎测试了完全相同的代码,没有得到任何意外或明显不同的结果。很明显,LuaTeX 提供在 Lua 中实现数组的功能,因此提供了完全不同的选项。其他引擎(pdftex、XeTeX)是否提供了任何可能有助于实现数组的东西?

答案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。只需在每个十进制数字之间插入三个虚拟字符即可,变成987659---8---7---6---5为什么插入三个而不是更多?因为 16 是大于 10 的最小的 2 的幂。选择 8 而不是 16 仍然会导致哈希冲突:和 的哈希值0--0--0--0--09--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而且速度也没有明显加快。我以后会再看看的。也许可以将其重用于文档元素之间的关系。

答案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。前缀和后缀实际上不会使散列变得更糟,但哈希表的某些特殊结构意味着它们会占用更多空间。

答案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 开始,这种情况不再存在,所有字节均被使用。

相关内容