8

在我发现常见/最新的 Javascript 实现使用字符串实习来提高性能（常见的 JavaScript 实现是否使用字符串实习？）之后，我认为===字符串会获得恒定的 O(1) 时间。所以我对这个问题给出了错误的答案：

JavaScript 字符串相等性能比较

由于根据该问题的 OP 它是 O(N)，因此将字符串输入加倍会使相等所需的时间加倍。他没有提供任何 jsPerf，因此需要进行更多调查，

所以我使用字符串实习的场景是：

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)/恒定时间

JSPerfs/性能更新：

即使字符串长 16 倍，JSPerf 似乎也显示恒定时间？请看一看：

http://jsperf.com/eqauility-is-constant-time

上面的字符串可能太小了：这可能显示线性时间（感谢 sergioFC）字符串是用循环构建的。我尝试了没有功能 - 仍然是线性时间/我改变了一点http://jsfiddle.net/f8yf3c7d/3/。

根据https://www.dropbox.com/s/8ty3hev1b109qjj/compare.html?dl=0（sergioFC 制作的 12MB 文件），当你有一个字符串并且无论 t1 有多大，你已经用引号分配了值和 t2 是（例如 5930496 个字符），它需要 0-1 毫秒/即时时间。

似乎当您使用 for 循环或函数构建字符串时，该字符串不会被保留。因此，只有当您直接分配带有引号的字符串时才会发生实习var str = "test";

4

3 回答 3

10

基于字符串 a 和 b 的所有性能测试（参见原始帖子），操作a === b需要：

  • 如果字符串被保留，则恒定时间 O(1) 。从这些示例看来，实习似乎只发生在直接分配的字符串上var str = "test";，而不是如果你使用 for 循环或函数通过连接构建它。

  • 线性时间 O(N)，因为在所有其他情况下，首先比较两个字符串的长度。如果相等，则我们进行逐字符比较。否则，它们当然不相等。N 是字符串的长度。

于 2014-10-24T19:19:18.830 回答
3

根据ECMAScript 5.1 规范的 Strict Equal Comparison algorithm，即使被比较的 Objects 的类型是 String，也会检查所有字符是否相等。

  1. 如果Type(x)是String，则返回true 如果x和y是完全相同的字符序列（长度相同，对应位置的字符相同）；否则，返回false。

实习严格来说是一种实现方式，以提高性能。语言标准在这方面没有强加任何规则。因此，是否实习字符串取决于规范的实施者。

于 2014-10-24T14:28:05.260 回答
1

首先，很高兴看到一个 JSPerf 测试证明了将字符串大小加倍会使执行时间加倍的说法。

接下来，让我们认为这是理所当然的。这是我的（未经证实的、未经检查的、可能与现实无关的）理论。

无论引用多少数据，比较两个内存地址都很快。但是你必须先实习这个字符串。如果您的代码中有

var a = "1234";
var b = "1234";

那么引擎首先要明白这两个字符串是一样的，可以指向同一个地址。因此，至少必须对这些字符串进行一次完全比较。所以基本上这里有以下选项：

  • 引擎在解析代码时直接比较和实习字符串。在这种情况下，equals 字符串应该获得相同的地址。
  • 引擎可能会说“这些字符串很大，我不想实习”并且有两个副本。
  • 引擎稍后可能会实习这些字符串。

在后两种情况下，字符串比较会影响测试结果。在最后一种情况下 - 即使字符串最终被拘留。

但正如我所写的，对于理论的圣人来说，这是一个狂野的理论。我首先想看看一些 JSPerf。

于 2014-10-24T14:34:31.303 回答