9

我需要编写一个函数来测试，如果给定的字符串在某种意义上是“空白”，它只包含空格字符。空白字符如下：

'\u0009',
'\u000A',
'\u000B',
'\u000C',
'\u000D',
' ',
'\u0085',
'\u00A0',
'\u1680',
'\u180E',
'\u2000',
'\u2001',
'\u2002',
'\u2003',
'\u2004',
'\u2005',
'\u2006',
'\u2007',
'\u2008',
'\u2009',
'\u200A',
'\u2028',
'\u2029',
'\u202F',
'\u205F',
'\u3000'

该函数将被调用很多次，因此它必须非常非常高效。但不应占用太多内存（例如将每个字符映射到数组中的真/假）。到目前为止我尝试过的事情：

  • 正则表达式 - 性能不太好
  • 修剪并检查长度是否为 0 - 性能不佳，还使用额外的内存来保存修剪后的字符串
  • 根据包含空白字符 ( if (!whitespaceCharactersMap[str[index]]) ...) 的哈希集检查每个字符串字符 - 效果很好

  • 我当前的解决方案使用硬编码比较：

    function(str) {
    var length = str.length;
    if (!length) {
        return true;
    }
    for (var index = 0; index < length; index++)
    {
        var c = str[index];
        if (c === ' ')
        {
            // skip
        }
        else if (c > '\u000D' && c < '\u0085')
        {
            return false;
        }
        else if (c < '\u00A0')
        {
            if (c < '\u0009')
            {
                return false;
            }
            else if (c > '\u0085')
            {
                return false;
            }
        }
        else if (c > '\u00A0')
        {
            if (c < '\u2028')
            {
                if (c < '\u180E')
                {
                    if (c < '\u1680')
                    {
                        return false;
                    }
                    else if(c > '\u1680')
                    {
                        return false;
                    }
                }
                else if (c > '\u180E')
                {
                    if (c < '\u2000')
                    {
                        return false;
                    }
                    else if (c > '\u200A')
                    {
                        return false;
                    }
                }
            }
            else if (c > '\u2029')
            {
                if (c < '\u205F')
                {
                    if (c < '\u202F')
                    {
                        return false;
                    }
                    else if (c > '\u202F')
                    {
                        return false;
                    }
                }
                else if (c > '\u205F')
                {
                    if (c < '\u3000')
                    {
                        return false;
                    }
                    else if (c > '\u3000')
                    {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

这似乎比哈希集（在 Chrome 上测试）快 50-100%。

有人看到或知道更多选择吗？

更新 1

我将在这里回答一些评论：

  • 这不仅仅是检查用户输入是否为空。我必须解析必须单独处理空格的某些数据格式。
  • 值得优化。我之前已经分析过代码。检查空白字符串似乎是一个问题。而且，正如我们所看到的，方法之间的性能差异可能高达 10 倍，这绝对值得付出努力。
  • 一般来说，我发现这个“哈希集 vs. 正则表达式 vs. 切换 vs. 分支”挑战很有教育意义。
  • 对于浏览器和 node.js，我需要相同的功能。

现在这是我对性能测试的看法：

http://jsperf.com/hash-with-comparisons/6

如果你们进行几次这些测试，我将不胜感激。

初步结论：

  • branchlessTest ( a^9*a^10*a^11...) 在 Chrome 和 Firefox 中非常快，但在 Safari 中则不然。从性能角度来看，这可能是 Node.js 的最佳选择。
  • switchTest 在 Chrom 和 Firefox 上也相当快，但令人惊讶的是在 Safari 和 Opera 上最慢
  • 带有 re.test(str) 的正则表达式在任何地方都表现良好，甚至在 Opera 中也是最快的。
  • 散列和分支几乎在所有地方都显示出几乎相同的差结果。对比也差不多，往往性能最差（这可能是实现的原因，check for' '应该是第一个）。

总而言之，就我而言，我将选择以下正则表达式版本：

var re = /[^\s]/;
return !re.test(str);

原因：

  • 无分支版本在 Chrome 和 Firefox 中很酷，但不太便携
  • 在 Safari 中切换太慢
  • 正则表达式似乎在任何地方都表现良好，它们的代码也非常紧凑
4

3 回答 3

7

硬编码解决方案似乎是最好的，但我认为switch应该更快。这取决于 JavaScript 解释器处理这些的方式（大多数编译器非常有效地执行此操作），因此它可能是特定于浏览器的（即，在某些情况下速度很快，在其他情况下速度很慢）。此外，我不确定 JavaScript 使用 UTF 字符串的速度有多快，因此您可以在比较值之前尝试将字符转换为其整数代码。

for (var index = 0; index < length; index++)
{
    var c = str.charCodeAt(index);
    switch (c) {
        case 0x0009: case 0x000A: case 0x000B: case 0x000C: case 0x000D: case 0x0020:
        case 0x0085: case 0x00A0: case 0x1680: case 0x180E: case 0x2000: case 0x2001:
        case 0x2002: case 0x2003: case 0x2004: case 0x2005: case 0x2006: case 0x2007:
        case 0x2008: case 0x2009: case 0x200A: case 0x2028: case 0x2029: case 0x202F:
        case 0x205F: case 0x3000: continue;
    }
    return false;
}

另一件要考虑的事情是改变for：

for (var index in str)
{
    ...
}

编辑

您的 jsPerf 测试得到了一些修订，当前版本在这里可用。我的代码在 Chrome 26 和 27 以及 IE10 中明显更快，但它也是 Firefox 18 中最慢的。

我在 64 位 Linux上的 Firefox 20.0 上运行了相同的测试（我不知道如何让 jsPerf 保存这些），结果证明它是两个最快的测试之一（与 并列trimTest，均约为 11.8M ops/sec ）。我还在WinXP 上测试了 Firefox 20.0.1，但在 VirtualBox 下（仍然在 64 位 Linux 下，这可能在这里产生显着差异），它提供了 10M 操作/秒switchTest，trimTest以 7.3M 操作/秒排在第二位。

所以，我猜测性能取决于浏览器版本和/或什至可能取决于底层操作系统/硬件（我想上面的 FF18 测试是在 Win 上进行的）。无论如何，要制作一个真正的最佳版本，您必须制作多个版本，在所有浏览器、操作系统、架构上测试每个版本……您可以掌握，然后在您的页面中包含最适合的版本对于访问者的浏览器、操作系统、体系结构......不过，我不确定哪种代码值得麻烦。

于 2013-06-09T14:05:20.410 回答
5

由于分支比大多数其他操作要昂贵得多，因此您希望将分支保持在最低限度。因此，您的 if/else 语句序列可能不是很高效。一种主要使用数学的方法会快得多。例如：

在不使用任何分支的情况下执行相等检查的一种方法是使用按位运算。一个例子是，检查 a == b：

a ^ b == 0

由于两个相似位（即 1 ^ 1 或 0 ^ 0）的异或为 0，异或两个相等的值产生 0。这很有用，因为它允许我们将 0 视为“真”值，并做更多数学。想象一下，我们有一堆用这种方式表示的布尔变量：非零数字是假的，零表示真。如果我们想问，“这些都是真的吗？” 我们只是将它们相乘。如果其中任何一个为真（等于零），则整个结果将为零。

因此，例如，代码看起来像这样：

function(str) {
    for (var i = 0; i < str.length; i++) {
        var c = str[i];
        if ((c ^ '\u0009') * (c ^ '\u000A') * (c ^ '\u000B') ... == 0)
            continue;
        return false;
    }
    return true;
}

这比简单地执行以下操作更具性能的主要原因：

if ((c == '\u0009') || (c == '\u000A') || (c == '\u0008') ...)

就是JavaScript有短路布尔操作符，意思是每次使用||操作符时，不仅要进行or操作，还要检查是否能证明该语句到目前为止一定为真，这是一个分支操作，这是昂贵的。另一方面，数学方法不涉及分支，除了 if 语句本身，因此应该快得多。

于 2013-06-09T14:16:26.967 回答
0

这将创建并使用对字符串字符的“哈希”查找，如果它检测到非空格，则返回 false：

var wsList=['\u0009','\u000A','\u000B','\u000C','\u000D',' ','\u0085','\u00A0','\u1680','\u180E','\u2000','\u2001','\u2002','\u2003','\u2004','\u2005','\u2006','\u2007','\u2008','\u2009','\u200A','\u2028','\u2029','\u202F','\u205F','\u3000'];
var ws=Object.create(null);
wsList.forEach(function(char){ws[char]=true});
function isWhitespace(txt){
    for(var i=0, l=txt.length; i<l; ++i){
        if(!ws[txt[i]])return false;
    }
    return true;
}

var test1=" \u1680 \u000B \u2002 \u2004";
isWhitespace(test1);
/*
true
*/
var test2=" _ . a ";
isWhitespace(test2);
/*
false
*/

不确定它的性能（还）。在对 jsperf 进行快速测试后，与使用/^\s*$/.

编辑：

看来您应该采用的解决方案可能取决于您正在使用的数据的性质：数据主要是空白还是非空白？也主要是ASCII范围的文本？您可以通过if对常见的非空白字符范围使用范围检查（通过），switch在最常见的空白上使用，然后对其他所有内容使用哈希查找来加快平均测试用例的速度。如果大多数被测试的数据由最常见的字符（0x0--0x7F 之间）组成，这可能会提高测试的平均性能。

也许这样的事情（if/switch/hash 的混合体）可以工作：

/*same setup as above with variable ws being a hash lookup*/
function isWhitespaceHybrid(txt){
    for(var i=0, l=txt.length; i<l; ++i){
        var cc=txt.charCodeAt(i)
        //above space, below DEL
        if(cc>0x20 && cc<0x7F)return false;
        //switch only the most common whitespace
        switch(cc){
            case 0x20:
            case 0x9:
            case 0xA:
            case 0xD:
            continue;
        }
        //everything else use a somewhat slow hash lookup (execute for non-ascii range text)
        if(!ws[txt[i]])return false;
    }
    return true;
}
于 2013-06-15T19:43:53.073 回答