题 \ d效率低于[0-9]


我昨天在有人用过的答案上发表了评论 [0123456789] 在一个 正则表达式 而不是 [0-9] 要么 \d。我说使用范围或数字说明符比使用字符集更有效。

我今天决定对它进行测试并发现我的意外(至少在C#正则表达式引擎中) \d 看起来效率低于其他两个似乎差别不大的其他两个。这是我的测试输出超过10000随机字符串1000个随机字符,其中5077实际上包含一个数字:

Regular expression \d           took 00:00:00.2141226 result: 5077/10000
Regular expression [0-9]        took 00:00:00.1357972 result: 5077/10000  63.42 % of first
Regular expression [0123456789] took 00:00:00.1388997 result: 5077/10000  64.87 % of first

令我惊讶的是有两个原因:

  1. 我原以为这个范围比套装更有效。
  2. 我不明白为什么 \d 比...差 [0-9]。还有更多 \d 而不仅仅是简写 [0-9]

这是测试代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace SO_RegexPerformance
{
    class Program
    {
        static void Main(string[] args)
        {
            var rand = new Random(1234);
            var strings = new List<string>();
            //10K random strings
            for (var i = 0; i < 10000; i++)
            {
                //Generate random string
                var sb = new StringBuilder();
                for (var c = 0; c < 1000; c++)
                {
                    //Add a-z randomly
                    sb.Append((char)('a' + rand.Next(26)));
                }
                //In roughly 50% of them, put a digit
                if (rand.Next(2) == 0)
                {
                    //Replace one character with a digit, 0-9
                    sb[rand.Next(sb.Length)] = (char)('0' + rand.Next(10));
                }
                strings.Add(sb.ToString());
            }

            var baseTime = testPerfomance(strings, @"\d");
            Console.WriteLine();
            var testTime = testPerfomance(strings, "[0-9]");
            Console.WriteLine("  {0:P2} of first", testTime.TotalMilliseconds / baseTime.TotalMilliseconds);
            testTime = testPerfomance(strings, "[0123456789]");
            Console.WriteLine("  {0:P2} of first", testTime.TotalMilliseconds / baseTime.TotalMilliseconds);
        }

        private static TimeSpan testPerfomance(List<string> strings, string regex)
        {
            var sw = new Stopwatch();

            int successes = 0;

            var rex = new Regex(regex);

            sw.Start();
            foreach (var str in strings)
            {
                if (rex.Match(str).Success)
                {
                    successes++;
                }
            }
            sw.Stop();

            Console.Write("Regex {0,-12} took {1} result: {2}/{3}", regex, sw.Elapsed, successes, strings.Count);

            return sw.Elapsed;
        }
    }
}

1124
2018-05-18 07:18


起源


也许 \d 处理区域设置。例如。希伯来语使用数字字母。 - Barmar
有关: stackoverflow.com/a/6479605/674039 - wim
这是一个有趣的问题,正是因为 \d 在不同的语言中并不意味着相同的事情。例如,在Java中 \d 确实只匹配0-9 - Ray Toal
@Barmar Hebrew通常不使用字母数字,而是使用相同的拉丁数字数字[0-9]。字母可以替换数字,但这是一种罕见的用途,并保留用于特殊术语。我不希望正则表达式解析器匹配 כ"גיורדיסירה (כ"ג是23的替代品。)另外,从新浪伊拉瓦尼安的答案可以看出,希伯来字母并不是\ d的有效匹配。 - Yuval Adam
将Weston的代码移植到Java产生: - Regex \ d花了00:00:00.043922结果:4912/10000 - Regex [0-9]花了00:00:00.073658结果:4912/10000 167%的第一个 - Regex [ 0123456789]截止00:00:00.085799结果:4912/10000第一名195% - Lunchbox


答案:


\d 检查所有Unicode数字,同时 [0-9] 限于这10个字符。例如, 波斯语 数字, ۱۲۳۴۵۶۷۸۹,是与之匹配的Unicode数字的示例 \d, 但不是 [0-9]

您可以使用以下代码生成所有此类字符的列表:

var sb = new StringBuilder();
for(UInt16 i = 0; i < UInt16.MaxValue; i++)
{
    string str = Convert.ToChar(i).ToString();
    if (Regex.IsMatch(str, @"\d"))
        sb.Append(str);
}
Console.WriteLine(sb.ToString());

哪个产生:

