😸

Go 文法 Tips

2025/05/19に公開

 背景LeetCode でアルゴリズムを勉強する際に Go で記述していたのですが、その中で気づいた点がいくつかありました。

せっかくなので、将来の自分のためにも Tips をまとめたいと思います。

 map// map[int]int 型の変数を作る（キーが int、値も int）
counts := make(map[int]int)

// キー x の値にインクリメント
counts[x]++

// 既存のキーを読む（キーがなければゼロ値＝0 が返る）
c := counts[x]

// キーを削除
delete(counts, x)

// map の長さ（キーの数）
length := len(counts)

 for ループのパターン
 (1) for-range：シーケンス／map の走査// スライス
for i, v := range []int{10, 20, 30} {
    fmt.Printf("i=%d, v=%d\n", i, v)
}
// map
for k, v := range map[string]int{"a":1, "b":2} {
    fmt.Printf("k=%s, v=%d\n", k, v)
}
インデックスだけが欲しい： for i := range nums { … }
値だけが欲しい： for _, v := range nums { … }

 (2) 初期化・条件・後処理を持つ古典的 for// C風ループ
for i := 0; i < 5; i++ {
    fmt.Println(i)
}
// while 風
i := 0
for i < 5 {
    fmt.Println(i)
    i++
}
// 無限ループ
for {
    // break や return で抜ける
}

 comma-ok イディオムGo では、map から要素を取り出すときに「キーが存在するか」を同時に判定できる “comma-ok” イディオムがあります。

例えば、m が map[int]string のとき：
m := map[int]string{
    1: "one",
    2: "two",
}

// 値だけ取り出す場合（キーがなければゼロ値 "" が返る）
v := m[3]       // v == ""

// キーの存在判定も同時に行う場合
v, ok := m[2]   // ok==true, v=="two"
v2, ok2 := m[5] // ok2==false, v2==""

// 判定してから処理する例
if val, exists := m[2]; exists {
    fmt.Printf("キー 2 は存在します。値=%q\n", val)
} else {
    fmt.Println("キー 2 は存在しません。")
}

 計算量アルゴリズムの漸近的な計算量（Big O 表記）は、「入力サイズ n が増えたときに必要な基本操作（ループの反復回数や再帰呼び出し回数など）がどれだけ増えるか」を見ることで求めます。以下、代表的なパターンごとに「どう数えるか」を説明します。

 1. O(n)：線形時間
例：単一ループ
for i := 0; i < n; i++ {
    // 定数時間の処理
}
ループが i=0 から i=n-1 まで ちょうど n 回 回る。
ループ内の処理を 1 回「定数時間」とすれば、合計で \Theta(n)。
定数倍や低次項を無視し、線形 （入力サイズに比例）なので O(n)。

 2. O(n^2)：二重ループ・全ペア比較
例：ネストしたループ
for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        // 定数時間の処理
    }
}
外側ループが n 回、内側ループも毎回 n 回走るので、合計 n \times n = n^2 回。
よって、二次的に増えるので O(n^2)。

 3. O(n\log n)：分割統治・ソート
例：マージソート（Merge Sort）
function mergeSort(A[1..n]):
    if n ≤ 1: return A
    mid = n / 2
    L = mergeSort(A[1..mid])
    R = mergeSort(A[mid+1..n])
    return merge(L, R)  // O(n) のマージ処理
配列を半分ずつに分割 → 再帰的にソート → 最後に長さ n の配列をマージ。
再帰式は

[

T(n) = 2,T\bigl(\tfrac n2\bigr) + O(n)

]
これは「Master 定理」で解くと T(n)=O(n\log n)。（\log は底 2）
実際、深さ \log n の再帰があり、各レイヤーで合計 O(n) のマージを行うため。

 4. その他のパターン


計算量
主な例・パターン
数え方のポイント


O(1)
添字アクセス、変数代入
定数回しか動かない

O(\log n)
二分探索（バイナリサーチ）
検索範囲が半分 → さらに半分…と割る → 深さ \log n

O(n^k)
k 重ループ
n のループを k 回ネスト

O(2^n)
再帰的な全列挙（フィボナッチの素朴実装）など
再帰呼び出し数が指数関数的に増える


 5. 実際の「数え方」手順
基本操作を定める
「ループ内の比較」「再帰呼び出し」「配列アクセス」など、どれを“1 操作”とみなすか決める。
構造ごとに反復回数を数える
単一ループ → 回数 n
ネスト → 乗算で n^2, n^3 …
再帰 → 再帰式を立てる（Master 定理や繰り返し展開で解く）
定数倍・低次項を捨てる
漸近表記なので、例えば 3n + 5 → O(n)、2n^2 + 10n → O(n^2)。
最悪・平均・最良の場合
アルゴリズムによってはケース別に異なることがあるので、必要なら区別して表記。

 まとめ

単純ループ → O(n)

二重ループ → O(n^2)

分割統治（ソートなど） → O(n\log n)（再帰式を Master 定理などで解く）

二分探索 → O(\log n)

定数処理 → O(1)
これらのパターンを組み合わせて、アルゴリズム全体の計算量を推定します。まずは身近なループ・再帰の反復回数を「どう数えるか」を意識してみてください。

 HashSetGo に限らず一般に…

 HashSet と HashMap の違い



HashSet
HashMap (辞書・連想配列)


主な役割
「要素の集合」を表現する
「キー ↔ 値」のペアを管理する

データ構造
キーだけを保ち、重複を許さない
キーとそれに対応する値を保持

主な操作
・要素の追加・削除・包含判定
・キーから値の取得・更新・削除

