🐼

Go言語とTypeScriptで学ぶ重複除去アルゴリズム完全ガイド

2025/07/13に公開

はじめに

配列やスライスから重複要素を除去する処理は、プログラミングにおいて非常によく使われる基本的なアルゴリズムです。本記事では、Go言語とTypeScriptを使って重複除去の実装方法を詳しく解説し、両言語の特徴や違いについても学んでいきます。

重複除去問題を通じて、効率的なアルゴリズムの考え方と実装のベストプラクティスを身につけることができます。

問題設定

以下の要件を満たす関数を実装してみましょう。

要件：

入力：整数のスライス/配列
出力：重複を除去した整数のスライス/配列（元の順序を保持）
例：[1, 2, 2, 3, 1, 4] → [1, 2, 3, 4]

Go言語での実装

基本的な実装

package main

import "fmt"

func removeDuplicates(nums []int) []int {
    if len(nums) == 0 {
        return []int{}
    }
    
    // 既に見た値を記録するためのmap
    seen := make(map[int]bool)
    // 結果を格納するスライス
    result := make([]int, 0, len(nums))
    
    for _, num := range nums {
        // まだ見ていない値の場合
        if !seen[num] {
            seen[num] = true
            result = append(result, num)
        }
    }
    
    return result
}

func main() {
    testCases := [][]int{
        {1, 2, 2, 3, 1, 4},
        {},
        {5, 5, 5},
        {1, 2, 3, 4},
    }

    for i, nums := range testCases {
        result := removeDuplicates(nums)
        fmt.Printf("テスト%d: %v → %v\n", i+1, nums, result)
    }
}

アルゴリズムの詳細解説

1. `make(map[int]bool)` - 重複チェック用のmap

seen := make(map[int]bool)

このmapは「辞書」のような役割を果たします。

キー: チェックしたい数値
値: その数値を見たかどうか（true/false）
目的: O(1)で「この数値を見たことがあるか？」を判定

2. `make([]int, 0, len(nums))` - 効率的なスライス作成

result := make([]int, 0, len(nums))

パラメータの意味：

型: []int - 整数のスライス
長さ: 0 - 最初は空（要素数0）
容量: len(nums) - 元のスライスと同じ容量を事前確保

なぜ容量を事前指定？

メモリの再割り当てを防ぐ
パフォーマンスの向上
最悪でも元の配列と同じサイズあれば十分

3. `for _, num := range nums` - アンダースコアの活用

for _, num := range nums {
    // インデックスは使わないので_で無視
}

アンダースコア（_）を使う理由：

Goでは使わない変数があるとコンパイルエラー
_で「この値は意図的に使わない」と明示
コードの意図を明確にする

4. 重複チェックのロジック

if !seen[num] {
    seen[num] = true
    result = append(result, num)
}

動作の流れ：

seen[num]でその数値を見たことがあるかチェック
見たことがなければ（!seen[num]がtrue）
その数値を「見た」と記録（seen[num] = true）
結果に追加（append(result, num)）

完全なテストコード

package main

import (
    "reflect"
    "testing"
)

func TestRemoveDuplicates(t *testing.T) {
    tests := []struct {
        name     string
        input    []int
        expected []int
    }{
        {
            name:     "通常のケース",
            input:    []int{1, 2, 2, 3, 1, 4},
            expected: []int{1, 2, 3, 4},
        },
        {
            name:     "空のスライス",
            input:    []int{},
            expected: []int{},
        },
        {
            name:     "重複なし",
            input:    []int{1, 2, 3, 4},
            expected: []int{1, 2, 3, 4},
        },
        {
            name:     "全て同じ値",
            input:    []int{5, 5, 5, 5},
            expected: []int{5},
        },
        {
            name:     "負の数を含む",
            input:    []int{-1, 2, -1, 3, 2},
            expected: []int{-1, 2, 3},
        },
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            result := removeDuplicates(tt.input)
            if !reflect.DeepEqual(result, tt.expected) {
                t.Errorf("removeDuplicates(%v) = %v, expected %v",
                    tt.input, result, tt.expected)
            }
        })
    }
}

Goのテストコードの記述方法について

なぜ `(t *testing.T)` と書くのか？

func TestRemoveDuplicates(t *testing.T) {
    // テストの処理
}

*testing.T の意味：

testing.TはGoの標準ライブラリの型
*はポインタを意味する（testing.T型の値のメモリアドレスを指す）
tは変数名（traditionallyの頭文字、慣習的に使われる）

なぜポインタを使うのか：

// ポインタを使わない場合（仮想的なコード）
func TestExample(t testing.T) {
    t.Error("テスト失敗") // この変更は元のオブジェクトに反映されない
}

// ポインタを使う場合（実際のコード）
func TestExample(t *testing.T) {
    t.Error("テスト失敗") // この変更は元のオブジェクトに反映される
}

ポインタを使うことで、テスト結果の記録や状態の変更が正しく行われます。

なぜ `tt` という変数名を使うのか？

for _, tt := range tests {
    t.Run(tt.name, func(t *testing.T) {
        result := removeDuplicates(tt.input)
        // ...
    })
}

tt の命名理由：

tはすでに*testing.Tで使用中
ttは「test table」の略
Goコミュニティでの慣習的な命名(ループ内変数はttがデファクトスタンダード)
参考：https://arp242.net/go-testing-style.html?source=post_page-----ab613c2f1431---------------------------------------#use-table-drive-tests-and-consistently-use-tt-for-a-test-case

