Javascript 的字符串比较在底层是如何工作的？

Question

为什么无论字符串长度如何，比较运算符都运行得更快？

考虑以下两个我用来比较长度为 1 亿的字符串的函数：

与===:

// O(?)
const compare1(a, b) {
  return a === b;
}

逐字比较：

// O(N)
const compare2(a, b) {
  if(a.length !== b.length) return false;
  const n = Math.max(a.length, b.length);
  for(var i=0; i<n; i++){
    if(a[i] !== b[i]) return false;
  }
  return true;
}

在测试这两个函数时，我发现compare1函数的速度明显更快。

对于 compare2 函数，我认为解释 JavaScript 代码、访问和比较内存的开销会很大。

但是根据我的理解，compare1函数可能还要比较N个字符。它运行这么快是不是因为它都发生在较低的级别？

Answer 1

有两个考虑：

=== 字符串基元的比较是用较低级别的编译代码实现的，它确实比显式 JavaScript 循环执行得更快，后者有额外的工作，包括更新JavaScript 变量 (i)，使用该变量 (a[i]) 执行访问；必须遵循所有规定的 ECMAScript 程序。
JavaScript引擎可以优化内存使用并使用两个字符串相同的知识（例如当已经在解析时间，或者一个字符串被分配给第二个variable/property）并且只存储该字符串一次（参见字符串池）。在那种情况下，比较是两个引用的简单 O(1) 比较。然而，在 JavaScript 中无法检查两个字符串基元是否实际上共享同一内存。

作为第二点的说明，请注意比较长字符串的两种情况的比较时间是如何不同的——这可能暗示正在发生此字符串池：

function compare(a, b) {
    let sum = 0, start, p;
    for (let i = 0; i < 10; i++) { // Perform 10 comparisons
        start = performance.now();
        p = a === b;
        sum += performance.now() - start;
    }
    return sum / 10; // Return average time to make the comparison
}

console.log("Hold on while strings are being created...");
setTimeout(function () {
    // Create long, non-trivial string
    let a = Array.from({length: 10000000}, (_, i) => i).join("");
    let b = a.slice(0); // Plain Copy - engine realises it is the same string & does not allocate space
    let c = a[0] + a.slice(1); // More complex - engine does not realise it is the same string
    console.log("Strings created. Test whether they are equal:", a === b && b === c);
    console.log(compare(a, b) + "ms");
    console.log(compare(a, c) + "ms");
});

Javascript 的字符串比较在底层是如何工作的？

How does Javascript's string comparison work at the lower level?

javascript

string

algorithm

compare

node.js