鍍金池/ 問答/HTML/ 優(yōu)化這個用于統(tǒng)計字母出現(xiàn)次數(shù)的函數(shù),看看你優(yōu)化后的函數(shù)需要耗時幾毫秒?

優(yōu)化這個用于統(tǒng)計字母出現(xiàn)次數(shù)的函數(shù),看看你優(yōu)化后的函數(shù)需要耗時幾毫秒?

某前端群里出了一個題目:
封裝一個charStat函數(shù)用于統(tǒng)計給定網(wǎng)址中html源代碼中a-z字母(不區(qū)分大小寫)出現(xiàn)的次數(shù),函數(shù)返回Promiseresolve這樣一個對象:keya-z(不可亂序)、value為對應字母出現(xiàn)次數(shù)。
為了排除掉網(wǎng)絡請求耗時影響,所以我們只優(yōu)化console.time('ms')console.timeEnd('ms')之間的代碼,保證結(jié)果正確的前提下,通過比較輸出結(jié)果中的ms:后的數(shù)值大小來評價優(yōu)化結(jié)果。
執(zhí)行多次,平均輸出大于50msE(不及格),在50ms內(nèi)評分為D等級方案,40ms內(nèi)為C,30ms內(nèi)為B20ms內(nèi)為A,10ms左右算終極方案了

以下是我的代碼,通過String.prototype.replace實現(xiàn),雖然比較精簡但耗時較長(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
      }
      // 以下是我覺得重點需要優(yōu)化的部分
      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 }
回答
編輯回答
練命

為什么一定要用正則?這樣簡單的需求,用最簡單的遍歷一次就解決了???

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;
2018年1月16日 00:19
編輯回答
夢若殤

做優(yōu)化最好基于同樣的樣本,'http://www.sina.com.cn/'的返回值是動態(tài)的,會有一定的誤差,特別是這個計算的結(jié)果受長度影響很大。

思路上優(yōu)化了兩個小的地方,一個是遍歷的時候以固定的順序用charCodeAt訪問大字符串(html),這樣理論上會更好的利用緩存;其次是避免使用toLowerCase,因為這個方法會對非ASCII字符做很多判斷,如果只需要處理字母的話,自己用char code會更快。

為了追求更好的結(jié)果,手動初始化了_c

在我電腦上的測試結(jié)果:

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));
2017年6月4日 06:28
編輯回答
墨小白

補充幾個,因機器和返回內(nèi)容長度時間會有些誤差

正常思路版 ≈ 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')

數(shù)組版 ≈ 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')
2018年3月26日 07:53
編輯回答
逗婦惱

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}

優(yōu)化了下

2018年2月28日 23:29
編輯回答
熟稔
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')
2017年10月1日 03:11