計算量 (平均)
追加・検索・削除ともに O(1)
キー検索・挿入・削除ともに O(1)


HashSet は、集合演算（和集合・差集合など）や重複排除が必要な場面で使います。

HashMap は、何らかのキー（ID、文字列など）に対して付帯情報（数値、構造体など）を紐づけたいときに使います。

 Go での表現

 1. HashMap の例 (map[K]V)
Go の組み込み型 map がそのままハッシュマップです。
// キーが string、値が int のハッシュマップ
ages := make(map[string]int)

// 追加・更新
ages["Alice"] = 30
ages["Bob"]   = 25

// 取得（キーがなければゼロ値 0 が返る）
fmt.Println(ages["Alice"])    // 30
fmt.Println(ages["Charlie"])  // 0

// 存在判定
if v, ok := ages["Charlie"]; ok {
    fmt.Println("Charlie:", v)
} else {
    fmt.Println("Charlie は未登録")
}

// 削除
delete(ages, "Bob")

 2. HashSet の例 (map[T]struct{})
Go には組み込みの「Set」型がないので、キーだけを扱う map を代用します。
値の部分には struct{}（0 バイト）か bool を入れるのが慣例です。
// int の集合 (HashSet) を表現
set := make(map[int]struct{})

// 要素の追加
set[3] = struct{}{}
set[7] = struct{}{}

// 含むかどうかの判定
if _, exists := set[3]; exists {
    fmt.Println("3 がセットに含まれる")
}

// 削除
delete(set, 7)

// 全要素の列挙
for x := range set {
    fmt.Println(x)
}

 ポイント
値を struct{} にするとメモリ的に最小限（0 バイト）。
値を bool にすると true／false が取れる（あえて false を入れるケースは少ないですが、可読性を重視する場合に）。
// bool を使った例
set2 := make(map[string]bool)
set2["apple"] = true
if set2["banana"] {
    // banana がある場合だけ true が返る
}

 まとめ

HashMap はそのまま map[Key]Value。

HashSet は map[Element]struct{} や map[Element]bool で擬似的に実現。
キーの存在判定には “comma-ok” イディオムを使う (_, ok := m[key])。
Go ではどちらも組み込みの map だけでシンプルに表現できるのが強みです。ぜひ手を動かして慣れてみてください！

 struct{}{}struct{}{} は「空の構造体（empty struct）のリテラル値」を表しています。

 1.struct{}とは？
struct{} は「フィールドをひとつも持たない構造体型」を定義する型名です。
空の構造体はゼロサイズ（メモリ上のサイズが 0 バイト）なので、複数個あっても追加のメモリを消費しません。
var x struct{}      // 型としての宣言。x の型は struct{} で、値はゼロ値（struct{}{} と同じ）

 2.struct{}{}が意味するもの
先ほどの型 struct{} に対する「コンポジットリテラル（composite literal）」。
フィールドがないので、中身の {} も空です。
// リテラルで生成した空の構造体値
v := struct{}{}     // v の型は struct{}、値は空（ゼロ値）

 3. なぜ map の値に使うのか？
Go には組み込みの Set 型がないので、map[Key]struct{} を使って「キーの集合」を表現するのが慣例です。
// int の集合を表す map
set := make(map[int]struct{})

// 追加
set[42] = struct{}{}

// 存在チェック
if _, ok := set[42]; ok {
    fmt.Println("42 が含まれる")
}

// 削除
delete(set, 42)
値に struct{} を使うメリット
メモリをまったく消費しない（1 要素あたり 0 バイト）
map[int]bool のように bool を値にするよりも、意図（値を保持しない）が明確


 4. サイズを確かめる例
package main

import (
    "fmt"
    "unsafe"
)

func main() {
    var a struct{}
    fmt.Println("Size of struct{}:", unsafe.Sizeof(a)) // → 0
}
このように、struct{}{} は「中身が空」の特殊な値として、主に集合（Set）やチャンネルのシグナリング用途などで使われます。

Go 文法 Tips

背景

map

for ループのパターン

(1) for-range：シーケンス／map の走査

(2) 初期化・条件・後処理を持つ古典的 for

`comma-ok` イディオム

計算量

1. O(n)：線形時間

2. O(n^2)：二重ループ・全ペア比較

3. O(n\log n)：分割統治・ソート

4. その他のパターン

5. 実際の「数え方」手順

まとめ

HashSet

HashSet と HashMap の違い

Go での表現

1. HashMap の例 (map[K]V)

2. HashSet の例 (map[T]struct{})

ポイント

まとめ

struct{}{}

1.struct{}とは？

2.struct{}{}が意味するもの

3. なぜ map の値に使うのか？

4. サイズを確かめる例

Discussion

計算量	主な例・パターン	数え方のポイント
O(1)	添字アクセス、変数代入	定数回しか動かない
O(\log n)	二分探索（バイナリサーチ）	検索範囲が半分 → さらに半分…と割る → 深さ \log n
O(n^k)	k 重ループ	n のループを k 回ネスト
O(2^n)	再帰的な全列挙（フィボナッチの素朴実装）など	再帰呼び出し数が指数関数的に増える

	HashSet	HashMap (辞書・連想配列)
主な役割	「要素の集合」を表現する	「キー ↔ 値」のペアを管理する
データ構造	キーだけを保ち、重複を許さない	キーとそれに対応する値を保持
主な操作	・要素の追加・削除・包含判定	・キーから値の取得・更新・削除
計算量 (平均)	追加・検索・削除ともに O(1)	キー検索・挿入・削除ともに O(1)