JavaScript 配列の重複排除に関するいくつかのアイデアの詳細な例-jsチュートリアル-php.cn

JavaScript 配列の重複排除に関するいくつかのアイデアの詳細な例

小云云

リリース： 2018-02-08 16:14:00

オリジナル

1479 人が閲覧しました

データ重複排除に対する実際の需要は、lodash などのツールライブラリが成熟した完全な実装を備えており、運用環境で十分に使用できることです。しかし、これは、いくつかのアイデアを使用して重複の削除をどのように達成できるかを検討する思考拡張の観点から妨げるものではありません。この記事では主に、JavaScript 配列の重複排除に関するいくつかのアイデアを紹介します。

1つ目は、従来の2層ループ比較のアイデアの実装です

function doubleLoopUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length, isExist; i < len; i++) {
    // 定义一个变量表示当前元素在 result 中是否存在。
    isExist = false;
    for (let j = 0, rLen = result.length; j < rLen; j++) {
      if (result[j] === arr[i]) {
        // 依次对result 中的元素 和 原数组元素进行比对。
        isExist = true;
        break;
      }
    }
    // 最后判断如果不存在，则将此元素插入result
    !isExist && result.push(arr[i]);
  }
  return result;
}

ログイン後にコピー

重複排除にはjsの組み込みindexOfを使用します

function indexOfUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    // 用indexOf 简化了二层循环的流程
    if (result.indexOf(arr[i]) === -1) result.push(arr[i]);
  }
  return result;
}

ログイン後にコピー

ソート前後を比較して重複排除

function sortUniq(arr) {
  let result = [], last;
  // 这里解构是为了不对原数组产生副作用
  [ ...arr ].sort().forEach(item => {
    if (item != last) {
      result.push(item);
      last = item;
    }
  });
  return result;
}

ログイン後にコピー

hashTableを使用して重複排除

function hashUniq(arr) {
  let hashTable = arr.reduce((result, curr, index, array) => {
    result[curr] = true;
    return result;
  }, {})
  return Object.keys(hashTable).map(item => parseInt(item, 10));
}

ログイン後にコピー

ES6 1 行のコードを設定します重複排除

function toSetUniq(arr) {
  return Array.from(new Set(arr));
}

ログイン後にコピー

splice 重複排除 (配列自体を直接操作しますが、副作用はあります)

function inPlaceUniq(arr) {
  let idx = 0;
  while (idx < arr.length) {
    let compare = idx + 1;
    while (compare < arr.length) {
      if (arr[idx] == arr[compare]) {
        arr.splice(compare, 1);
        continue;
      }
      ++compare
    }
    ++idx;
  }
  return arr;
}

ログイン後にコピー

最後に、nodejs でテストを実行して、どれがより効率的かを確認します~

let data = [];
for (var i = 0; i < 100000; i++) {
  data.push(Math.random())
}

// 实现一个性能测试的装饰器
function performanceTest(fn, descript) {
  var a = new Date().getTime();
  return function () {
    fn.apply(this, [].slice.call(arguments, 0));
    console.log(descript, new Date().getTime() - a)
  }
}

performanceTest(hashUniq, "hashTable")(data)
performanceTest(sortUniq, "sortUniq")(data)
performanceTest(toSetUniq, "toSetUniq")(data)
performanceTest(indexOfUniq, "indexOfUniq")(data)
performanceTest(doubleLoopUniq, "doubleLoopUniq")(data)
performanceTest(inPlaceUniq, "inPlaceUniq")(data)

ログイン後にコピー

結果は次のとおりです

hashTable 168ms
sortUniq 332ms
toSetUniq 80ms
indexOfUniq 4280ms
doubleLoopUniq 13303ms
inPlaceUniq 9977ms

ログイン後にコピー

拡張思考: 配列内の要素がオブジェクトの場合に重複を削除するにはどうすればよいですか?

参照型であるため、必然的に deepEqual が使用されますが、このアイデアはこの問題を解決できますが、必然的に十分な効率が得られません。

上記のテストから、新しい Set と hashTable による重複排除が最も効率的であることがわかります。
したがって、これら 2 つのメソッドに基づいて変換する必要があるのは間違いありません。私は hashTable を使用したいと考えています。
一方で、詳細な比較による時間を削減するために、JSON.stringify を使用してみます。参照型を基本型に変換します。

function collectionUniq(collection) {
  let hashTable = {};
  collection.forEach(item => {
    hashTable[JSON.stringify(item)] = true;
  })
  return Object.keys(hashTable).map(item => JSON.parse(item))
}

ログイン後にコピー

ここで問題が発生します。データがこのような場合、それは GG です。

let collection = [ { a: 1, b: 2, c: 3 }, { b: 2, c: 3, a: 1 } ]

ログイン後にコピー

toHash というアイデアがあります。この配列の基本的な重複排除の後、精度を確保するために、
最初に JSON 文字列を走査 =>
charCodeAt() を通じて各文字列の Unicode エンコードを取得します。 =>
加算して合計を取得し、最後に値が等しいものをペアで比較することで、重複排除の効果が得られます。

function toHash(obj) {
  let power = 1;
  let res = 0;
  const string = JSON.stringify(obj, null, 2);
  for (let i = 0, l = string.length; i < l; i++) {
    switch (string[i]) {
      case '{':
        power *= 2
        break
      case '}':
        power /= 2
        break
      case ' ':
      case '\n':
      case '\r':
      case '\t':
      break
      default:
        res += string[i].charCodeAt(0) * power
    }
  }
  return res
}

ログイン後にコピー

これは実装の基本的なアイデアにすぎず、ハッシュ衝突の可能性を減らすために、一部の特殊文字の重みを増減することができます。

重要なのは、ジャックポットを獲得するよりも衝突の可能性を確実に小さくすることです。