TypeScriptでの実装

複数のアプローチ

TypeScriptでは複数の方法で重複除去を実装できます。

1. Setを使った実装（最もシンプル）

function removeDuplicatesWithSet(nums: number[]): number[] {
    return [...new Set(nums)];
}

2. Goと同じロジックの実装

function removeDuplicatesWithMap(nums: number[]): number[] {
    if (nums.length === 0) {
        return [];
    }
    
    const seen: { [key: number]: boolean } = {};
    const result: number[] = [];
    
    for (const num of nums) {
        if (!seen[num]) {
            seen[num] = true;
            result.push(num);
        }
    }
    
    return result;
}

`[...new Set(nums)]` の詳細解説

この書き方がなぜ必要なのか、ステップバイステップで解説します：

Step 1: Setとは

const nums = [1, 2, 2, 3, 1, 4];
const numSet = new Set(nums);
console.log(numSet); // Set {1, 2, 3, 4}

Setは「重複を許可しない集合」のデータ構造です。

Step 2: SetとArrayの違い

const array = [1, 2, 3, 4];  // Array型
const set = new Set([1, 2, 3, 4]);  // Set型

// 利用可能なメソッドが異なる
console.log(array.length);      // ✅ 4
console.log(set.size);          // ✅ 4
console.log(set.length);        // ❌ undefined

console.log(array.map(x => x * 2));  // ✅ [2, 4, 6, 8]
// console.log(set.map(x => x * 2));    // ❌ エラー！

console.log(array[0]);          // ✅ 1
console.log(set[0]);            // ❌ undefined

Step 3: なぜスプレッド構文が必要？

function removeDuplicates(nums: number[]): number[] {
    // ❌ 型エラー：Set<number>をnumber[]に代入できない
    // return new Set(nums);
    
    // ✅ 正しい：SetをArrayに変換
    return [...new Set(nums)];
}

Step 4: スプレッド構文の動作

const set = new Set([1, 2, 3, 4]);

// スプレッド構文で展開
console.log(...set);     // 1 2 3 4 （個別の値として展開）

// 配列として格納
console.log([...set]);   // [1, 2, 3, 4] （配列として格納）

Big O記法の補足説明

Big O記法とは？

Big O記法は、アルゴリズムの効率性を表現するための数学的な記法です。「データ量が増えたとき、処理時間やメモリ使用量がどのように増加するか」を表します。

身近な例で理解するBig O記法

本棚から本を探す例

O(1) - 定数時間：

本の位置を正確に知っている場合
「3段目の左から5番目」→ 一発で取れる
データが1冊でも1000冊でも、取る時間は同じ

O(log n) - 対数時間：

辞書で単語を探す場合
1. 真ん中のページを開く
2. 探している単語より前か後かを判断
3. 該当する半分で同じことを繰り返す
データが2倍になっても、探索回数は1回しか増えない

O(n) - 線形時間：

本棚を端から順番に探す場合
1冊ずつチェックして目的の本を探す
データが2倍になると、探索時間も2倍になる

O(n²) - 二次時間：

本の内容を全て比較する場合
全ての本を、他の全ての本と比較する
データが2倍になると、処理時間は4倍になる

プログラミングでの具体例

O(1) の例：配列の特定位置にアクセス

func getElement(arr []int, index int) int {
    return arr[index]  // 配列のサイズに関係なく一定時間
}

O(n) の例：配列の全要素を処理

func sumArray(arr []int) int {
    sum := 0
    for _, num := range arr {  // 配列のサイズに比例した時間
        sum += num
    }
    return sum
}

O(n²) の例：二重ループ

func printPairs(arr []int) {
    for i := 0; i < len(arr); i++ {
        for j := 0; j < len(arr); j++ {  // n × n = n²
            fmt.Printf("(%d, %d) ", arr[i], arr[j])
        }
    }
}

重複除去アルゴリズムでのBig O分析

Map/Set使用版 - O(n)

for _, num := range nums {        // n回のループ
    if !seen[num] {              // O(1) - map検索
        seen[num] = true         // O(1) - map更新
        result = append(result, num)  // O(1) - append
    }
}
// 全体：n × O(1) = O(n)

includes使用版 - O(n²)

for (const num of nums) {           // n回のループ
    if (!result.includes(num)) {    // O(n) - 配列全体を検索
        result.push(num);           // O(1) - push
    }
}
// 全体：n × O(n) = O(n²)

なぜBig Oが重要なのか？

実際のデータサイズでの比較

データサイズ	O(n)	O(n²)	差
100個	100回	10,000回	100倍
1,000個	1,000回	1,000,000回	1,000倍
10,000個	10,000回	100,000,000回	10,000倍

データが大きくなるほど、効率的なアルゴリズムの重要性が増します。

計算量の比較

方法	時間計算量	空間計算量	説明
map/Set使用	O(n)	O(n)	各要素について平均O(1)の検索
includes使用	O(n²)	O(n)	各要素について O(n)の検索

両言語の比較とまとめ

Goの特徴

メリット：

明示的で理解しやすい
メモリ効率が良い（容量の事前指定）
型安全性が高い

注意点：

冗長に見える場合がある
使わない変数はエラーになる

TypeScriptの特徴