【Algorithm】頻度カウンター(Frequency Counter)パターン

はじめに

この記事は、株式会社スピードリンクジャパン Advent Calendar 2023 の18日目の記事です。

頻度カウンター(Frequency Counter)とは

プログラミングにおける頻度カウンターパターンは、データ内の要素の頻度や回数を計算するために使用される技術です。このパターンは、オブジェクトやマップを使用して、特定の要素がデータ構造（例：配列、文字列）内で何回出現するかをカウントします。特に配列や文字列のような線形データ構造で効果的です。

使用目的

頻度カウンターパターンは、複雑な問題を解決する際に時間の複雑さを改善するのに非常に役立ちます。特にデータが多いときに入れ子になったループの使用を避けることで、時間の複雑さをO(N^2)からO(N)に減らして性能を大幅に高めることができます。

例：配列要素の二乗を探し

問題定義
1つのメソッドを作ります。2つの配列が与えられた場合、1つ目の配列のすべての要素の二乗が2つ目の配列に存在するかどうかを確認する問題です。2つの配列の長さが同じであり、要素の頻度も同じでなければなりません。

same([0, 0, 0], [0, 0, 0]); // true
same([1, 2, 3], [1, 4, 9]); // true
same([1, 2, 3], [1, 4, 8]); // false
same([10], [100]); // true
same([1, 2], [1]) // false

入れ子になったループ
1つ目の配列の各要素を順番に探索して、2つ目の配列でその要素の二乗を探す方法です。この方法は入れ子になったループを使用するため、時間の複雑さがO(N^2)です。

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }
  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    if (correctIndex === -1) {
      return false;
    }
    arr2.splice(correctIndex, 1);
  }
  return true;
}

頻度カウンター
頻度カウンターを使用して、各配列の要素の頻度を計算し、それを比較する方法です。この方法では、時間の複雑さをO(N)に減らすことができます。

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) {
    return false;
  }

  let frequencyCounter1 = {};

  for (let val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }

  for (let val of arr2) {
    let squareRoot = Math.sqrt(val);
    if (!frequencyCounter1[squareRoot]) {
      return false;
    }
    frequencyCounter1[squareRoot] -= 1;
  }

  return true;
}

結論

頻度カウンターパターンは、プログラミングにおいて非常に役立つツールです。特に配列や文字列を扱う際、入れ子になったループを避け、時間の複雑さを減らすのに大きな助けとなります。このパターンを通じて、コードの効率性を高めることができます。

参考