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/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-进行字符比较。