如何有效地检测字符串中的代理对？

Question

我需要检测数十万个不同长度的字符串中的代理对。

我想知道什么是最快、最有效的方法来做到这一点。

    string srcString = " = ";
    var hasSurrogate = srcString.Any(c => '\uD800' <= c && c <= '\uDFFF');

Any其 O(n) 速度运行良好，但也许有更有效的方法来做到这一点

Answer 1

你无法克服复杂性，O(N)因为你必须检查每个角色。但是你可以通过使用循环来显着加快速度Span<Char>- 我所说的“显着”是指速度快 10 倍以上。

我能想到的最快的方法是：

static bool searchUsingSpanIsSurrogate(string s)
{
    var span = s.AsSpan();

    foreach (var c in span)
    {
        if (char.IsSurrogate(c))
            return true;
    }

    return false;
}

出于兴趣，我尝试了几种不同的方法。这是基准：

using System;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace Demo;

public class Program
{
    public static void Main()
    {
        var summary = BenchmarkRunner.Run<UnderTest>();
    }
}

public class UnderTest
{
    [Benchmark]
    public void SearchUsingLinq()
    {
        _ = searchUsingLinq(_haystack);
    }

    [Benchmark]
    public void SearchUsingSpan()
    {
        _ = searchUsingSpan(_haystack);
    }

    [Benchmark]
    public void SearchUsingLinqIsSurrogate()
    {
        _ = searchUsingLinqIsSurrogate(_haystack);
    }

    [Benchmark]
    public void SearchUsingSpanIsSurrogate()
    {
        _ = searchUsingSpanIsSurrogate(_haystack);
    }

    [Benchmark]
    public void SearchUsingIndexedIsSurrogate()
    {
        _ = searchUsingIndexedIsSurrogate(_haystack);
    }

    [Benchmark]
    public void SearchUsingLoop()
    {
        _ = searchUsingLoop(_haystack);
    }

    [Benchmark]
    public void SearchUsingLoopIsSurrogate()
    {
        _ = searchUsingLoop(_haystack);
    }

    static bool searchUsingLinq(string s)
    {
        return s.Any(c => '\uD800' <= c && c <= '\uDFFF');
    }

    static bool searchUsingSpan(string s)
    {
        var span = s.AsSpan();

        foreach (var c in span)
        {
            if ('\uD800' <= c && c <= '\uDFFF')
                return true;
        }

        return false;
    }

    static bool searchUsingLinqIsSurrogate(string s)
    {
        return s.Any(char.IsSurrogate);
    }

    static bool searchUsingSpanIsSurrogate(string s)
    {
        var span = s.AsSpan();

        foreach (var c in span)
        {
            if (char.IsSurrogate(c))
                return true;
        }

        return false;
    }

    static bool searchUsingIndexedIsSurrogate(string s)
    {
        for (int i = 0; i < s.Length; ++i)
        {
            if (char.IsSurrogate(s, i))
                return true;
        }

        return false;
    }

    static bool searchUsingLoop(string s)
    {
        foreach (var c in s)
        {
            if ('\uD800' <= c && c <= '\uDFFF')
                return true;
        }

        return false;
    }

    static bool searchUsingLoopIsSurrogate(string s)
    {
        foreach (var c in s)
        {
            if (char.IsSurrogate(c))
                return true;
        }

        return false;
    }

    readonly string _haystack = new string('X', 100_000);
}

结果如下：

|                        Method |      Mean |     Error |    StdDev |    Median |
|------------------------------ |----------:|----------:|----------:|----------:|
|               SearchUsingLinq | 626.05 us |  9.130 us |  8.094 us | 625.55 us |
|               SearchUsingSpan | 102.21 us |  1.851 us |  1.732 us | 101.94 us |
|    SearchUsingLinqIsSurrogate | 746.70 us | 17.373 us | 49.284 us | 735.55 us |
|    SearchUsingSpanIsSurrogate |  53.00 us |  1.260 us |  3.675 us |  51.85 us |
| SearchUsingIndexedIsSurrogate |  62.64 us |  2.638 us |  7.736 us |  58.60 us |
|               SearchUsingLoop |  64.02 us |  1.581 us |  4.537 us |  62.19 us |
|    SearchUsingLoopIsSurrogate |  62.79 us |  1.228 us |  3.103 us |  61.47 us |

看起来您使用哪种非 Linq 方法并不重要，因为它们的性能都非常接近。如果您想要最大性能，请不要使用 Linq，因为使用委托的开销相当高。

Answer 2

你能做的最好的事情就是衡量。有几个实现并对它们进行基准测试。我比较了使用Any()与for. 一个简单的for循环速度快了 10 倍。

方法	意思是	错误	标准差
有代理人	8,095.7 纳秒	160.38纳秒	230.01纳秒
有代理人	765.8纳秒	14.19纳秒	13.27纳秒

我使用BenchmarkDotNet和这个简单的代码：

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace PerfTests.Console;

public class Program
{
    public static void Main(string[] args)
    {
        var summary = BenchmarkRunner.Run<SurrogateBenchmark>();
    }
}

public class SurrogateBenchmark
{
    private static string test = "".PadRight(1000) + " = ";

    [Benchmark]
    public bool HasSurrogateAny()
    {
        return test.Any(c => '\uD800' <= c && c <= '\uDFFF');
    }

    [Benchmark]
    public bool HasSurrogateFor()
    {
        for (int i = 0; i < test.Length; i++)
        {
            char c = test[i];
            if ('\uD800' <= c && c <= '\uDFFF') return true;
        }
        return false;
    }
}

请注意，我在实际代理项之前添加了 1000 个空格，以便算法有一些工作要做，并且不会遇到代理项作为字符串中的第一个字符。

环境：.NET 6.0.7、Intel Xeon Gold 16核2.4 GHz、WS2019虚拟机

事实证明， aforeach提供了基本相同的性能，以及一个更易读的版本，它使用Char.IsSurrogate()：

方法	意思是	错误	标准差
有代理人	8,630.1 纳秒	134.03纳秒	125.37纳秒
每个都有代理	770.1纳秒	10.31纳秒	9.14纳秒
具有可读代理	796.0纳秒	13.41纳秒	12.54纳秒
有代理人	773.2纳秒	11.46纳秒	10.72纳秒

最后，在我的设置中，使用 a forover a 的版本Span<char>实际上要慢一些：

方法	意思是	错误	标准差
有代理人	764.1纳秒	12.99纳秒	11.52纳秒
具有跨度代理	803.7纳秒	15.95纳秒	21.30纳秒

其余三个测试的代码：

[Benchmark]
public bool HasSurrogateForEach()
{
    foreach (char c in test)
    {
        if ('\uD800' <= c && c <= '\uDFFF') return true;
    }
    return false;
}

[Benchmark]
public bool HasSurrogateForReadable()
{
    for (int i = 0; i < test.Length; i++)
    {
        char c = test[i];
        if (Char.IsSurrogate(c)) return true;
    }
    return false;
}

[Benchmark]
public bool HasSurrogateForSpan()
{
    var s = test.AsSpan();
    for (int i = 0; i < s.Length; i++)
    {
        char c = test[i];
        if ('\uD800' <= c && c <= '\uDFFF') return true;
    }
    return false;
}