昨天在学习reactjs小书的时候遇到一个string相关的问题，也就是这样的一个需求：

用户会在textarea中输入文本，当提交文本，在下方显示的时候，要对具有\`\`这样的字符围起来的字符串进行<code></code>的转化（也就是markdown中的行内代码语法）

直接字符替换

起初没多想，不就是字符替换吗？而且这就是个递归问题嘛，遇到第一个\`符号用<code>替换遇到第二个\`符号用</code>替换，然后递归下去，直到找不到\`符号，于是在经过一番调试，抓脑之后，写成了现在的版本：

// 思路一：直接字符替换
/**
 * 
 * @param {string} str       要替换的字符串
 * @param {number} idx       待替换字符的位置
 * @param {string:enum} type 待替换字符是开始还是结束字符
 */
function getResults(str, idx, type) {
  // type: begin/end，表示要去查找的`字符是开始的还是结束的，分别对应<code>和</code>
  if (type === 'begin') {
    if (idx === -1) {
        return str;
    }
    // 直接字符串拼接
    const temp =
        str.substring(0, idx) + "<code>" + str.substring(idx + 1, str.length);
    return getResults(temp, temp.indexOf("`"), "end");
  } else {
    if (idx === -1) {
        return str;
    }
    const temp =
        str.substring(0, idx) + "</code>" + str.substring(idx + 1, str.length);
    return getResults(temp, temp.indexOf("`"), "begin");
  }
}
function handlerStr(str) {
  return getResults(str, str.indexOf('`'), 'begin');
}
const str = "code`js`and`cs`dddd";
const res1 = handlerStr(str);
console.log(res1);

// output: code<code>js</code>and<code>cs</code>dddd

好的，感觉效果还可以，基本满足需求了，不过突然自己想到：

  1. 天啊，这是文本输入！，如果用户输入的文本很大，成千上万个字符呢？，其中用到了很多的字符串拼接，这不就性能很差了吗....
  2. 突然想到这样的一种情况，\`code\`js\`code\`，那么这种嵌套的结构，如果要表示成最内层嵌套的不转化，只转化最外层的话，那不就gg了？

心里又拔凉拔凉的了...，第一种情况还说不准，但是第二种情况就直接宣判了思路一的死刑，因为思路一会转化成<code>code</code><code>js</code>code</code>的形式，但是垂死挣扎一下，看下markdown的转化到底是不是那样的？直接github的isssue框里面试一下markdown即可，发现答案是：不是！，思路一的转化就是正确的，第二种情况是想多了哈哈哈......

使用replace方法

但是第一种情况的隐患下，还是得找一下第二种方法，于是就找到了今天的主角：string的replace方法：

首先看一下mdn的定义：

replace() 方法返回一个由替换值（replacement）替换一些或所有匹配的模式（pattern）后的新字符串

这里的字符串替换有一个特点就是不能简单的替换，因为这是需要配对的，前一个替换成<code>，而后一个得替换成闭合的</code>，那么这种情况该怎么办呢？

继续看mdn上关于replace的介绍，突然其中的接受一个函数作为参数 一下子点亮了，原来replace也提供这种高等级的控制啊！

例如mdn中给的案例：

/**
 * 
 * @param {string} match  匹配的子串
 * @param {string} pi     正则:第n个括号匹配的字符串
 * @param {number} offset 匹配到的子字符串在原字符串中的偏移量
 * @param {string} str    被匹配的原字符串
 */
function replacer(match, p1, p2, p3, offset, string) {
  // p1 is nondigits, p2 digits, and p3 non-alphanumerics
  return [p1, p2, p3].join(' - ');
}
var newString = 'abc12345#$*%'.replace(/([^\d]*)(\d*)([^\w]*)/, replacer);
console.log(newString);  // abc - 12345 - #$*%

另外对于正则匹配如果使用了g的修饰符，那么回调函数就会对每个匹配结果都调用。

这样的话，思路就变成：找到一个正则，可以匹配到\`符号圈起来的字符串，然后利用正则匹配中的括号来提取出中间部分，其中前后的\`符号可以用<code>，</code>来替换，这样就可以了，正则自己学了忘，忘了学，现在看来又得学了....还好找到这两个有用的参考链接：

《JS 正则迷你书》，一本很好的js正则迷你书
正则表达式括号嵌套匹配，借鉴了其中回答者的[^()]*写法

于是写出来如下：

//思路二：replace方法的新认识
/**
 * 
 * @param {string} match  匹配的子串
 * @param {string} p1     正则:第n个括号匹配的字符串
 * @param {number} offset 匹配到的子字符串在原字符串中的偏移量
 * @param {string} str    被匹配的原字符串
 */
function handlerReplace(match, p1, offset, str) {
  const temp = ["<code>", p1, "</code>"].join("");
  return temp;
}
const str = "code`js`and`cs`dd`dd";
const res2 = str.replace(/`([^`]*)`/g, handlerReplace);
console.log(res2);
// output: code<code>js</code>and<code>cs</code>dddd

测试

接下来就是对于这两种方法的简单测试，测试字符串如下：

// 生成指定num的带`的随机字符串
function generateRandomTestStr(swapTime = 10, repeatTime = 100000) {
  // 使用数组
  const str = "abcdefghijklnmopqrstuvwxyz";
  const arr = str.split("")
  while (swapTime --) {
    let i = Math.floor(Math.random() * 26);
    let j = Math.floor(Math.random() * 26);
    swap(arr, i, j)
  }
  // 然后再随机加入两个`符号
  let start = Math.floor(Math.random() * 26);
  let end = Math.floor(Math.random() * 26);
  arr[start] = '`';
  arr[end] = '`';
  // 再把字符串重复10万次
  return arr.join("").repeat(repeatTime)
  function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
// 默认生成一个26*10w长度的字符串
const testStr = generateRandomTestStr();

然后分别测试之前的两种方法，结果在百万这个量级：

  1. 第一种方法直接爆栈了，也是当然的毕竟这么多层递归
  2. 第二种方法耗时0.111秒

降低一下量级，到第一种方法不爆栈的前提下（26*2000）：

  1. 第一种方法跑三次：0.3/0.288/0.286秒
  2. 第二种方法跑三次：0.005/0.004/0.005秒

简直没法比，数量级的差别...，当然也要去想一下为什么，大致我的肤浅的理解：

第一种方法，如果indexOf可以理解为遍历去寻找的话，那么应该就相当于O(n^2)的复杂度，再加上每次字符串拼接使用substring在大字符串上，需要消耗大量的内存分配（要生成不同的字符串好几份），而报错中也有这样的信息（应该也和这种在O(n^2)的复杂度下，每一次循环都生成需要垃圾回收的大字符串直接相关）：

<--- Last few GCs --->
[185692:00000000003DBD40]     1374 ms: Mark-sweep 1395.8 (1409.1) -> 1395.8 (1409.1) MB, 3.7 / 0.0 ms  allocation failure GC in old space requested

而第二种方法，直接使用的正则匹配，加上可能能被引擎优化的标准库方法，可以达到比较好的性能了啊

遗留问题

  • 正则的字符串处理性能会更好一点吗？（联系之前的cloudflare的正则事件）
  • 只做了偶数情况的匹配，如果边界条件为奇数呢？第一种方法可以实现的是如果为奇数，则可以把</code>添到字符串末尾即可，而第二种方法则不可以，如果为奇数，直接最后的\`符号会不能被转换，这种情况该怎么做呢？

标签: none

添加新评论