012345678901234567890123456789߀߁߂߃߄߅߆߇߈߉012345678901২345678901234567890123456789୦୧୨୩୪୫୬୭୮୯0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789᠐᠑᠒᠓᠔᠕᠖᠗᠘᠙᥆᥇᥈᥉᥊᥋᥌᥍᥎᥏᧐᧑᧒᧓᧔᧕᧖᧗᧘᧙᭐᭑᭒᭓᭔᭕᭖᭗᭘᭙᮰᮱᮲᮳᮴᮵᮶᮷᮸᮹᱀᱁᱂᱃᱄᱅᱆᱇᱈᱉᱐᱑᱒᱓᱔᱕᱖᱗᱘᱙꘠꘡꘢꘣꘤꘥꘦꘧꘨꘩꣐꣑꣒꣓꣔꣕꣖꣗꣘꣙꤀꤁꤂꤃꤄꤅꤆꤇꤈꤉꩐꩑꩒꩓꩔꩕꩖꩗꩘꩙0123456789


1467
2018-05-18 07:24



这是一个更完整的数字列表,不是0-9: fileformat.info/info/unicode/category/Nd/list.htm - Robert McKee
@weston Unicode有17个平面,每个平面16位。最重要的角色是基本的平面,但是一些特殊的角色,大多数是中国人,都在补充的平面上。处理C#中的那些有点烦人。 - CodesInChaos
@RobertMcKee:Nitpick:完整的unicode字符集实际上是21位(每个16位的17个平面)。但是当然21位数据类型是不切实际的,所以如果你使用2的幂数据类型,那么你需要32位。 - sleske
根据 这篇维基百科文章,Unicode Consortium已声明1,114,112代码点(0到0x010FFFF)的限制永远不会改变。它链接到unicode.org,但我没有在那里找到声明(我可能只是错过了它)。 - Keith Thompson
它永远不会被改变 - 直到他们需要改变它。 - Robert McKee


感谢ByteBlast在文档中注意到这一点。只需更改正则表达式构造函数:

var rex = new Regex(regex, RegexOptions.ECMAScript);

提供新的时间:

Regex \d           took 00:00:00.1355787 result: 5077/10000
Regex [0-9]        took 00:00:00.1360403 result: 5077/10000  100.34 % of first
Regex [0123456789] took 00:00:00.1362112 result: 5077/10000  100.47 % of first

250
2018-05-18 09:37



什么是 RegexOptions.ECMAScript 做? - this.lau_
从 正则表达式选项:“为表达式启用符合ECMAScript的行为。” - chrisaycock
实际上,我认为它取消了对Unicode的支持。 - 0xFE
@ 0xFE:不完全。 Unicode转义仍然有效 ECMAScript (\u1234)。它只是改变意义的速记字符类(就像 \d)以及消失的Unicode属性/脚本缩写(如 \p{N})。 - Tim Pietzcker
这不是“为什么”部分的答案。这是一个“修复症状”的答案。仍然有价值的信息 - usr


正则表达式中的“\ d”是指数字吗?

[0-9] 不等于 \d[0-9] 只匹配 0123456789 人物,而 \d 火柴 [0-9] 和其他数字字符,例如东部阿拉伯数字 ٠١٢٣٤٥٦٧٨٩


106
2018-05-18 07:27



根据: msdn.microsoft.com/en-us/library/20bw873z.aspx  If ECMAScript-compliant behavior is specified, \d is equivalent to [0-9]. - User 12345678
嗯,我错了,或者链接中的这个句子正好相反。 “\ d匹配任何十进制数字。它等同于\ p {Nd}正则表达式模式,它包括标准的十进制数字0-9以及许多其他字符集的十进制数字。” - İsmet Alkan
@ByteBlast谢谢,使用构造函数: var rex = new Regex(regex, RegexOptions.ECMAScript); 使它们在性能方面几乎无法区分。 - weston
哦,无论如何,谢谢大家。这个问题对我来说是一个很好的学习。 - İsmet Alkan
请不要“只是复制”其他问题的答案。如果问题是重复的,请将其标记为此类。 - BoltClock♦


一个补充 最佳答案 从 新浪伊拉维亚人,这是一个.NET 4.5版本(因为只有那个版本支持UTF16输出,c.f。前三行),他的代码, 使用全范围的Unicode代码点。 由于缺乏对更高Unicode平面的适当支持,许多人并不知道总是检查并包括上层Unicode平面。然而,他们有时确实包含一些重要人物。

