Superlin的读书笔记

12bet,字符串和正则表达式

12bet,字符串连接

+和+=操作符

str += "one" + "two";

以上方式会使用一个暂存的字符串保存"one" + "two"的结果,然后将暂存的字符串和str拼接并将结果赋值给str。

str += "one";
str += "two";
// 等价于 str = str + "one" + "two";
// 即 str = ((str + "one") + "two");

以上方式在大多数浏览器中要快10%-40%。

除IE 以外,浏览器尝试扩展表达式左端字符串的内存,然后简单地将第二个字符串拷贝到它的尾部。如果在一个循环中,基本字符串位于最左端,就可以避免多次复制一个越来越大的基本字符串。

string concat

12bet,中,连接字符串只是记录下构成新字符串的各部分字符串的引用。当你真正使用连接后的字符串时,各部分字符串才被逐个拷贝到一个新的“真正的”字符串中,然后用它取代先前的字符串引用,所以并非每次使用字符串时都发生合并操作。IE7 和更早的浏览器中,12博体育,每连接一对字符串都要把它们复制到一块新分配的内存中,这样的性能是很差的。

数组拼接

12bet,在大多数浏览器上,数组联结比连接字符串的其他方法更慢,但是事实上,为一种补偿方法,在IE7 和更早的浏览器上它是连接大量字符串唯一高效的途径。

IE7 天真的连接算法要求浏览器在循环过程中反复地为越来越大的字符串拷贝和分配内存。结果是以平方关系递增的运行时间和内存消耗。

当联结一个数组时,12博体育,浏览器分配足够大的内存用于存放整个字符串,也不会超过一次地拷贝最终字符串的同一部分。

concat

这是连接字符串最灵活的方法,因为你可以用它追加一个字符串,或者一次追加几个字符串,或者一个完整的字符串数组。

大多数情况下concat 比简单的+和+=慢一些,而且在IE,Opera 和Chrome 上大幅变慢。此外,虽然使用concat 合并数组中的所有字符串看起来和前面讨论的数组联结差不多,但通常它更慢一些(Opera 除外),而且它还潜伏着灾难性的性能问题,正如IE7 和更早版本中使用+和+=创建大字符串那样。

正则表达式优化

正则表达式工作原理

  1. 编译:当你创建了一个正则表达式对象之后(使用一个正则表达式直接量或者RegExp 构造器),浏览器检查你的模板有没有错误,然后将它转换成一个本机代码例程,用于执行匹配工作。如果你将正则表达式赋给一个变量,你可以避免重复执行此步骤。
  2. 设置起始位置:当一个正则表达式投入使用时,首先要确定目标字符串中开始搜索的位置。它是字符串的起始位置,或者由正则表达式的lastIndex 属性指定,但是当它从第四步返回到这里的时候(因为尝试匹配失败),此位置将位于最后一次尝试起始位置推后一个字符的位置上。
  3. 匹配每个正则表达式的字元:正则表达式一旦找好起始位置,它将一个一个地扫描目标文本和正则表达式模板。当一个特定字元匹配失败时,正则表达式将试图回溯到扫描之前的位置上,然后进入正则表达式其他可能的路径上。
  4. 匹配成功或失败:如果在字符串的当前位置上发现一个完全匹配,那么正则表达式宣布成功。如果正则表达式的所有可能路径都尝试过了,但是没有成功地匹配,那么正则表达式引擎回到第二步,从字符串的下一个字符重新尝试。只有字符串中的每个字符(以及最后一个字符后面的位置)都经历了这样的过程之后,还没有成功匹配,那么正则表达式就宣布彻底失败。

理解回溯

每当正则表达式做出这样的决定,如果有必要的话,它会记住另一个选项,以备将来返回后使用。如果所选方案匹配成功,正则表达式将继续扫描正则表达式模板,如果其余部分匹配也成功了,那么匹配就结束了。但是如果所选择的方案未能发现相应匹配,或者后来的匹配也失败了,正则表达式将回溯到最后一个决策点,然后在剩余的选项中选择一个。它继续这样下去,直到找到一个匹配,或者量词和分支选项的所有可能的排列组合都尝试失败了,那么它将放弃这一过程,然后移动到此过程开始位置的下一个字符上,重复此过程。

下面的例子演示了匹配分支的过程:

/h(ello|appy) hippo/.test("hello there, happy hippo");

example of backtracking

下面的例子展示了重复量词的回溯:

