将一个字符串与一组通配符进行比较的最快方法

本文关键字：比较 方法 一个 字符串 一组 通配符 | 更新日期: 2023-09-27 18:29:49

我有一个Dictionary，我的Key是一个带通配符的String。我想知道一个字符串是否与字典中的任何键匹配。

示例：

String str = "Really Large String";
Dictionary dic = new Dictionary<String, MyClass>();
dic.Add("First+Match*", new MyClass());
dic.Add("*Large*", new MyClass());

编辑：我想做一些类似的事情：

foreach(var s in dic.Keys){
  if(str.Match(s))
    //Do Something
}

将一个字符串与一组通配符进行比较的最快方法

为什么不呢，

var dic = Dictionary<Regex, MyClass>()
dic.Add(new Regex("..."), new MyClass)
....
foreach(var match in dic.Keys.Where(k => k.IsMatch(str)))
{
    var myClass = dic[match];
    ....
}

现在的问题是，为什么要使用字典，为什么不扩展MyClass来匹配字符串本身，也许是使用名为Match的Predicate。

var matchers = new HashSet<MyClass>();
matchers.Add(new MyClass("some regex?");
....
foreach(var match in matchers.Where(Match(str)))
{
    ....
}

编辑

如果你只想要第一个匹配，那么你可以使用FirstOrDefault而不是Where。

var firstMatch = matchers.FirstOrDefault(Match(str))
if (firstMatch != null)
{
    ....
}

然而，这将使列表的顺序变得重要。

编辑2

将MyClass部分实现为包含Match谓词可能是。。。

partial class MyClass
{
    private readonly RegEx matcher;
    public MyClass(string regEx)
    {
        matcher = new RegEx(regEx);
    }
    public bool Match(string value)
    {
        return matcher.IsMatch(value);
    }
}

您可以使用RegEx，只需将带有通配符的字符串转换为正则表达式模式（我认为您想使用非常古老的标准"*"answers"？"通配符）：

public static string ToRegEx(string pattern)
{
    return Regex.Escape(pattern).Replace("''*", ".*").Replace("''?", ".");
}

这个解释会比我想要的长一点，但在这种情况下，完全了解幕后发生的事情可能非常有用。因为一种特定的方法在源代码中看起来很有效，并不意味着CPU也会以同样的方式看待它。当您关心字节对字节的执行速度时，您必须了解在实际执行操作的级别上发生了什么。任何高于这个级别的东西都只是语义，最终都是美化的宏，它们不会给你一个准确的实际创建的画面。

Intel/AMD CPU有一组重复扫描指令，允许您设置指针，将一个字节放入寄存器，设置要扫描的字节数，然后CPU在内部启动并作为单个内部指令运行扫描，逐字节扫描，直到找到匹配或不匹配（或计数器用完）。当计数器用完时，调整指针和处理"不符合标准；我用完了计数器！"的情况可能是一个混乱的过程；这不会直接影响您的代码，但如果您在循环中进行大量单独的搜索，它可能会影响执行时间。因此，最大限度地减少实际搜索次数从来都不是一个坏主意。这不是一个很大的因素，但它可能会起作用。

在大型搜索的情况下，我在自己的代码中所做的是向前扫描第一个字节。将其作为任何进一步过程的起点进行匹配，可以节省绝大多数时间，否则通过比较每个字节会浪费这些时间。让CPU来做吧。CPU必须做大量的工作，只是为了加载指令并准备执行它，这样任何时候你都可以减少工作量，程序就会运行得更快。

这里的问题是你不能直接控制这些事情。无论你使用什么语言，都很可能使用最慢的暴力方法：拿起一个字节，看着它，拿起下一个字节。如果你的语言就是这样做的（大多数都是这样做的），那么任何两种编码方法的选择都不会有太大区别：它们都已经被困在了性能的基础上。如果你在一个可以插入一块汇编代码的情况下，你将从中受益匪浅。但大多数人都被禁止这样做，因为在1985年，这被认为是非法的。当然，有32位和64位的问题需要考虑，但这些问题是可以考虑的。总之，最重要的是，如果你能确切地了解你的特定语言是做什么的，那么就要考虑到这一点。如果它使用的是比较字符串的搜寻和啄取方法，那么这场战斗已经失败了，你为调整代码所做的大部分工作可能不会有多大效果。

相关文章：