JavaScript字符串相等性能比较

Question

我有一个noob javascript问题。假设我们有两个非常大的字符串（〜百万字符或更多）是相同的 - 它们具有相同的长度和相同的内容。假设我们有这两个函数都做同样的事情（比较字符串）：

function equals1(a, b) {
    return a === b;
}

function equals2(a, b) {
    if (a.length !== b.length) {
           return false;
    }
    for (var i = 0; i < a.length; ++i) {
        if (a[i] !== b[i]) {
            return false;
         }
    }
    return true;
}

为什么第一个函数（equals1（））几乎是第二个函数的两倍？如何改进第二个，使其表现与第一个一样好？

Answer 1

第一个做同样的事情。如果字符串长度不同，则返回false。然后它检查相同索引处的字符是否相同。但是，它是在JS实现级别实现的，因此它的运行速度与C，C ++，Java或编写JavaScript实现的任何语言一样快。

Answer 2

第一个函数更快，因为它不必检查i < a.length是否有一百万次，并且在i上执行一百万次递增操作。

Answer 3

根据ECMAScript委员会的一个人，很可能Javascript正在进行字符串实习（Do common JavaScript implementations use string interning?）。我认为那时===将是O（1）但是基于原始海报的性能测试，它是O（n），因为双倍的字符串使得相等的时间加倍。不用字符串实习真的很难过它们应该如此。

更新：JSPerf

原始海报声称应该支持O（N）复杂性来自http://jsperf.com/eqaulity-is-constant-time似乎即使我有16倍大的字符串，时间也不会超过1-2％

因此，请重新考虑我所罢工的事情和你的选票

换一种说法：

当你这样做

var str1 = "stringwithmillionchars"; //stored in address 51242
var str2 = "stringwithmillionchars"; //stored in address 12313

“stringwithmillionchars”将被存储一次，比如说地址201012的内存，str1和str2都将“指向此地址201012.这个地址可以通过某种散列来确定，映射到内存中的特定位置。

这样做的时候

"stringwithmillionchars"==="stringwithmillionchars"

看起来像

getContentOfAddress(51242)===getContentOfAddress(12313)

或者201012 === 201012

需要O（1）/恒定时间

示例中的for循环（equals2（））具有O（N）时间，其中N是两个字符串的长度。这是因为它必须在每对字符之间进行N次比较，并在i和str.length之间进行N次比较。

注意：地址编号是随机选择的，用于说明目的。

重要提示：基于我的问题（Why Javascript ===/== string equality sometimes has constant time complexity and some times has linear time complexity）的性能比较，只有当字符串直接用引号分配时才会发生实际情况，否则比较将采用线性时间而不是常量，因为char-to-char比较发生。

Answer 4

您可以执行以下操作，使equals2功能速度提高两倍：

function equals2(a, b) {
    if (a.length !== b.length) {
           return false;
    }
    for (var i = 0; i < a.length/2; ++i) {
        if (a[i] !== b[i] || a[a.length-i-1] !== b[b.length-i-1]) {
            return false;
         }
    }
    return true;
}