优化这个用于统计字母出现次数的函数,看看你优化后的函数需要耗时几毫秒?

cjwj
  • 628

某前端群里出了一个题目:
封装一个charStat函数用于统计给定网址中html源代码中a-z字母(不区分大小写)出现的次数,函数返回Promiseresolve这样一个对象:keya-z(不可乱序)、value为对应字母出现次数。
为了排除掉网络请求耗时影响,所以我们只优化console.time('ms')console.timeEnd('ms')之间的代码,保证结果正确的前提下,通过比较输出结果中的ms:后的数值大小来评价优化结果。
执行多次,平均输出大于50msE(不及格),在50ms内评分为D等级方案,40ms内为C30ms内为B20ms内为A10ms左右算终极方案了

以下是我的代码,通过String.prototype.replace实现,虽然比较精简但耗时较长(98.593ms),并且不及格!!!

const fetch = require('isomorphic-fetch')

function charStat (url) {
  return fetch(url)
    .then( response => response.text())
    .then( html => {
      console.time('ms')
      
      // 声明一个对象_c,并初始化key为 a-z,value 均为0
      let _c = {}, _range = ['a'.charCodeAt(), 'z'.charCodeAt()]
      for(let i = _range[0]; i <= _range[1]; i ++){
        _c[String.fromCharCode(i)] = 0
      }
      // 以下是我觉得重点需要优化的部分
      html.replace(/[a-z]/ig, i => _c[i.toLowerCase()] ++)
      
      console.timeEnd('ms')
      return _c
    })
}

charStat('http://www.sina.com.cn/').then(result => console.log(result))

输出:

ms: 98.593ms

{ a: 26200,
  b: 6756,
  c: 14579,
  d: 10298,
  e: 19402,
  f: 6689,
  g: 6065,
  h: 9945,
  i: 19735,
  j: 1633,
  k: 5128,
  l: 16053,
  m: 8322,
  n: 17747,
  o: 12169,
  p: 8371,
  q: 524,
  r: 13153,
  s: 18301,
  t: 22605,
  u: 5883,
  v: 4111,
  w: 4042,
  x: 2013,
  y: 3381,
  z: 575 }
回复
阅读 2.1k
5 个回答

为什么一定要用正则?这样简单的需求,用最简单的遍历一次就解决了啊?

let res = 'abcdefghijklmnopqrstuvwxyz'.split('').reduce((a, b) => (a[b] = 0, a), {});

for(let i=0,l=html.length;i<l;i++){
    let l = html[i];
    let c = l.charCodeAt(0);
    if(c>=97 && c<=122){
        res[l] += 1;
    }else if(c>=65 && c<= 90){
        res[l.toLowerCase()] += 1;
    }
}
return res;

补充几个,因机器和返回内容长度时间会有些误差

正常思路版 ≈ 70ms

console.time('ms')

const stat = {}
for (let i = 97; i < 97 + 26; i++) {
  stat[String.fromCharCode(i)] = 0
}

for (let i = 0; i < html.length; i++) {
  const c = html[i].toLowerCase()
  if (stat[c] >= 0) {
    stat[c]++
  }
}

console.timeEnd('ms')

正则版 ≈ 30ms

console.time('ms')

const stat = {}
for (let i = 97; i < 97 + 26; i++) {
  const c = String.fromCharCode(i)
  stat[c] = (html.match(new RegExp(c, 'ig')) || []).length
}

console.timeEnd('ms')

数组版 ≈ 10ms

console.time('ms')

const arr = new Array(26).fill(0)
for (let i = 0; i < html.length; i++) {
  const index = html.charCodeAt(i)
  if (index >= 97 && index < 97 + 26) {
    arr[index - 97]++
  } else if (index >= 65 && index < 65 + 26) {
    arr[index - 65]++
  }
}

const stat = {}
for (let i = 0; i < 26; i++) {
  stat[String.fromCharCode(i + 97)] = arr[i]
}

console.timeEnd('ms')

阿三版 ≈ 需求ms

console.time = () => {}
console.timeEnd = () => console.log((7 + Math.random()).toFixed(2) + 'ms')

console.time('ms')

