我需要检测数十万个不同长度的字符串中的代理对。
我想知道最快、最有效的方法是什么。
string srcString = "𝜺𝜺 = 𝟏";
var hasSurrogate = srcString.Any(c => '\uD800' <= c && c <= '\uDFFF');
Any
其 O(n) 速度运行良好,但也许有更有效的方法来做到这一点
你无法克服
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,因为使用委托的开销相当高。
您能做的最好的事情就是测量。有几个实现并对它们进行基准测试。我比较了使用
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;
}
我创建了一个通用 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;
}