☰

反转标记列表的最有效方法（尾部递归）

tag-icon • tag-icon tex-core performance
反转标记列表的最有效方法（尾部递归）

目标：反转字符列表，从\def\mylist{abcdefgh}到\def\mylist{hgfedcba}。使用未出现在列表中的标记很容易，例如\relax：

\def\mylist{abcdefgh}
\def\reverse #1%
  {\edef #1{\expandafter \reverseloop #1\relax \marker }}
\def\reverseloop #1#2\marker
  {\ifx#1\relax\reverseend\fi \reverseloop #2\marker #1}
\def\reverseend #1\marker #2{}
\reverse\mylist
\show\mylist

到目前为止，一切都很好。不幸的是，这浪费了大量的内存，当\mylist有几千个字符时尝试应用相同的函数已经崩溃了。事实上，每次调用都会\reverseloop读取整个标记列表作为其#2参数，这是不会通过尾部递归从 TeX 内存中清除，因为 TeX 永远不会到达 的替换文本的末尾，或者更确切地说，只有在所有宏都展开\reverseloop后才会到达替换文本的末尾。您可以从 中的调用跟踪中看到这一点\reverseloop

\def\fiveup{\edef\mylist{\mylist\mylist\mylist\mylist\mylist}}
\fiveup \fiveup \fiveup \fiveup
\tracingall
\reverse\mylist

因此，整个过程消耗的内存与字符数量的平方成正比，达到数百万，这是 TeX 主内存的典型大小。我怎样才能仅使用线性量的内存来实现这样的逆转？

它应该可以轻松扩展到 100000 个字符，尽管可能有点慢：当然我们无法避免二次时间。我不太关心可扩展性。

答案1

\def\firstoftwo#1#2{#1}
\def\secondoftwo#1#2{#2}

\def\rev#1#2\revA#3\revB{%
  \if\relax\detokenize{#2}\relax
    \expandafter\firstoftwo
  \else
    \expandafter\secondoftwo
  \fi{#1#3}{\rev#2\revA#1#3\revB}}

\edef\x{\rev abcde\revA\revB}\show\x

在我的计算机上，反转一个包含 10000 个字符的字符串大约需要 20 秒，而且不会占用太多内存。

对于你的列表我得到

8.16 real         5.16 user         0.05 sys

（只是因为我必须对此做出反应\show）

其中#3有“到目前为止已反转”的字符串；在递归的每个步骤中，我都会将剩余字符串中的第一个标记放在它前面，即#1#2。当#2为空时，递归结束。

“线性”反转应通过以下方式获得

\catcode`\@=11
\def\reverse#1{\count@=\z@\def\temp{}
  \expandafter\doreverse#1\doreverse
  \loop\ifnum\count@>\z@
    \edef\temp{\temp\csname @@\romannumeral\count@\endcsname}%
    \advance\count@\m@ne
  \repeat
  \expandafter\def\expandafter#1\expandafter{\temp}%
}
\def\doreverse#1{%
  \unless\ifx#1\doreverse
    \advance\count@\@ne
    \expandafter\def\csname @@\romannumeral\count@\endcsname{#1}%
    \expandafter\doreverse
  \fi}
\catcode`\@=12

它仅受可用内存的限制，使用空间来控制序列。

使用\def\mylist{<string>}，\reverse\mylist依次定义\i，\ii依此类推，直到形成列表的标记，最后以相反的顺序将它们存储回 ，然后\temp使其\mylist等价。所以之后

\def\mylist{abcdefgh}
\reverse\mylist

\mylist将扩展为hgfedcba。它不适用于支撑组，但在这种情况下修改应该是微不足道的。

我在 42 秒内反转了一个 40000 个字符长的字符串。TeX 拒绝处理 100000 个字符长的字符串，因为它会耗尽池大小。（我删除了\begingroup，\endgroup因为它会耗尽保存大小。）

答案2

我没有检查内存，但是 lua 解决方案是：

\def\StrRev#1{\directlua{tex.print(string.reverse('#1'))}}

abcdefgh\par
\StrRev{abcdefgh}

打印内容：结果

我测量了两种字符串长度的运行时间。在我的机器上：

使用\nullfont

100 000 个字符：0.21 秒
1 000 000 个字符：1.24 秒

带字体

100 000 个字符：0.74 秒
1 000 000 个字符：6.21 秒

答案3

这是一个可扩展的解决方案，可以保留外部括号和条目顺序：

\documentclass{article}
\makeatletter
\let\xp\expandafter
\@ifdefinable\leftbracechar\relax
\edef\leftbracechar{\xp\@gobble\string\{}
\newcommand*\ifstrsame[2]{%
  \ifnum\pdfstrcmp{#1}{#2}=\z@\xp\@firstoftwo\else
    \xp\@secondoftwo\fi
}
\newcommand*\ifleftbrace[1]{%
  \ifstrsame{\detokenize\xp{\@gobble#1.}}{}\@secondoftwo{%
    \ifstrsame{\xp\@car\detokenize{#1}\@nil}\leftbracechar
      \@firstoftwo\@secondoftwo
  }%
}
\begingroup
\catcode`\&=3
\gdef\preservebracereverse#1{\pr@reverse{}&#1\@nnil}
\gdef\pr@reverse#1#2\@nnil{%
  \pr@rev@rse{#1}{\xp\ifleftbrace\xp{\@gobble#2}}#2\@nnil
}
\gdef\pr@rev@rse#1#2&#3{%
  \xp\ifx\@car#3\@nil\@nnil\xp\@firstoftwo\else\xp\@secondoftwo\fi
  {\unexpanded{#1}}
  {#2{\pr@reverse{{#3}#1}}{\pr@reverse{#3#1}}&}%
}
\endgroup
\makeatother

% Example:
\edef\x{\preservebracereverse{{ax}bcd{ey}}}
\show\x

\begin{document}

\end{document}

答案4

我不知道原贴作者在这 11 年里想出了什么，但 source3.pdf 中似乎没有什么“有趣”的东西，尤其\tl_reverse_items:n是最优解​时间。不确定记忆，也没有\str_reverse_items:n。

有了\expanded原始的可用资源，就有可能O（n log n）. （分而治之。）

否则，我认为最好的情况（具有 f 型扩展或类似情况）是O(n√n)。

我们的想法是，

  • 计算物品数量，
  • 先反转√n物品（需要在）时间），
  • 将其扔到剩余的n-√n物品（需要在）时间）
  • 然后继续反转剩余的n-√n项目。

每一次√n项目逆转，所花的时间是在），所以总时间复杂度是O(n√n)。

我尝试实现它。在 LuaLaTeX 上反转 524288 个字符需要 2.83 秒。看起来符合预期。

该实现仅处理非空格字符串字符，尽管将所有内容转换为空格部分也可以实现O(n√n)使用上面描述的相同想法，我不会期望有很大的差异。

相比之下，\tl_reverse_items:n反转 8192 个项目需要 1.74 秒。

（尽管这种比较不公平，\tl_reverse_items:n因为它不会一次抓取 8 个项目并且必须归还括号）

我认为在这种情况下这是最佳的，因为即使是简单的可扩展收集任务n输入流中未限定的项目并将它们放在一个组中似乎需要二次时间n没有\expanded（但需要线性时间）

时间复杂度O（n log n）很容易。
（因为所有事情（除了避免哈希减半）\expanded都可以做，\edef可以在相似的时间复杂度内不可扩展地做。至少在这个特殊情况下它不需要嵌套，所以可以取代分而治之方法中\edef的作用）\expanded

（由于它依赖于一堆未发布的库等，因此实现发布起来不太方便。）

或者，有一个解决方案O(kn)时间和欧拉 (k × n^(1/k))tok 寄存器（或哈希表条目，假设TeX 哈希运算耗时 O(1)）

下面我将描述解决方案在）（见下文注释）时间和O(√n)tok 寄存器。推广（例如，采用以下解决方案）在）时间和O(∛n)学习“tok 寄存器”并不难。

  • 将字符串拆分为√n零件，将每个零件存储到 tok 寄存器中。这可以在线性时间内完成。
  • 反转每个部分（其大小为√n）在线性时间内按部分大小进行计算，使用√ntok 寄存器。
  • 以相反的顺序将各部分连接成结果。这也可以在线性时间内完成。

（我尝试实现这个，它花费了 1.45 秒来反转 524288 个字符。我猜比上面的稍微快一点，尽管实现可以稍微优化一下，例如在后半部分一次分块 8 个字符。）

\tl_build_put_left实现，尽管有时间复杂性O(n log 5 n)代替在），速度快得出奇，只有 1.74 秒。

回想起来，这种方法存在一个问题，即范围内的数字1..n需要对数10（n）十进制数字来表示，所以实际时间复杂度是O（n log n）。

在我的算法中，字符串拆分部分和连接部分都会受到此影响。

因此，解决方法...

  • 首先，对于字符串拆分部分，我想不出比定义更好的方法√n控制序列来计算步骤。每个控制序列需要至少有 csname 长度log 10 (√n) = O(log n)。
  • 对于连接部分，类似地定义√n控制序列分别\toksdef被放入相应的 toks 寄存器，然后定义√n每个控制序列都会扩展为以下控制序列加上\toksdef被扩展的控制序列，因此其中一个控制序列的完整扩展等于所有这些控制序列的连接。√ntoks 寄存器。

这些部分的时间复杂度是O(√n log n)但幸运的是，它们只需要做一次，所以与在）。

另一个解决方法（仅适用于连接部分）是将其拆分成大小为O（log n），然后使用朴素算法处理，时间复杂度将是O（n 对数对数 n）。
如果以递归方式应用这个想法，我想它会变成O（n log * n）或类似的东西。

最终的时间复杂度仍然是在），但内存使用量却O(√n log n)。当然也有类似的想法O（∛n log n）等等，尽管我还没有完全弄清楚细节。

另一个（在我看来相当奇怪）解决方法是使用 e-TeX 扩展，\currentiflevel它可以在欧拉(1)。

我测试了这个的限制，在 LuaLaTeX 上它似乎是无限制的，但在 LaTeX、PDFLaTeX 和 XeLaTeX 上它运行到超过 2000000 直到报告“超出 TeX 容量”，所以在任何情况下，它对于任何目的来说都足够大，并且在理论分析中，我们可以假设它占用线性内存并且仅受可用内存的限制。（与\romannumeral嵌套级别、\expandafter嵌套级别或\dimexpr嵌套级别等不同）

虽然如果这个值已经是一个很大的值（在实践中不太可能，但在理论上是可能的）可能会有点困难，不确定......我可以看到几种方法

  • 重复执行\fi直到达到一个小的值，然后重复执行\ifcase\z@直到达到原始值（我认为这不会影响正常程序的行为......？除了可能改变日志中的内容我错了，\currentiftype存在）

  • 希望 TeX 实现能够评估内部\numexpr\currentiflevel-\originalvalue\relax数字欧拉(1)预期 ⟨内部数字⟩ 的时间，就是\the\toks\numexpr\currentiflevel-\originalvalue\relax在这种情况下。

    （这在理论上是可能的，因为在任何时间点都不可能O（log n）生成的 token，虽然我不确定它在现实中是如何实现的）

相关内容