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

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虚拟机

事实证明，

foreach

提供了基本相同的性能，以及使用

Char.IsSurrogate()

的更具可读性的版本：

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

最后，在我的设置中，使用

for

而非

Span<char>

的版本实际上有点 慢:

方法	意思是	错误	标准偏差
有代理人	764.1 纳秒	12.99 纳秒	11.52 纳秒
HasSurrogateForSpan	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;
}

Answer 3

我创建了一个通用 TextSegment 记录和一个方法SeparateWordsAndEmojis，用于处理输入字符串并将每个字符分类为“文本”或“表情符号”。希望这有帮助

private static List<TextSegment> SeparateWordsAndEmojis(string input)
{
    var segments = new List<TextSegment>();

    var span = input.AsSpan();

    for (var i = 0; i < span.Length; i++)
    {
        if (char.IsSurrogate(span[i]))
        {
            segments.Add(new TextSegment("emoji", char.ConvertFromUtf32(char.ConvertToUtf32(span[i], span[i + 1]))));
            i++;
        }
        else
        {
            segments.Add(new TextSegment("text", span[i].ToString()));
        }
    }

    return segments;
}