☰

高效地在字符串中搜索宏

tag-icon • tag-icon latex3
高效地在字符串中搜索宏

作为后续问题这，我意识到\regex_extract_all与相比，这确实很慢\str_if_in。我的目标如下：我有一个L宏列表/哈希表和一个字符串s（我更希望它保留为字符串而不是标记列表……但我可能能够使用原始标记列表，因此如果使用原始标记列表的解决方案更快，我想我可以接受它）：我的目标是从中提取s属于的所有宏L。我看到两个选项：

  • 使用循环L并检查宏是否在字符串中\str_if_in。问题：这样的规模|s| x |L|可能会变得很大（可能L有几百个元素）
  • 使用正则表达式s来提取所有宏并检查它们是否在哈希表中L：这像一样扩展|s|，但问题是：正则表达式在 LaTeX 中真的很慢。

所以我的问题是：我可以编写一个\regex_extract_all能够有效提取宏的专门版本吗？

梅威瑟：

\documentclass[]{article}

\begin{document}

\ExplSyntaxOn
\cs_generate_variant:Nn \regex_extract_all:nnN { VVN, nVN }
\cs_generate_variant:Nn \regex_extract_all:NnN { NVN }

\str_new:N \l__robExt_my_str
\str_set:Nn \l__robExt_my_str {I like \vegetable and \fruit.}

\regex_const:Nn \l__robExt_macro_regex { \\[A-Za-z]+ }
\regex_show:N \l__robExt_macro_regex
\regex_extract_all:NVN \l__robExt_macro_regex \l__robExt_my_str \l__robExt_output_seq
\show\l__robExt_output_seq % I need a more efficient way to get this list

\ExplSyntaxOff

\end{document}

答案1

恕我直言，完成你的任务最有效的解决方案如下：

\def\registerL#1{\expandafter\def\csname L:\string#1\endcsname {}}

\def\getfromstring#1{\normalbraces#1\def\listmacros{}\expandafter\getfromstringA#1\getfromstringA}
\def\getfromstringA#1{\ifx#1\getfromstringA \else
   \ifcsname L:\string#1\endcsname \addto\listmacros{#1}\fi
   \expandafter\getfromstringA\fi
}
\long\def\addto#1#2{\expandafter\def\expandafter#1\expandafter{#1#2}}

\let\ea=\expandafter
\def\normalbraces#1{{\catcode`{=12 \catcode`}=12 \everyeof={\endfile}%
   \ea\normalbracesA\ea#1\scantokens\ea{#1}}}
\def\normalbracesA#1#2\endfile{\gdef#1{#2}}

\registerL \vegetable
\registerL \fruit

\def\mystring{I like {\vegetable and} \fruit.}

\getfromstring\mystring

{\tt \meaning\listmacros} % prints  macro:->\vegetable \fruit 

\bye

您要搜索的宏已由 注册\registerL \macro。这意味着它们存储在哈希表中（搜索速度非常快）。接下来，\getfromstring宏会逐个扫描给定的字符串标记，如果标记是已注册的宏，则将标记保存到\listmacros中\addto。

你可以用这个解决方案做基准测试。我确信没有比它更快的解决方案了。

答案2

下面使用 实现对宏的可扩展搜索etl。

宏\__robExt_extract_macros:n使用该可扩展搜索将所有找到的宏列表分配给一个序列。这适用于tl输入版本，并且适用于任何级别的组。代码应该足够快。

我将您的\regex_extract_all:NVN使用情况与我的进行了基准测试\__robExt_extract_macros:n，我的实现速度提高了 38 倍，同时执行了更多操作（但仍然有点慢，如果要搜索的宏列表是固定的，则可以结合我的循环和 @wipet 的检查来\ifcsname加快速度）。

\documentclass[]{article}

\usepackage{etl}