var str = "<p>Para 1.</p>" +
          "<img src='smiley.jpg'>" +
          "<p>Para 2.</p>" +
          "<div>Div.</div>";
/<p>.*</p>/i.test(str);   // 贪婪
/<p>.*?</p>/i.test(str); // 懒惰

greedy and lazy backtracking

回溯失控

当一个正则表达式占用浏览器上秒,上分钟或者更长时间时,问题原因很可能是回溯失控。考虑下面的正则表达式,它的目标是匹配整个HTML 文件。不像其他大多数正则表达式那样,JavaScript 没有选项可使点号匹配任意字符,包括换行符,所以此例中以[sS]匹配任意字符。

/<html>[sS]*?<head>[sS]*?<title>[sS]*?</title>[sS]*?</head>[sS]*?<body>[sS]*?</body>[sS]*?</html>/

此正则表达式匹配正常HTML 字符串时工作良好,但是如果目标字符串缺少一个或多个标签时,它就会变得十分糟糕。例如</html>标签缺失,那么最后一个[sS]*?将扩展到字符串的末尾,因为在那里没有发现</html>标签,然后并没有放弃,正则表达式将察看此前的[sS]*?队列记录的回溯位置,使它们进一步扩大。正则表达式尝试扩展倒数第二个[sS]*?——用它匹配</body>标签,就是此前匹配过正则表达式模板</body>的那个标签——然后继续查找第二个</body>标签直到字符串的末尾。当所有这些步骤都失败了,倒数第三个[sS]*?将被扩展直至字符串的末尾,依此类推。

解决这个问题可以通过重复一个非捕获组来达到同样效果,它包含一个回顾(阻塞下一个所需的标签)和[sS](任意字符)元序列。这确保中间位置上你查找的每个标签都会失败,然后,更重要的是,[sS]模板在你在回顾过程中阻塞的标签被发现之前不能被扩展。应用此方法后正则表达式最终修改如下:

/<html>(?:(?!<head>)[sS])*<head>(?:(?!<title>)[sS])*<title>(?:(?!</title>)[sS])*</title>(?:(?!</head>)[sS])*</head>(?:(?!<body>)[sS])*<body>(?:(?!</body>)[sS])*</body>(?:(?!</html>)[sS])*</html>/

像这样为每个匹配字符多次前瞻缺乏效率,而且成功匹配过程也相当慢。匹配较短字符串时此方法相当不错,但匹配一个HTML 文件可能需要前瞻并测试上千次。

使用类似于原子组的方式修改如下:

现在如果没有尾随的</html>那么最后一个[sS]*?将扩展至字符串结束,正则表达式将立刻失败因为没有回溯点可以返回。正则表达式每次找到一个中间标签就退出一个前瞻,它在前瞻过程中丢弃所有回溯位置。下一个后向引用简单地重新匹配前瞻过程中发现的字符,将他们作为实际匹配的一部分。

