☰

执行查找表时超出容量

tag-icon • tag-icon macros
执行查找表时超出容量

我想实现简单的键值查找表。我想以函数式的方式实现它，所以我将这种表的初始状态定义get为导致错误的函数（因为表最初是空的）。然后我定义了put一个函数，get如果其参数等于get参数，则重新定义执行该操作，它应该返回值，在其他情况下应该返回原始值get。

一般来说，它应该成为嵌套的堆栈if。我在专用包中完成了它。

如果键在表中，则一切正常。如果我尝试获取不存在的键，则会出现问题 - 它应该导致错误，但实际上它会导致堆栈溢出：

\lookupPut{x}{foo}
\lookupPut{y}{bar}
\lookupGet{x} % gives foo
\lookupGet{y} % gives bar
\lookupGet{z} % causes 'capacity exceeded'

TeX 容量超出，抱歉 [输入堆栈大小=5000]。 \lookupGet{z}

这是完整的包源：

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{lookup}

\RequirePackage{ifthen}

\newcommand{\lookupGet}[1]{
    \PackageError
    {customdetails}
    {No #1 key in lookup!}
    {
        Key #1 was not found in lookup. You can insert it with lookupPut(key, value).
    }
}

\newcommand{\lookupPut}[2]{
    \let\@lookupHelper\lookupGet
    \renewcommand{\lookupGet}[1]{
        \PackageInfo{lookup}{get key X #1 X} % X characters are to be sure where string starts and ends
        \PackageInfo{lookup}{get val X #2 X}
        \PackageInfo{lookup}{get 1st X ##1 X}
        \ifthenelse{
            \equal{##1}{#1}
        }
        {#2}
        {\@lookupHelper{##1}}
    }
}

\endinput

我确信这是保存旧版本函数的正确方法——我知道如果我使用\let，它会在定义时刻而不是使用时刻分配已解析的值（如果我不清楚，请原谅，我对 TeX 及其命名还不太熟悉）。

查找表是否是个好主意并不在这里。

PS：我不知道我应该在这里使用什么标签。如果你有标签，请继续编辑 ;)

答案1

实现查找的最简单方法是使用 TeX 的哈希表，通过定义一个\lookup@<key>扩展为的宏<value>：

%%% lookup.sty %%%
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{lookup}[2015/06/10 Lookup for custom details]

\newcommand{\lookupGet}[1]{%
  \@ifundefined{lookup@#1}{%  
    \PackageError{lookup}{No #1 key in lookup}{%
      Key #1 was not found in lookup. %
      You can insert it with \string\lookupPut{key}{value}.%
    }%
  }{%
    \@nameuse{lookup@#1}%
  }%
}
\newcommand{\lookupPut}[2]{%
  \@namedef{lookup@#1}{#2}%
}
\endinput

平均运行时间复杂度为常数：O(1)。

该问题的实现思路是依次检查每个密钥，直到找到正确的密钥。这使得平均运行时间复杂度为线性：O(n）。

可以通过在宏中收集键值对来完成实现。然后可以通过修改和查询列表来实现诸如 put、get、lookup、delete 之类的操作。但是运行时复杂度至少为 O(n），因为数据宏至少需要扩展一次，所有n項目。

进一步说明：

  • 行尾通常会转换为空格。问题中的代码有很多不需要的空格，它们在水平模式下不会消失。

  • Ulrike 已经解释了无限循环评论. 可以\let使用包中的 patch 命令以更好的方式扩展宏定义，而无需进行有问题的分配，etoolbox例如参见 macros \appto。\preto

答案2

Heiko 已经解释了错误的原因。以下是针对您的查找表的不同实现。

您可以根据需要定义任意数量的表，也可以以可扩展的方式检索值（但不进行错误检查），也可以进行错误检查；可选参数允许\lookupGet将项目存储在控制序列中。

文件lookup.sty

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{lookup}

\RequirePackage{xparse}

\ExplSyntaxOn
\DeclareExpandableDocumentCommand{\lookupGetX}{O{default}m}
 {
  \lookup_get_x:nn { #1 } { #2 }
 }
\NewDocumentCommand{\lookupGet}{O{default}mo}
 {
  \lookup_get_check:nn { #1 } { #2 }
  \IfValueTF { #3 }
   {
    \tl_set_eq:NN #3 \l_lookup_item_tl
   }
   {
    \tl_use:N \l_lookup_item_tl
   }
 }
\NewDocumentCommand{\lookupPut}{O{default}mm}
 {
  \lookup_put:nnn { #1 } { #2 } { #3 }
 }

\prop_new:N \l_lookup_table_default_prop % the default table
\tl_new:N \l_lookup_item_tl

\cs_new:Npn \lookup_get_x:nn #1 #2
 {% syntactic sugar for \prop_item:nn
  \prop_item:cn {l_lookup_table_#1_prop} { #2 }
 }

\cs_new_protected:Npn \lookup_get_check:nn #1 #2
 {
  \prop_if_exist:cTF { l_lookup_table_#1_prop }
   {% the table exists
    \prop_get:cnN { l_lookup_table_#1_prop } { #2 } \l_lookup_item_tl
    \quark_if_no_value:VT \l_lookup_item_tl
     {% no value available
      \msg_error:nnnn { lookup } { no~item } { #1 } { #2 }
      \tl_set:Nn \l_lookup_item_tl { ERROR }
     }
   }
   {% the table doesn't exist
    \msg_error:nnn { lookup }{ no~table } { #1 }
   }
 }
\cs_generate_variant:Nn \quark_if_no_value:nT { V }

\cs_new_protected:Npn \lookup_put:nnn #1 #2 #3
 {
  \prop_if_exist:cF { l_lookup_table_#1_prop }
   {
    \prop_new:c { l_lookup_table_#1_prop }
   }
  \prop_put:cnn { l_lookup_table_#1_prop } { #2 } { #3 }
 }

\msg_new:nnnn { lookup } { no~item }
 {
  No~'#2'~key~in~lookup~table~(#1).
 }
 {
  Key~'#2'~was~not~found~in~lookup~table~(#1).~
  You~can~insert~it~with~\tl_to_str:N \lookupPut[<table>]{<key>}{<value>}.
 }

\msg_new:nnnn { lookup } { no~table }
 {
  No~'#1'~lookup~table.
 }
 {
  The~lookup~table~'#2'~does~not~exist.
 }
\ExplSyntaxOff

\endinput

文件testlookup.tex

\documentclass{article}
\usepackage{lookup}

\begin{document}

% store some values
\lookupPut{x}{foo}
\lookupPut{y}{bar}

\lookupGet{x} % gives foo

\lookupGet{y} % gives bar

\lookupGet{z} % gives ERROR

\lookupGet{y}[\test]
\texttt{\meaning\test} % gives macro:->bar

% a new lookup table

\lookupPut[new]{newx}{newfoo}

\lookupGet[new]{newx} % gives newfoo

\lookupGet[new]{newy} % gives ERROR

\lookupGet[inexistent]{Hey!} % gives ERROR

% check the fully expandable version

\edef\test{\lookupGetX{x} \lookupGetX[new]{newx}}

\texttt{\meaning\test} % gives macro:-> foo newfoo

\end{document}

终端输出

This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015) (preloaded format=pdflatex)
 restricted \write18 enabled.
entering extended mode
(./testlookup.tex
LaTeX2e <2015/01/01>
Babel <3.9l> and hyphenation patterns for 79 languages loaded.
(/usr/local/texlive/2015/texmf-dist/tex/latex/base/article.cls
Document Class: article 2014/09/29 v1.4h Standard LaTeX document class
(/usr/local/texlive/2015/texmf-dist/tex/latex/base/size10.clo)) (./lookup.sty
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3packages/xparse/xparse.sty
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/expl3.sty
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/expl3-code.tex)
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/l3unicode-data.def)
(/usr/local/texlive/2015/texmf-dist/tex/latex/l3kernel/l3pdfmode.def))))
(./testlookup.aux)

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!
! lookup error: "no item"
! 
! No 'z' key in lookup table (default).
! 
! See the lookup documentation for further information.
! 
! For immediate help type H <return>.
!...............................................  

l.14 \lookupGet{z} 
                   % gives ERROR
? 

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!
! lookup error: "no item"
! 
! No 'newy' key in lookup table (new).
! 
! See the lookup documentation for further information.
! 
! For immediate help type H <return>.
!...............................................  

l.25 \lookupGet[new]{newy} 
                           % gives ERROR
? 

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!
! lookup error: "no table"
! 
! No 'inexistent' lookup table.
! 
! See the lookup documentation for further information.
! 
! For immediate help type H <return>.
!...............................................  

l.27 \lookupGet[inexistent]{Hey!} 
                                  % gives ERROR
? 
[1{/usr/local/texlive/2015/texmf-var/fonts/map/pdftex/updmap/pdftex.map}]
(./testlookup.aux) )</usr/local/texlive/2015/texmf-dist/fonts/type1/public/amsf
onts/cm/cmr10.pfb></usr/local/texlive/2015/texmf-dist/fonts/type1/public/amsfon
ts/cm/cmtt10.pfb>
Output written on testlookup.pdf (1 page, 23121 bytes).
Transcript written on testlookup.log.

PDF 输出

在此处输入图片描述

解释

借助expl3未来 LaTeX 的编程框架，我们可以获得多种数据类型，其中包括财产清单，并附有参考名称prop。

\l_<module>_<proper name>_prop属性列表变量具有类似或 的名称\g_<module>_<proper name>_prop，其中l和g表示变量是在本地管理还是全局管理。

该包xparse自动加载expl3并\ExplSyntaxOn进入编程框架。

首先，我定义了三个用户级宏，它们只是对参数进行规范化；例如，\lookupGetX声明为完全可扩展且具有一个可选参数，具有默认值default和一个强制参数。

让我们检查一下\lookup_get_x:nn；它只是调用

\prop_item:cn {l_lookup_table_#1_prop} { #2 }

意思是：获取第二个参数中给出的键对应的第一个参数所指定的属性列表的值。

属性列表是以下内容的集合核心价值对。有人说

\prop_put:Nnn \l_foo_bar_prop { x } { abc }

以便

\prop_item:Nn \l_foo_bar_prop { x }

将传递与x给定属性列表中的键关联的值。但是，通过在我们使用的函数中更改，我们给出了Nc姓名括号中的变量没有反斜杠，因此我们可以在那里使用参数。因此调用

\prop_item:cn { l_lookup_table_default_prop } { x }

效果与

\prop_item:Nn \l_lookup_table_default_prop { x }

但是，如您所见，我们可以根据所使用的函数的参数注入不同的属性列表名称。

如果键不存在，则该函数\prop_item:Nn（或其变体）不返回任何内容。这就是为什么我定义另一个版本，该版本执行必要的检查，但存在缺陷，无法在以下情况下使用。这就是使用第二种方法从属性列表中检索值的原因：\prop_item:cn\edef\write\lookup_get_check:nn

\prop_get:NnN \l_lookup_table_default_prop { x } \l_lookup_item_tl

检索与键关联的值x（如前所述，我使用变体\prop_get:cnN来姓名变量）并将其存储在代币列表多变的\l_lookup_item_tl。

如果密钥不存在，则存储的值是\q_no_value可以查找的特殊标记，这用于通过条件检查错误，\quark_if_no_value:VTF如果作为第一个参数给出的变量仅包含特殊标记，则该条件位于 true 分支之后，否则位于 false 分支之后。 true 分支发出错误消息，并将标记列表变量中的值更改为比特殊标记更合理的值。

不过，在尝试检索值之前，会检查所引用的属性列表变量是否存在，\prop_if_exist:cTF如果属性列表已设置，则进入 true 分支。在这种情况下，false 分支会发出正确的错误消息。

好消息是，在编程框架中，最多可以有\ExplSyntaxOff、空格、行尾和空行被忽略（某些特殊情况除外）。你的代码中充满了虚假的空格，这种编程风格明确地通过输入 来告诉需要空格的位置~。

更多相关信息请参见texdoc expl3和texdoc interface3。

相关内容