更新

以来 \d 在正则表达式中不支持非BMP字符(谢谢 萨那托斯),这里是一个使用Unicode字符数据库的版本

public static void Main()
{
    var unicodeEncoding = new UnicodeEncoding(!BitConverter.IsLittleEndian, false);
    Console.InputEncoding = unicodeEncoding;
    Console.OutputEncoding = unicodeEncoding;

    var sb = new StringBuilder();
    for (var codePoint = 0; codePoint <= 0x10ffff; codePoint++)
    {
        var isSurrogateCodePoint = codePoint <= UInt16.MaxValue 
               && (  char.IsLowSurrogate((char) codePoint) 
                  || char.IsHighSurrogate((char) codePoint)
                  );

        if (isSurrogateCodePoint)
            continue;

        var codePointString = char.ConvertFromUtf32(codePoint);

        foreach (var category in new []{
        UnicodeCategory.DecimalDigitNumber,
            UnicodeCategory.LetterNumber,
            UnicodeCategory.OtherNumber})
        {
        sb.AppendLine($"{category}");
            foreach (var ch in charInfo[category])
        {
                sb.Append(ch);
            }
            sb.AppendLine();
        }
    }
    Console.WriteLine(sb.ToString());

    Console.ReadKey();
}

产生以下输出:

DecimalDigitNumber   012345678901234567890123456789߀߁߂߃߄߅߆߇߈߉012345678901২345678901234567890123456789୦୧୨୩୪୫୬୭୮୯0123456789012345678901234567890123456789෦෧෨෩෪෫෬෭෮෯012345678901234567890123456789012345678901234567890123456789᠐᠑᠒᠓᠔᠕᠖᠗᠘᠙᥆᥇᥈᥉᥊᥋᥌᥍᥎᥏᧐᧑᧒᧓᧔᧕᧖᧗᧘᧙᪀᪁᪂᪃᪄᪅᪆᪇᪈᪉᪐᪑᪒᪓᪔᪕᪖᪗᪘᪙᭐᭑᭒᭓᭔᭕᭖᭗᭘᭙᮰᮱᮲᮳᮴᮵᮶᮷᮸᮹᱀᱁᱂᱃᱄᱅᱆᱇᱈᱉᱐᱑᱒᱓᱔᱕᱖᱗᱘᱙꘠꘡꘢꘣꘤꘥꘦꘧꘨꘩꣐꣑꣒꣓꣔꣕꣖꣗꣘꣙꤀꤁꤂꤃꤄꤅꤆꤇꤈꤉꧐꧑꧒꧓꧔꧕꧖꧗꧘꧙꧰꧱꧲꧳꧴꧵꧶꧷꧸꧹꩐꩑꩒꩓꩔꩕꩖꩗꩘꩙ ꯰꯱꯲꯳꯴꯵꯶꯷꯸꯹0123456789𐒠𐒡𐒢𐒣𐒤𐒥𐒦𐒧𐒨𐒩𑁦𑁧𑁨𑁩𑁪𑁫𑁬𑁭𑁮𑁯𑃰𑃱𑃲𑃳𑃴𑃵𑃶𑃷𑃸𑃹𑄶𑄷𑄸𑄹𑄺𑄻𑄼𑄽𑄾𑄿𑇐𑇑𑇒𑇓𑇔𑇕𑇖𑇗𑇘𑇙𑋰𑋱𑋲𑋳𑋴𑋵𑋶𑋷𑋸𑋹𑓐𑓑𑓒𑓓𑓔𑓕𑓖𑓗𑓘𑓙𑙐𑙑𑙒𑙓𑙔𑙕𑙖𑙗𑙘𑙙𑛀𑛁𑛂𑛃𑛄𑛅𑛆𑛇𑛈𑛉𑜰𑜱𑜲𑜳𑜴𑜵𑜶𑜷𑜸𑜹𑣠𑣡𑣢𑣣𑣤𑣥𑣦𑣧𑣨𑣩𖩠𖩡𖩢𖩣𖩤𖩥𖩦𖩧𖩨𖩩𖭐𖭑𖭒𖭓𖭔𖭕𖭖𖭗𖭘𖭙𝟎𝟏𝟐𝟑𝟒𝟓𝟔𝟕𝟖𝟗𝟘𝟙𝟚𝟛𝟜𝟝𝟞𝟟𝟠𝟡𝟢𝟣𝟤𝟥𝟦𝟧𝟨𝟩𝟪𝟫𝟬𝟭𝟮𝟯𝟰𝟱𝟲𝟳𝟴𝟵𝟶𝟷𝟸𝟹𝟺𝟻𝟼𝟽𝟾𝟿

