☰

尝试消除递归过程中的堆栈溢出（字母冒泡排序器）

tag-icon • tag-icon sorting recursion
尝试消除递归过程中的堆栈溢出（字母冒泡排序器）

我在看这个问题，按行的字母顺序排列表格，并想，“那个 OP 需要某种冒泡排序器。”

我在这里做了一个数值冒泡排序器，使用 LaTeX 压缩数字列表（它实际上对参考编号进行了排序，并且压缩了连续的引用）并且发现我也做了一个 alpha-bubble 排序器，同样在这里，使用 LaTeX 对逗号分隔的列表进行排序？。

不幸的是，我发现当列表变大时，alpha-bubble 排序器很容易因递归而导致堆栈溢出。因此，我努力简化这里的事情，重写代码。它能够处理比引用版本更大的列表大小，但正如所包含的 MWE 所示，如果我取消注释列表中的那个额外项目（encontrar），我就会破坏堆栈。

现在我知道，理论上，避免在条件递归期间炸毁堆栈的方法是...\expandafter\recursion\fi。但是，当递归嵌套在块中很深时\if，​​或者当递归不仅仅是一个宏名，而是一个...\recursion<data-block>\relax\fiblob 时，我一直不擅长掌握这种技巧。

David C 告诉我堆栈大小是在 texmf.cnf 中设置的，尽管我还没有在我的 MikTeX 安装中找到该文件，但我意识到扩大堆栈并不是一个好的解决办法，而是一种更好的代码。

我还没有做出\the\lccode调整来忽略搜索中的字母大小写，但是每次只能做一件事。

我认为通用的 LaTeX 阿尔法冒泡排序器不仅对我有用，而且对我之外的人也有用，因此我在这里将其作为一个问题发布，希望它能够被打败并成为一个有用的工具。

在下面的 MWE 中，例程\alphabubblesorter调用\sortlist进行主冒泡排序，\picknext对于首字母相同的情况，调用 。因此，\sortlist通过数据列表进行递归，\picknext通过两个比较条目的字母列表进行递归。