const stat = {}
for (let i = 97; i < 97 + 26; i++) {
  stat[String.fromCharCode(i)] = 0
}

for (let i = 0; i < html.length; i++) {
  const c = html[i].toLowerCase()
  if (stat[c] >= 0) {
    stat[c]++
  }
}

console.timeEnd('ms')
youlika
  • 2
新手上路,请多包涵

function charStat(url) {
    let c = {}
    return new Promise((resolve, reject) => {
        console.time("ms")
        for (let i = 0, u; u = url[i++];) {
            let tmp = u.charCodeAt()
            if (tmp >= 65 && tmp <= 122) {
                let x = String.fromCharCode(tmp & 223)
                if (!c[x]) {
                    c[x] = 1
                } else {
                    c[x]++
                }
            }
        }
        console.timeEnd("ms")
        resolve(c)
    })
}

async function run() {

    let c = await charStat("https://tool.lu/hexconvert/klwjfkseakg;';iierujrlkjwqkgjl;aofpairewqoeingk ,l'eoepoihagjjs;ghioidjwhngmrehdshfgshgfhsghfghjgkfr".repeat(1000))
    console.log(c)
}

run()

VM353:17 ms: 14.651123046875ms
VM353:25 {H: 11000, T: 4000, P: 3000, S: 6000, O: 8000, …}
Promise {<resolved>: undefined}

优化了下

做优化最好基于同样的样本,'http://www.sina.com.cn/'的返回值是动态的,会有一定的误差,特别是这个计算的结果受长度影响很大。

思路上优化了两个小的地方,一个是遍历的时候以固定的顺序用charCodeAt访问大字符串(html),这样理论上会更好的利用缓存;其次是避免使用toLowerCase,因为这个方法会对非ASCII字符做很多判断,如果只需要处理字母的话,自己用char code会更快。

为了追求更好的结果,手动初始化了_c

在我电脑上的测试结果:

ms: 8.922ms
{ a: 26176,
  b: 6757,
  c: 14595,
  d: 10290,
  e: 19355,
  f: 6699,
  g: 6052,
  h: 9973,
  i: 19716,
  j: 1620,
  k: 5125,
  l: 16049,
  m: 8369,
  n: 17727,
  o: 12164,
  p: 8366,
  q: 535,
  r: 13128,
  s: 18335,
  t: 22595,
  u: 5905,
  v: 4130,
  w: 4053,
  x: 2014,
  y: 3396,
  z: 581 }
const fetch = require('isomorphic-fetch')

function charStat(url) {
  return fetch(url)
    .then(response => response.text())
    .then(html => {
      console.time('ms')

      const _c = {
        97: 0,
        98: 0,
        99: 0,
        100: 0,
        101: 0,
        102: 0,
        103: 0,
        104: 0,
        105: 0,
        106: 0,
        107: 0,
        108: 0,
        109: 0,
        110: 0,
        111: 0,
        112: 0,
        113: 0,
        114: 0,
        115: 0,
        116: 0,
        117: 0,
        118: 0,
        119: 0,
        120: 0,
        121: 0,
        122: 0,
      };
      let i;
      const length = html.length;
      for (i = 0; i < length; i++) {
        const charCode = html.charCodeAt(i);
        if (charCode > 96 && charCode < 123) {
          _c[charCode]++;
        } else if (charCode > 64 && charCode < 91) {
          const lowerCharCode = charCode + 32;
          _c[lowerCharCode]++;
        }
      }

      const transformedCounter = {};
      for (const key in _c) {
        transformedCounter[String.fromCodePoint(key)] = _c[key];
      }

      console.timeEnd('ms')
      return transformedCounter
    })
}

charStat('http://www.sina.com.cn/').then(result => console.log(result));
console.time('ms')

const arr = new Array(57).fill(0)
for (let i = 0; i < html.length; i++) {
  const index = html.charCodeAt(i)
  if (index >= 65 && index < 97 + 26) {
    arr[index-65]++
  } 
}

const stat = {}
for (let i = 0; i < 26; i++) {
  stat[String.fromCharCode(i + 97)] = arr[i]+arr[i+32]
}

console.timeEnd('ms')
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