c – 比O(n)glob匹配器好吗？

发布时间：2020-12-16 10:18:39 所属栏目：百科来源：网络整理

导读：问题：给定一个 globs的列表,我需要从给定字符串匹配的列表中找到(并返回)一个glob,或者明确地确定没有匹配.不包括设置时间,性能必须优于所有的线性搜索水珠： foreach glob in list: if glob.matches(string): return globreturn None 问题：是否有可用的库

问题：给定一个 globs的列表,我需要从给定字符串匹配的列表中找到(并返回)一个glob,或者明确地确定没有匹配.不包括设置时间,性能必须优于所有的线性搜索水珠：

foreach glob in list:
  if glob.matches(string):
    return glob
return None

问题：是否有可用的库(C首选)？

编辑：经过一番思考,我想我可以说这可以做到.鉴于globs或多或少具有不同语法的正则表达式,使用glob语法的lex的运行时版本将符合要求.

鉴于问题可以简单地减少到已知问题,我仍然只对实施的解决方案感兴趣.

解决方法

将您的globs转换为正则表达式(一系列简单的字符串操作可以实现此目的 – *变为.*等).使用|将它们组合成单个正则表达式并将结果分配给每个glob的不同捕获组,以便在匹配时确定匹配的glob.依靠你最喜欢的正则表达式库将正则表达式编译成一个DFA,这个DFA希望比组成部分的线性遍历更加优化,这是可能的 – 但是,在最一般的情况下,它不会更快.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!