LetterNumber

ᛮᛯᛰⅠⅡⅢⅣⅤⅥⅦⅧⅨⅩⅪⅫⅬⅭⅮⅯⅰⅱⅲⅳⅴⅵⅶⅷⅸⅹⅺⅻⅼⅽⅾⅿↀↁↂↅↆↇↈ〇〡〢〣〤〥〦〧〨〩〸〹〺ꛦꛧꛨꛩꛪꛫꛬꛭꛮꛯ𐅀𐅁𐅂𐅃𐅄𐅅𐅆𐅇𐅈𐅉𐅊𐅋𐅌𐅍𐅎𐅏𐅐𐅑𐅒𐅓𐅔𐅕𐅖𐅗𐅘𐅙𐅚𐅛𐅜𐅝𐅞𐅟𐅠𐅡𐅢𐅣𐅤𐅥𐅦𐅧𐅨𐅩𐅪𐅫𐅬𐅭𐅮𐅯𐅰𐅱𐅲𐅳𐅴𐍁𐍊𐏑𐏒𐏓𐏔𐏕𒐀𒐁𒐂𒐃𒐄𒐅𒐆𒐇𒐈𒐉𒐊𒐋𒐌𒐍𒐎𒐏𒐐𒐑𒐒𒐓𒐔𒐕𒐖𒐗𒐘𒐙𒐚𒐛𒐜𒐝𒐞𒐟𒐠𒐡𒐢𒐣𒐤𒐥𒐦𒐧𒐨𒐩𒐪𒐫𒐬𒐭𒐮𒐯𒐰𒐱𒐲𒐳𒐴𒐵𒐶𒐷𒐸𒐹𒐺𒐻𒐼𒐽𒐾𒐿𒑀𒑁𒑂𒑃𒑄𒑅𒑆𒑇𒑈𒑉𒑊𒑋𒑌𒑍𒑎𒑏𒑐𒑑𒑒𒑓𒑔𒑕𒑖𒑗𒑘𒑙𒑚𒑛𒑜𒑝𒑞𒑟𒑠𒑡𒑢𒑣𒑤𒑥𒑦𒑧𒑨𒑩𒑪𒑫𒑬𒑭𒑮