\documentclass[10pt]{article}
\newcommand\alphabubblesort[1]{\def\sortedlist{}\expandafter\sortlist#1,9,\relax}
\def\sortlist#1#2,#3#4,#5\relax{%
  \ifnum`#3=`9\relax%
    \edef\sortedlist{\sortedlist#1#2}%
  \else
    \ifnum`#1<`#3\relax%
      \edef\sortedlist{\sortedlist#1#2,}%
      \sortlist#3#4,#5\relax%
    \else%
      \ifnum`#1>`#3\relax%
        \let\tmp\sortedlist%
        \def\sortedlist{}%
        \expandafter\sortlist\tmp#3#4,#1#2,#5\relax%
      \else%
        \picknext#2!,#4!\relax%
        \if F\flipflop%
          \edef\sortedlist{\sortedlist#1#2,}%
          \sortlist#3#4,#5\relax%
        \else%
          \let\tmp\sortedlist%
          \def\sortedlist{}%
          \expandafter\sortlist\tmp#3#4,#1#2,#5\relax%
        \fi%
      \fi%
    \fi%
  \fi%
}
\def\picknext#1#2,#3#4\relax{%
  \ifnum`#1<`#3\relax
    \xdef\flipflop{F}%
  \else%
    \ifnum`#1>`#3\relax%
      \xdef\flipflop{T}%
    \else%
      \picknext#2!,#4!\relax%
    \fi%
  \fi%
}
\begin{document}
\alphabubblesort{da,cc,ca,eda,edc,edb,ef,ec,ed,eb,edzq,ba,e,fa,waaa,wa,qa}\sortedlist

\def\mydata{%
Spanish     ,
ser         ,
haber       ,
estar       ,
tener       ,
hacer       ,
poder       ,
decir       ,
ir          ,
ver         ,
dar         ,
saber       ,
querer      ,
llegar      ,
pasar       ,
deber       ,
poner       ,
parecer     ,
quedar      ,
creer       ,
hablar      ,
llevar      ,
dejar       ,
seguir      ,
%encontrar   ,
llamar       }
\alphabubblesort{\mydata}\sortedlist
\end{document}

在此处输入图片描述

答案1

类似这样的操作允许在递归调用之前弹出参数堆栈

\documentclass[10pt]{article}
\newcommand\alphabubblesort[1]{\def\sortedlist{}\expandafter\sortlist#1,zzzzzzzzzz,\relax}
\def\sortlist#1#2,#3#4,#5\relax{%
  \let\next\relax
  \ifnum`#3=`z\relax%
    \edef\sortedlist{\sortedlist#1#2}%
  \else
    \ifnum`#1<`#3\relax%
      \edef\sortedlist{\sortedlist#1#2,}%
      \def\next{\sortlist#3#4,#5\relax}%
    \else%
      \ifnum`#1>`#3\relax%
        \let\tmp\sortedlist%
        \def\sortedlist{}%
        \def\next{\expandafter\sortlist\tmp#3#4,#1#2,#5\relax}%
      \else%
        \picknext#2!,#4!\relax%
        \if F\flipflop%
          \edef\sortedlist{\sortedlist#1#2,}%
           \def\next{\sortlist#3#4,#5\relax}%
        \else%
          \let\tmp\sortedlist%
          \def\sortedlist{}%
          \def\next{\expandafter\sortlist\tmp#3#4,#1#2,#5\relax}%
        \fi%
      \fi%
    \fi%
  \fi%
\next
}
\def\picknext#1#2,#3#4\relax{%
  \ifnum`#1<`#3\relax
    \xdef\flipflop{F}%
  \else%
    \ifnum`#1>`#3\relax%
      \xdef\flipflop{T}%
    \else%
      \ZZfifi{\picknext#2!,#4!\relax}%
    \fi%
  \fi%
}

\def\ZZfifi#1\fi\fi{\fi\fi#1}

\begin{document}
\alphabubblesort{30,2c,2a,4da,4dc,4db,4f,4c,4d,2b,4dzq,10,4,50,W0,w0,q0}\sortedlist

\def\mydata{%
Spanish     ,
ser         ,
haber       ,
estar       ,
tener       ,
hacer       ,
poder       ,
decir       ,
ir          ,
ver         ,
dar         ,
saber       ,
querer      ,
llegar      ,
pasar       ,
deber       ,
poner       ,
parecer     ,
quedar      ,
creer       ,
hablar      ,
llevar      ,
dejar       ,
seguir      ,
encontrar   ,
llamar       }
\alphabubblesort{\mydata}\sortedlist
\end{document}

我不想干涉大卫（史蒂文）的惊人回答，但我意识到我可以通过直接转到来进一步简化事情\picknext。我还添加了\the\lccode筛选字母大小写的部分。

因此，在这个版本中，\sortlist如果合适，仅执行两个相邻列表项的交换，而\picknext决定是否应该进行交换。（\sortlist除了列表结束条件之外，不再比较任何内容）。

由于 David 太谦虚了，没有列出他所做的更改的细节，我只想提醒读者注意他对 的使用\next，这是一种将内容移出嵌套\if结构的方法，并不罕见。但最精彩的是他创建并使用了\ZZfifi，如果我理解得没错的话，它吸收了当前递归的剩余两个\fis，然后从堆栈中弹出其中两个作为下一个递归的第一步。大师级！

\documentclass[10pt]{article}
\newcommand\alphabubblesort[1]{\def\sortedlist{}\expandafter\sortlist#1,\cr,\relax}
\def\sortlist#1,#2,#3\relax{%
  \let\next\relax
  \ifx\cr#2\relax%
    \edef\sortedlist{\sortedlist#1}%
  \else
    \picknext#1!,#2!\relax%
    \if F\flipflop%
      \edef\sortedlist{\sortedlist#1,}%
      \def\next{\sortlist#2,#3\relax}%
    \else%
      \let\tmp\sortedlist%
      \def\sortedlist{}%
      \def\next{\expandafter\sortlist\tmp#2,#1,#3\relax}%
    \fi%
  \fi%
\next
}
\def\picknext#1#2,#3#4\relax{%
  \ifnum\the\lccode`#1<\the\lccode`#3\relax
    \xdef\flipflop{F}%
  \else%
    \ifnum\the\lccode`#1>\the\lccode`#3\relax%
      \xdef\flipflop{T}%
    \else%
      \ZZfifi{\picknext#2!,#4!\relax}%
    \fi%
  \fi%
}
\def\ZZfifi#1\fi\fi{\fi\fi#1}
\begin{document}
\alphabubblesort{da,cc,ca,eda,edc,edb,ef,ec,ed,eb,edzq,ba,e,fa,waaa,wa,qa}\sortedlist

\def\mydata{
Spanish, ser, haber, estar, tener, hacer, poder, decir, ir, ver, dar, saber, querer,
llegar, pasar, deber, poner, parecer, quedar, creer, hablar, llevar, dejar,
seguir, encontrar, llamar}
\alphabubblesort{\mydata}\sortedlist
\end{document}

在此处输入图片描述

相关内容