🫧

new Map を使わない JS/TS での重複要素の検出と頻度カウントを試してみる

に公開
JavaScript
TypeScript
初心者
map
tech

はじめに

任意の文字列をはじめ、プリミティブな各要素の重複検出や頻度カウントを行うにはnew Mapを使うのが最もシンプルで簡単な方法です。

しかし今回、学習や理解のために「Mapを使わずにどう実装できるか？」を試してみました。

結論

やはり王道はnew Mapを使うことです。

1. new Mapを使うのがベストプラクティス

const targetCharacter = 'message';

const charMap: Map<string, number> = new Map();
for (const char of targetCharacter) {
    charMap.set(char, (charMap.get(char) || 0) + 1);
}
console.log(charMap);
// Map (5) {"m" => 1, "e" => 2, "s" => 2, "a" => 1, "g" => 1}
  • パフォーマンス：大量のデータの追加/削除が頻繁な場合に優れています
  • キーの型の柔軟性：任意の型をキーとして使用可能
  • イテレーションが簡単：順序が保証され、様々な反復メソッドが利用可能

Mapには上記のような利点があるので、今回の重複チェックや頻度検出といったケースに向いています。

Mapに関しては、以前まとめた記事があるので良ければこちらをご確認ください

https://zenn.dev/benjuwan/articles/99b0e963f6ec11

new Mapを使わずに実装

本題です。

当初、筆者は「オブジェクトの配列を用意し、その中にある各オブジェクト要素に対して処理するアプローチ」を採っていたのですが、これでは配列とオブジェクトに対する操作が複雑になるほか非効率な実装でうまくいきませんでした。
オブジェクトを使って更新していくというアプローチは良かったものの、具体的な実装で詰まっていた感じです。

そこでAIとの壁打ちを通じて、単一オブジェクトを用意してそれを使い回す方法や、パフォーマンス面で懸念はあるものの配列ベースで処理する方法を知りました。

2. オブジェクトをMapとして使用

const targetCharacter = 'message';
const targetChar: (string | number)[] = targetCharacter.split('');

type resultType = {
    char: string | number;
    count: number;
};

// 重複チェック及び固有オブジェクトを用意するための処理用オブジェクト
// ※オブジェクトのミュータブルな性質を利用して各要素ごとのオブジェクトを生成する
// ※`Index Signature`：文字列型の`key`（プロパティ）は動的生成するためブラケット記法で型注釈付き指定
const countObj: { [key: string]: number } = {};

for (const char of targetChar) {
    const key = String(char); // 数値も文字列キーに変換
    if (key in countObj) {
        // if (Object.hasOwn(countObj, key)) { // es2022以降だとこちらを推奨
        countObj[key]++; // 重複対象の文字列（キー）の値を加算
    } else {
        countObj[key] = 1; // 重複していない場合は（初期値）1を設定
    }
}

// 処理用オブジェクト`countObj`を希望する型配列の形式に変換
const result: resultType[] = Object.entries(countObj).map(([char, count]) => ({
    char,
    count
}));

// 重複要素のみ抽出
const duplicates = result.filter(item => item.count > 1);
console.log('重複:', duplicates);
/* 
"重複:",
[{
  "char": "e",
  "count": 2
}, {
  "char": "s",
  "count": 2
}] 
*/
  • Object.hasOwn()とin演算子との違い
    • in演算子はプロトタイプチェーンも探索する
    • Object.hasOwn()は自身のプロパティのみを判定する（より安全）

3. 配列ベース（※非効率な処理でパフォーマンス面でも非推奨）

const targetCharacter = 'message';
const targetChar: (string | number)[] = targetCharacter.split('');

type resultType = {
    char: string | number;
    count: number;
};

// 重複チェックのための処理用配列（対象要素別オブジェクトを格納していく）
const countArray: resultType[] = [];

for (const char of targetChar) {
    // `find`メソッドで対象文字列と、既存オブジェクトのキー重複をチェック
    // ※`find`メソッドで各要素を毎回全探索（O(n)）するため非効率
    const existing: resultType[] = countArray.find(item => item.char === char);

    if (existing) {
        // 重複対象のカウント（キー）値を加算
        existing.count++;
    } else {
        // 重複していない場合は初期値オブジェクトを生成
        countArray.push({ char, count: 1 });
    }
}
console.log(countArray);
/*
[{
  "char": "m",
  "count": 1
}, {
  "char": "e",
  "count": 2
}, {
  "char": "s",
  "count": 2
}, {
  "char": "a",
  "count": 1
}, {
  "char": "g",
  "count": 1
}] 
*/

頻度チェックは不要で、単なる重複チェックを行いたい場合

  • new Setを使用する
const mixedIntStrAry: (string | number)[] = ['a', 1, 'b', 2, 'a', 3, 2, 15];
const mixedIntStrAryLength: number = mixedIntStrAry.length;

console.log(new Set(mixedIntStrAry)); // Set (6) {"a", 1, "b", 2, 3, 15} 
const exceptDuplicatedLength: number = new Set(mixedIntStrAry).size;

const hasDuplicate: boolean = exceptDuplicatedLength !== mixedIntStrAryLength;
console.log(hasDuplicate); // true

まとめ

new Mapを使わないアプローチではオブジェクトの利用が共通点かつポイントとなりました。これはオブジェクトがミュータブルであることが大きいです。

  • 配列ベースのアプローチ
    各要素ごとのオブジェクトを生成して、それを更新していく

  • オブジェクトをMapとして使用するアプローチ
    重複チェック及び加算処理用の単一オブジェクトを用意して対象要素ごとに検証。処理後、最終的に望む配列形式に加工し、その対象配列をフィルタリングして結果を得る。
    今回の検証に直接的な関係性はないものの、このアプローチ方法ではオブジェクトのキーを動的生成するIndex Signatureも重要な働きを持っています。

Discussion