JavaScript 字符串相等性能比较

Question

我有一个菜鸟 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

根据 ECMAScript 委员会的一位人士的说法，最有可能的 Javascript 正在执行字符串实习（Do common JavaScript implementations use string interning？）。我认为然后 === 将是 O(1) 但基于原始海报的性能测试它是 O(n) 因为将字符串加倍会使相等的时间加倍.. 没有使用字符串实习真的很遗憾他们应该是这样的。

更新：JSPerf

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

所以请重新考虑我删除的那些事情和你的反对票

换句话说：

当你做

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

一旦假设在内存的地址 201012 中，“stringwithmillionchars”将被存储，并且 str1 和 str2 都将“指向这个地址 201012。这个地址可以通过某种哈希确定以映射到内存中的特定位置。

所以在做的时候

"stringwithmillionchars"==="stringwithmillionchars"

看起来像

getContentOfAddress(51242)===getContentOfAddress(12313)

或者 201012 === 201012

这需要 O(1)/恒定时间

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

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

重要：基于我的问题中的性能比较（为什么 Javascript ===/== 字符串相等有时具有恒定的时间复杂度，有时具有线性时间复杂度）仅当字符串直接用引号分配时才会发生实习，否则比较将采用线性时间而不是常数，因为发生了字符到字符的比较。