\ExplSyntaxOn
\cs_new:Npn \__robExt_macro_searcher:nn #1#2
  {
    % search in the tl #1 for all macros contained in #2
    \__robExt_macro_searcher_aux:en
      { \__robExt_macro_searcher_prepare:n {#2} }
      {#1}
  }
\cs_new:Npn \__robExt_macro_searcher_prepare:n #1
  { \tl_map_tokens:nn {#1} { {} \exp_not:n } }
\cs_new:Npn \__robExt_macro_searcher_aux:nn
  {
    \etl_act:nnnnn
      \__robExt_macro_searcher_search:nN
      \use_none:n
      \__robExt_macro_searcher_aux:nn
  }
\cs_generate_variant:Nn \__robExt_macro_searcher_aux:nn { e }
\cs_new:Npn \__robExt_macro_searcher_search:nN #1#2
  {
    \__robExt_macro_searcher_cmp_loop:Nw #2 #1
    \prg_break: {} \prg_break: {} \prg_break: {} \prg_break: {}
    \prg_break_point:
  }
\cs_new:Npn \__robExt_macro_searcher_cmp_loop:Nw #1 #2#3 #4#5 #6#7 #8#9
  {
    #2 \etl_token_if_eq:NNT #1 #3 \__robExt_macro_searcher_output:w
    #4 \etl_token_if_eq:NNT #1 #5 \__robExt_macro_searcher_output:w
    #6 \etl_token_if_eq:NNT #1 #7 \__robExt_macro_searcher_output:w
    #8 \etl_token_if_eq:NNT #1 #9 \__robExt_macro_searcher_output:w
    \__robExt_macro_searcher_cmp_loop:Nw #1
  }
\cs_new:Npn \__robExt_macro_searcher_output:w
    #1 \__robExt_macro_searcher_cmp_loop:Nw #2
  { \exp_not:N #2 \prg_break: }

\cs_generate_variant:Nn \seq_set_split:Nnn { Nne }
\cs_new_protected:Npn \__robExt_extract_macros:n #1
  {
    \seq_set_split:Nne \l__robExt_output_seq {}
      { \__robExt_macro_searcher:nn {#1} { \vegetable \fruit } }
  }
\ExplSyntaxOff

\begin{document}

\ExplSyntaxOn

\__robExt_extract_macros:n {I like \vegetable and \fruit.}
\seq_show:N \l__robExt_output_seq % I need a more efficient way to get this list

\ExplSyntaxOff

\end{document}

如果只搜索一组固定的宏，并且在找到它们时执行特定的代码（而真实的列表根本不引起我们的兴趣），我们也可以实现这一点（这使得etl基于的实现更加简单！）：

\documentclass[]{article}

\usepackage{etl}

\ExplSyntaxOn
\cs_new_protected:Npn \__robExt_setup_protected_action:Nn #1#2
  { \cs_new_protected:cpn { __robExt_action_ \token_to_str:N #1 : } {#2} }
\cs_new_protected:Npn \__robExt_setup_action:Nn #1#2
  { \cs_new:cpn { __robExt_action_ \token_to_str:N #1 : } {#2} }

\cs_new:Npn \__robExt_macro_searcher:n
  {
    \etl_act:nnnnn
      \__robExt_macro_searcher_search:nN
      \use_none:n
      { \use_i:nn \__robExt_macro_searcher:n }
      {}
  }
\cs_generate_variant:Nn \__robExt_macro_searcher_aux:nn { e }
\cs_new:Npn \__robExt_macro_searcher_search:nN #1#2
  {
    \cs_if_exist:cT { __robExt_action_ \token_to_str:N #2 : }
      { \exp_not:c { __robExt_action_ \token_to_str:N #2 : } }
  }
\ExplSyntaxOff

\begin{document}
\ExplSyntaxOn

\__robExt_setup_protected_action:Nn \vegetable
  { \typeout { \noexpand \vegetable used } }
\__robExt_setup_protected_action:Nn \fruit
  { \typeout { \noexpand \fruit used } }

\__robExt_macro_searcher:n {I like \vegetable and \fruit.}

\ExplSyntaxOff
\end{document}

打印

\vegetable used
\fruit used

到日志/终端。

答案3

假设每个搜索的宏的名称中都不包含空格，以下是一个基于字符串的解决方案，它应该非常快。

我们利用这样一个事实：\tl_to_str:n每个控制字都以当前值\escapechar（我们主动设置的，但实际上大多数情况下应该是反斜杠）开头并以空格结尾。所以我们抓取这两个之间的所有内容并假设这是宏名称。这样我们就可以非常快速地完成列表，并以一个已知的宏名称终止，该宏名称也满足该条件。此外，我们在~用户输入的末尾放置了一个，以确保如果发现一些意外输入，我们可以正常失败。

为了不被控制符号绊倒，我们需要测试每个反斜杠后的第一个标记是否在 中[A-Za-z]。这个测试是最耗时的。

我根据代码对其进行了基准测试etl，对于输入，I like \vegetable and \fruit.此方法稍快一些（约 160 次操作 vs. 约 175 次操作），但一旦出现三个控制符号（I \\ \> \< like \vegetable and \fruit.），则需要更长的时间（约 300 次操作 vs. 约 230 次操作）。因此，选择这两种方法中的哪一种取决于出现的控制符号数量。

\documentclass[]{article}

\ExplSyntaxOn
\cs_new_protected:Npn \__robExt_setup_protected_action:Nn #1#2
  { \cs_new_protected:cpn { __robExt_action_ \cs_to_str:N #1 : } {#2} }
\cs_new_protected:Npn \__robExt_setup_action:Nn #1#2
  { \cs_new:cpn { __robExt_action_ \cs_to_str:N #1 : } {#2} }
\cs_new_protected:Npe \__robExt_search_macros:n #1
  {
    \exp_not:n
      {
        \group_begin:
          \tex_escapechar:D = `\\ \exp_stop_f:
          \exp_last_unbraced:NNo
        \group_end:
        \__robExt_search_macros:w \tl_to_str:n
      }
      { #1 } ~ \tl_to_str:n { \robExt_search_macros_done: }
  }
\__robExt_setup_action:Nn \robExt_search_macros_done: { \use_none:n }
\cs_generate_variant:Nn \use_ii_i:nn { e }
\use_ii_i:en { \char_generate:nn { `\\ } { 12 } } { \cs_new:Npn \__robExt_search_macros:w #1 } #2
  {
    \__robExt_if_letter:nTF {#2}
      { \__robExt_search_macros_aux:w #2 }
      { \__robExt_search_macros:w }
  }
\cs_new:Npn \__robExt_search_macros_aux:w #1~
  {
    \cs_if_exist_use:c { __robExt_action_#1: }
    \__robExt_search_macros:w
  }
\prg_new_conditional:Npnn \__robExt_if_letter:n #1 { TF }
  {
    \bool_lazy_or:nnTF
      {
        \bool_lazy_and_p:nn
          { \int_compare_p:nNn { `#1 } > { `a - 1 } }
          { \int_compare_p:nNn { `#1 } < { `z + 1 } }
      }
      {
        \bool_lazy_and_p:nn
          { \int_compare_p:nNn { `#1 } > { `A - 1 } }
          { \int_compare_p:nNn { `#1 } < { `Z + 1 } }
      }
      \prg_return_true:
      \prg_return_false:
  }
\ExplSyntaxOff

\begin{document}
\ExplSyntaxOn

\__robExt_setup_protected_action:Nn \vegetable
  { \typeout { \noexpand \vegetable used } }
\__robExt_setup_protected_action:Nn \fruit
  { \typeout { \noexpand \fruit used } }

\__robExt_search_macros:n {I like \vegetable and \fruit.}

\ExplSyntaxOff
\end{document}

印刷

\vegetable used
\fruit used

到日志/终端。

相关内容