JS 字符串去重最佳方案

研究一下字符串去重最佳方案

问题

33332211123111122233123123aabbddff 返回 321abdf

最佳题解

开始我以为~~~方法 test4 最快~~~

然而最快的是下面的 test6 方法，开始我也不明白为什么用 str.indexOf(c) === i 后来我想明白之后发现这段代码才是最巧妙的一段。

// 该方法由群友德巨晨晨提供
function test6(str) {
  const len = str.length;
  const res = [];
  for (let i = 0; i < len; i++) {
    const c = str[i];
    if (str.indexOf(c) === i) {
      res.push(c);
    }
  }
  return res.join('');
}

全部实现和用例

function test(str) {
  let list = [];
  return [...str]
    .filter((e) => {
      let inList = list.indexOf(e) > -1;
      if (inList) {
        return false;
      }
      list.push(e);
      return true;
    })
    .join('');
}

function test2(str) {
  let list = [];
  let newStr = [];
  for (let index = 0; index < str.length; index++) {
    const element = str[index];
    if (list.indexOf(element) == -1) {
      newStr.push(element);
      list.push(element);
    }
  }
  return newStr.join('');
}

function test3(str) {
  let list = [];
  let newStr = str;
  while (newStr.length != 0) {
    list.push(newStr[0]);
    let reg = RegExp(newStr[0], 'g')
    newStr = newStr.replace(reg, '');
  }
  return list.join('');
}

function test4(params) {
  return Array.from(new Set(params)).join('')
}

function test5(params) {
  return [...new Set(params)].join('')
}

function test6(str) {
  const len = str.length;
  const res = [];
  for (let i = 0; i < len; i++) {
    const c = str[i];
    if (str.indexOf(c) === i) {
        res.push(c);
    }
  }
  return res.join('');
}

function test6_1(str) {
  const len = str.length;
  let res = '';
  for (let i = 0; i < len; i++) {
    const c = str[i];
    if (str.indexOf(c) === i) {
        res += c
    }
  }
  return res;
}

function test7(str) {
  var len = str.length;
  var res = new Array(len);
  var c, _i = 0;
  for (let i = 0; i < len; i++) {
    c = str[i];
    if (str.indexOf(c) === i) {
        res[_i++] = c;
    }
  }
  return res.join('');
}


function randomString(e) {
  e = e || 32;
  var t = 'ABCDEFGHJKMNPQRSTWXYZabcdefhijkmnprstwxyz2345678',
    a = t.length,
    n = '';
  for (i = 0; i < e; i++) n += t.charAt(Math.floor(Math.random() * a));
  return n;
}

let longString = randomString(1000000)
console.time('test')
console.log('test :>> ', test(longString));
console.timeEnd('test')

console.time('test2')
console.log('test2 :>> ', test2(longString));
console.timeEnd('test2')

console.time('test3')
console.log('test3 :>> ', test3(longString));
console.timeEnd('test3')

console.time('test4')
console.log('test4 :>> ', test4(longString));
console.timeEnd('test4')

console.time('test5')
console.log('test5 :>> ', test5(longString));
console.timeEnd('test5')

console.time('test6')
console.log('test6 :>> ', test6(longString));
console.timeEnd('test6')

console.time('test6_1')
console.log('test6_1 :>> ', test6_1(longString));
console.timeEnd('test6_1')

console.time('test7')
console.log('test7 :>> ', test7(longString));
console.timeEnd('test7')

输出

test :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test: 181.931ms
test2 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test2: 119.95ms
test3 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test3: 140.046ms
test4 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test4: 61.402ms
test5 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test5: 53.693ms
test6 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test6: 41.997ms
test6_1 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test6_1: 44.282ms
test7 :>>  8S5QCWbFmfBJtjeyNcKEA4M2pkshX6R3xanTDGzPHrZ7idYw
test7: 60.487ms

总结

• test2 中朴实无华的 for 循环比 test1 快不少
• test4 中没有用结构，比 test5 快一些
• test6_1 是对 test6 的负优化，字符串拼接竟然没 join('') 快

也许？想办法进大厂，接触高端项目，就不用踩这些坑了？这些坑他们可能早就踩过了

衍生问题

• indexOf 方法够不够快？是不是最快的？
• new Set(params) 方法的底层原理是什么，能写一个类似的方法追上 new Set(params) 吗？

参考资料

https://stackoverflow.com/questions/1960473/get-all-unique-values-in-a-javascript-array-remove-duplicates https://stackoverflow.com/questions/26097132/javascript-remove-duplicates-algorithm-efficiency