OtherNumber   ²³¹¼½¾৴৵৶.৸৹୲୳୴୵୶୷௰௱௲౸౹౺౻౼౽౾൰൱൲൳൴൵༪༫༬༭༮༯༰༱༲༳፩፪፫፬፭፮፯፰፱፲፳፴፵፶፷፸፹፺፻፼៰៱៲៳៴៵៶៷៸៹᧚⁰⁴⁵⁶⁷⁸⁹₀₁₂₃₄₅₆₇₈₉⅐⅑⅒⅓⅔⅕⅖⅗⅘⅙⅚⅛⅜⅝⅞⅟↉①②③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾⑿⒀⒁⒂⒃⒄⒅⒆⒇⒈⒉⒊⒋⒌⒍⒎⒏⒐⒑⒒⒓⒔⒕⒖⒗⒘⒙⒚⒛⓪⓫⓬⓭⓮⓯⓰⓱⓲⓳⓴⓵⓶⓷⓸⓹⓺⓻⓼⓽⓾⓿❶❷❸❹❺❻❼❽❾❿➀➁➂➃➄➅➆➇➈➉➊➋➌➍➎➏➐➑➒➓⳽㆒㆓㆔㆕㈠㈡㈢㈣㈤㈥㈦㈧㈨㈩㉈㉉㉊㉋㉌㉍㉎㉏㉑㉒㉓㉔㉕㉖㉗㉘㉙㉚㉛㉜㉝㉞㉟㊀㊁㊂㊃㊄㊅㊆㊇㊈㊉㊱㊲㊳㊴㊵㊶㊷㊸㊹㊺㊻㊼㊽㊾㊿꠰꠱꠲꠳꠴꠵𐄇𐄈𐄉𐄊𐄋𐄌𐄍𐄎𐄏𐄐𐄑𐄒𐄓𐄔𐄕𐄖𐄗𐄘𐄙𐄚𐄛𐄜𐄝𐄞𐄟𐄠𐄡𐄢𐄣𐄤𐄥𐄦𐄧𐄨 𐄩𐄪𐄫𐄬𐄭𐄮𐄯𐄰𐄱𐄲𐄳𐅵𐅶𐅷𐅸𐆊𐆋𐋡𐋢𐋣𐋤𐋥𐋦𐋧𐋨𐋩𐋪𐋫𐋬𐋭𐋮𐋯𐋰𐋱𐋲𐋳𐋴𐋵𐋶𐋷𐋸𐋹𐋺𐋻𐌠𐌡𐌢𐌣𐡘𐡙𐡚𐡛𐡜𐡝𐡞𐡟𐡹𐡺𐡻𐡼𐡽𐡾𐡿𐢧𐢨𐢩𐢪𐢫𐢬𐢭𐢮𐢯𐣻𐣼𐣽𐣾𐣿𐤖𐤗𐤘𐤙𐤚𐤛𐦼𐦽𐧀𐧁𐧂𐧃𐧄𐧅𐧆𐧇𐧈𐧉𐧊𐧋𐧌𐧍𐧎𐧏𐧒𐧓𐧔𐧕𐧖𐧗𐧘𐧙𐧚𐧛𐧜𐧝𐧞𐧟𐧠𐧡𐧢𐧣𐧤𐧥𐧦𐧧𐧨𐧩𐧪𐧫𐧬𐧭𐧮𐧯𐧰𐧱𐧲𐧳𐧴𐧵𐧶𐧷𐧸𐧹𐧺𐧻𐧼𐧽𐧾𐧿𐩀𐩁𐩂𐩃𐩄𐩅𐩆𐩇𐩽𐩾𐪝𐪞𐪟𐫫𐫬𐫭𐫮𐫯𐭘𐭙𐭚𐭛𐭜𐭝𐭞𐭟𐭸𐭹𐭺𐭻𐭼𐭽𐭾𐭿𐮩𐮪𐮫𐮬𐮭𐮮𐮯𐳺𐳻𐳼𐳽𐳾𐳿𐹠𐹡𐹢𐹣𐹤𐹥𐹦𐹧𐹨𐹩𐹪𐹫𐹬𐹭𐹮𐹯𐹰𐹱𐹲𐹳𐹴𐹵𐹶𐹷𐹸𐹹𐹺𐹻𐹼𐹽𐹾𑁒𑁓𑁔𑁕𑁖𑁗𑁘𑁙𑁚𑁛𑁜𑁝𑁞𑁟𑁠𑁡𑁢𑁣𑁤𑁥𑇡𑇢𑇣𑇤𑇥 𑇦𑇧𑇨𑇩𑇪𑇫𑇬𑇭𑇮𑇯𑇰𑇱𑇲𑇳𑇴𑜺𑜻𑣪𑣫𑣬𑣭𑣮𑣯𑣰𑣱𑣲𖭛𖭜𖭝𖭞𖭟𖭠𖭡𝍠𝍡𝍢𝍣𝍤𝍥𝍦𝍧𝍨𝍩𝍪𝍫𝍬𝍭𝍮𝍯𝍰𝍱𞣇𞣈𞣉𞣊𞣋𞣌𞣍𞣎𞣏🄀🄁🄂🄃🄄🄅🄆🄇🄈🄉🄊🄋🄌


14
2017-09-13 08:24



令人遗憾的是,Win32控制台不显示星体字符 - Sebastian
如果我记得很清楚,遗憾的是在.NET中 Regex 不支持非BMP字符。所以最后用正则表达式检查字符> 0xffff是没用的。 - xanatos


\ d检查所有Unicode,而[0-9]仅限于这10个字符。 如果只有10位数,你应该使用。 其他我推荐使用\ d,因为写得少。


0
2018-03-11 10:27





\d 效率会降低,因为必须进行转换才能进行比较。

例如,如果我希望Regex找到IP地址,我宁愿我们 \d 比 [0123456789] 甚至 [0-9] 代表任何数字。

一般来说在我的正则表达式中使用,功能如果比速度更重要。


-14
2018-02-08 20:56



虽然这可能会产生一个小的损失,但在将模式与任何输入字符串进行比较之前,可以执行一次。所以,时间复杂性是 O(1)不是 O(n),(其中 n 是输入字符串的长度。)简而言之,影响最小。 - jpaugh