更多方式提高正则表达式效率

  1. 关注如何让匹配更快失败:正则表达式处理慢往往是因为匹配失败过程慢,而不是匹配成功过程慢。如果你使用正则表达式匹配一个很大字符串的一小部分,情况更为严重,正则表达式匹配失败的位置比匹配成功的位置要多得多。如果一个修改使正则表达式匹配更快但失败更慢(例如,通过增加所需的回溯次数去尝试所有分支的排列组合),这通常是一个失败的修改。
  2. 正则表达式以简单的,必需的字元开始:最理想的情况是,一个正则表达式的起始字元应当尽可能快速地测试并排除明显不匹配的位置。用于此目的好的起始字元通常是一个锚(^或$),特定字符(例如x 或u363A),字符类(例如,[a-z]或速记符例如d),和单词边界(b)。如果可能的话,避免以分组或选择字元开头,避免顶级分支例如/one|two/,因为它强迫正则表达式识别多种起始字元。
  3. 编写量词模板,使它们后面的字元互相排斥:当字符与字元毗邻或子表达式能够重叠匹配时,一个正则表达式尝试分解文本的路径数量将增加。为避免此现象,尽量具体化你的模板。当你想表达[^"rn]*时不要使用.*?(依赖回溯)。
  4. 减少分支的数量,缩小它们的范围:分支使用 | ,竖线,可能要求在字符串的每一个位置上测试所有的分支选项。你通常可通过使用字符类和选项组件减少对分支的需求,或将分支在正则表达式上的位置推后(允许到达分支之前的一些匹配尝试失败)。
  5. 使用非捕获组:捕获组花费时间和内存用于记录后向引用,并保持它们是最新的。如果你不需要一个后向引用,可通过使用非捕获组避免这种开销——例如,(?:…)替代(…)。有些人当他们需要一个完全匹配的后向引用时,喜欢将他们的正则表达式包装在一个捕获组中。这是不必要的,因为你能够通过其他方法引用完全匹配,例如,使用regex.exec()返回数组的第一个元素,或替换字符串中的$&
  6. 捕获感兴趣的文字,减少后处理:如果你需要引用匹配的一部分,应当通过一切手段,捕获那些片断,再使用后向引用处理。例如,如果你写代码处理一个正则表达式所匹配的引号中的字符串内容,使用/"([^"]*)"/然后使用一次后向引用,而不是使用/"[^"]*"/然后从结果中手工剥离引号。当在循环中使用时,减少这方面的工作可以节省大量时间。
  7. 暴露所需的字元:为帮助正则表达式引擎在如何优化查询例程时做出明智的决策,应尽量简单地判断出那些必需的字元。当字元应用在子表达式或者分支中,正则表达式引擎很难判断他们是不是必需的,有些引擎并不作此方面努力。例如,正则表达式/^(ab|cd)/暴露它的字符串起始锚。IE 和Chrome 会注意到这一点,并阻止正则表达式尝试查找字符串头端之后的匹配,从而使查找瞬间完成而不管字符串长度。但是,由于等价正则表达式/(^ab|^cd)/不暴露它的^锚,IE 无法应用同样的优化,最终无意义地搜索字符串并在每一个位置上匹配。
  8. 使用适当的量词:贪婪量词和懒惰量词即使匹配同样的字符串,其查找匹配过程也是不同的。在确保正确等价的前提下,使用更合适的量词类型(基于预期的回溯次数)可以显著提高性能,尤其在处理长字符串时。
  9. 将正则表达式赋给变量,以重用它们:将正则表达式赋给变量以避免对它们重新编译。有人做的太过火,使用正则表达式缓存池,以避免对给定的模板和标记组合进行多次编译。不要过分忧虑,正则表达式编译很快,这样的缓存池所增加的负担可能超过他们所避免的。重要的是避免在循环体中重复编译正则表达式。
  10. 将复杂的正则表达式拆分为简单的片断:尽量避免一个正则表达式做太多的工作。复杂的搜索问题需要条件逻辑,拆分为两个或多个正则表达式更容易解决,通常也更高效,每个正则表达式只在最后的匹配结果中执行查找。在一个模板中完成所有工作的正则表达式怪兽很难维护,而且容易引起回溯相关的问题。

什么时候不应该使用正则表达式

例如,如果你想检查一个字符串是不是以分号结束,你可以使用:

endsWithSemicolon = /;$/.test(str);

虽说当前没有哪个浏览器聪明到这个程度,能够意识到这个正则表达式只能匹配字符串的末尾。最终它们所做的将是一个一个地测试了整个字符串。每当发现了一个分号,正则表达式就前进到下一个字元($),检查它是否匹配字符串的末尾。如果不是这样的话,正则表达式就继续搜索匹配,直到穿越了整个字符串。字符串的长度越长(包含的分号越多),它占用的时间也越长。

更好的办法是跳过正则表达式所需的所有中间步骤,简单地检查最后一个字符是不是分号:

endsWithSemicolon = str.charAt(str.length - 1) == ";";

字符串trim

使用正则表达式来trim

// trim 1
String.prototype.trim = function() {
    return this.replace(/^s+/, "").replace(/s+$/, "");
}

通过将/s+$/替换成/ss*$/,在Firefox中大约35%的性能提升。虽然这两个正则表达式的功能完全相同,Firefox 却为那些以非量词字元开头的正则表达式提供额外的优化。在其他浏览器上,差异不显著,或者优化完全不同。然而,改变正则表达式,在字符串开头匹配/^ss*/不会产生明显差异,因为^锚需要照顾那些快速作废的非匹配位置(避免一个轻微的性能差异,因为在一个长字符串中可能产生上千次匹配尝试)。

第二种方案是将两个正则合并为一个,但它们在处理长字符串时,总比用两个简单的表达式要慢,因为两个分支选项都要测试每个字符位置。

// trim 2
String.prototype.trim = function() {
    return this.replace(/^s+|s+$/g, "");
}

第三种方案的工作原理是匹配整个字符串,捕获从第一个到最后一个非空格字符之间的序列,记入后向引用1。然后使用后向引用1 替代整个字符串。中间[sS]*?使用懒惰匹配,需要一个个尝试,因此在操作长目标字符串时很慢。

// trim 3
String.prototype.trim = function() {
    return this.replace(/^s*([sS]*?)s*$/, "$1");
}

第四种方式是前一种的改进版,以贪婪量词取代了懒惰量词,为确保捕获组只匹配到最后一 个非空格字符,必需尾随一个S

// trim 4
String.prototype.trim = function() {
    return this.replace(/^s*([sS]*S)?s*$/, "$1");
}

[sS]*中的贪婪量词“*”表示重复方括号中的任意字符模板直至字符串结束。然后正则表达式每次回溯一个字符,直到它能够匹配后面的S,或者直到回溯到第一个字符而匹配整个组(然后它跳过这个组)。

如果尾部空格不比其它字符串更多,它通常比前面那些使用懒惰量词的方案更快。

第五种方案在所有浏览器中都最慢,一般不会使用。

// trim 5
String.prototype.trim = function() {
    return this.replace(/^s*(S*(s+S+)*)s*$/, "$1");
}

不使用正则表达式来trim

// trim 6
String.prototype.trim = function() {
    var start = 0,
        end = this.length - 1,
        ws = "nrtfx0bxa0u1680u180eu2000u2001u2002u2003u2004u2005u2006u2007u2008u2009u200au200bu2028u2029u202fu205fu3000ufeff";
    while (ws.indexOf(this.charAt(start)) > -1) {
        start++;
    }
    while (end > start && ws.indexOf(this.charAt(end)) > -1) {
        end--;
    }
    return this.slice(start, end + 1);
}

当字符串末尾只有少量空格时,这种情况使正则表达式陷入疯狂工作。原因是,尽管正则表达式很好地去除了字符串头部的空格,它们却不能同样快速地修剪长字符串的尾部。

虽然本实现不受字符串总长度影响,但它有自己的弱点:(它害怕)长的头尾空格。因为循环检查字符是不是空格在效率上不如正则表达式所使用的优化过的搜索代码。

混合方式

最后一个办法是将两者结合起来,用正则表达式修剪头部空格,用非正则表达式方法修剪尾部字 符。

// trim 7
String.prototype.trim = function() {
    var str = this.replace(/^s+/, ""),
        end = str.length - 1,
        ws = /s/;
    while (ws.test(str.charAt(end))) {
        end--;
    }
    return str.slice(0, end + 1);
}

所有修剪方法总的趋势是:在基于正则表达式的方案中,字符串总长比修剪掉的字符数量更影响性能;而非正则表达式方案从字符串末尾反向查找,不受字符串总长的影响,但明显受到修剪空格数量的影响。简单地使用两个子正则表达式在所有浏览器上处理不同内容和长度的字符串时,均表现出稳定的性能。因此它可以说是最全面的解决方案。

总结

  • 密集的字符串操作和粗浅地编写正则表达式可能是主要性能障碍,但本章中的建议可帮助您避免常见缺陷。
  • 当连接数量巨大或尺寸巨大的字符串时,数组联合是IE7 和它的早期版本上唯一具有合理性能的方法。
  • 如果你不关心IE7 和它的早期版本,数组联合是连接字符串最慢的方法之一。使用简单的+和+=取而代之,可避免(产生)不必要的中间字符串。
  • 回溯既是正则表达式匹配功能基本的组成部分,又是正则表达式影响效率的常见原因。
  • 回溯失控发生在正则表达式本应很快发现匹配的地方,因为某些特殊的匹配字符串动作,导致运行缓慢甚至浏览器崩溃。避免此问题的技术包括:使相邻字元互斥,避免嵌套量词对一个字符串的相同部分多次匹配,通过重复利用前瞻操作的原子特性去除不必要的回溯。
  • 提高正则表达式效率的各种技术手段,帮助正则表达式更快地找到匹配,以及在非匹配位置上花费更少时间。
  • 正则表达式并不总是完成工作的最佳工具,尤其当你只是搜索一个文本字符串时。
  • 虽然有很多方法来修整一个字符串,使用两个简单的正则表达式(一个用于去除头部空格,另一个用于去除尾部空格)提供了一个简洁、跨浏览器的方法,适用于不同内容和长度的字符串。从字符串末尾开始循环查找第一个非空格字符,或者在一个混合应用中将此技术与正则表达式结合起来,提供了一个很好的替代方案,它很少受到字符串整体长度的影响。