为什么Javascript ===/==字符串相等有时具有恒定的时间复杂度，有时却具有线性的时间复杂度? [英] Why Javascript ===/== string equality sometimes has constant time complexity and sometimes has linear time complexity?
问题描述
我发现常见/最新的Javascript实现正在使用String Interning来提高性能(
After I found that the common/latest Javascript implementations are using String Interning for perfomance boost (Do common JavaScript implementations use string interning?), I thought === for strings would get the constant O(1) time. So I gave a wrong answer to this question:
由于根据该问题的OP，所以它是O(N)，因此将字符串输入加倍会使相等所需的时间加倍.他没有提供任何jsPerf，因此需要更多调查，
Since according to the OP of that question it is O(N), doubling the string input doubles the time the equality needs. He didn't provide any jsPerf so more investigation is needed,
所以我使用字符串实习的方案是:
var str1 ="stringwithmillionchars";//存储在地址51242中
var str2 ="stringwithmillionchars";//存储在地址12313
一旦让我们说"stringwithmillionchars"存储在内存的地址201012中并且str1和str2都将指向"该地址201012.然后可以通过某种哈希来确定该地址，以映射到内存中的特定位置.
The "stringwithmillionchars" would be stored once let's say in address 201012 of memory and both str1 and str2 would be "pointing" to this address 201012. This address could then be determined with some kind of hashing to map to specific locations in memory.
所以做
"stringwithmillionchars" ==="stringwithmillionchars"
看起来像
getContentOfAddress(51242)=== getContentOfAddress(12313)
或 201012 === 201012
这将花费O(1)/恒定时间
which would take O(1)/constant time
JSPerfs/性能更新:
JSPerf似乎显示恒定时间，即使字符串长16倍?请看看:
JSPerf seems to show constant time even if the string is 16 times longer?? Please have a look:
http://jsperf.com/eqaulity-is-constant-time
上面的字符串可能太小:这可能显示线性时间(由于sergioFC)，字符串是通过循环构建的.我尝试不使用函数-仍然是线性时间/我对其进行了一些更改 http://jsfiddle.net/f8yf3c7d/3/.
Probably the strings are too small on the above: This probably show linear time (thanks to sergioFC) the strings are built with a loop. I tried without functions - still linear time / I changed it a bit http://jsfiddle.net/f8yf3c7d/3/ .
根据 https://www.dropbox.com/s/8ty3hev1b109qjj/compare.html?dl=0 (sergioFC制作的12MB文件)，当您有字符串并且已经为引号分配了值时，无论t1和t2有多大(例如5930496个字符)，它花了0-1毫秒/即时时间.
According to https://www.dropbox.com/s/8ty3hev1b109qjj/compare.html?dl=0 (12MB file that sergioFC made) when you have a string and you already have assigned the value in quotes no matter how big the t1 and t2 are (e.g 5930496 chars), it is taking it 0-1ms/instant time.
似乎当您使用for循环或函数构建字符串时，该字符串不会被中断.因此，仅当您直接使用诸如 var str ="test";
It seems that when you build a string using a for loop or a function then the string is not interned. So interning happens only when you directly assign a string with quotes like var str = "test";
推荐答案
基于字符串a和b的所有性能测试(请参见原始文章)，操作 a === b 需执行以下操作:
Based on all the Performance Tests (see original post) for strings a and b the operation a === b takes:
-
恒定时间O(1)(如果字符串已插入).从示例中看来，实习仅在仅发生于直接分配的字符串，如
var str ="test";；如果不是使用for循环或函数通过串联构建的，则不会发生.
constant time O(1) if the strings are interned. From the examples it seems that interning only happens with directly assigned strings like
var str = "test";and not if you build it with concatenation using for-loops or functions.
线性时间O(N)，因为在所有其他情况下，将首先比较两个字符串的长度.如果相等，则我们进行逐字符比较.当然，它们不相等.N是字符串的长度.
linear time O(N) since in all the other cases the length of the two strings is compared first. If it is equal then we have character by character comparison. Else of course they are not equal. N is the length of the string.
这篇关于为什么Javascript ===/==字符串相等有时具有恒定的时间复杂度，有时却具有线性的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
