課題8: マップを使ったデータ処理

課題概要

マップを使って、実用的なデータ処理ツールを実装します。頻度カウント、キャッシュ、グルーピング、セット演算など、マップの典型的な使用パターンを学びます。

マンダトリー要件

要件1: 単語カウンターとテキスト解析

テキスト解析ツールを実装してください。

ファイル: textanalyzer/analyzer.go

package textanalyzer

// WordCount は単語の出現回数を返す
func WordCount(text string) map[string]int {
    // TODO: 実装してください
    // - 単語を空白で分割
    // - 大文字小文字を区別しない
    // - 記号を除去
}

// CharFrequency は文字の出現頻度を返す
func CharFrequency(text string) map[rune]int {
    // TODO: 実装してください
}

// TopWords は出現回数の多い順にn個の単語を返す
func TopWords(text string, n int) []WordFreq {
    // TODO: 実装してください
}

type WordFreq struct {
    Word  string
    Count int
}

// UniqueWords はユニークな単語の数を返す
func UniqueWords(text string) int {
    // TODO: 実装してください
}

// WordPositions は各単語の出現位置を返す
func WordPositions(text string) map[string][]int {
    // TODO: 実装してください
    // 各単語がテキスト中の何番目に出現するかを記録
}

// IsAnagram は2つの文字列がアナグラムか判定
func IsAnagram(s1, s2 string) bool {
    // TODO: 実装してください
    // 文字の出現回数が同じならアナグラム
}

要件2: LRUキャッシュ

LRU（Least Recently Used）キャッシュを実装してください。

ファイル: cache/lru.go

package cache

import (
    "errors"
)

var ErrNotFound = errors.New("key not found")

type LRUCache struct {
    capacity int
    cache    map[string]*Node
    head     *Node
    tail     *Node
}

type Node struct {
    key   string
    value interface{}
    prev  *Node
    next  *Node
}

// NewLRUCache はLRUキャッシュを作成
func NewLRUCache(capacity int) *LRUCache {
    // TODO: 実装してください
    // head と tail のダミーノードを作成
}

// Get は値を取得し、最近使用済みにする
func (c *LRUCache) Get(key string) (interface{}, error) {
    // TODO: 実装してください
    // - キーが存在すれば値を返し、先頭に移動
    // - 存在しなければ ErrNotFound を返す
}

// Put は値を保存し、最近使用済みにする
func (c *LRUCache) Put(key string, value interface{}) {
    // TODO: 実装してください
    // - キーが存在すれば更新し、先頭に移動
    // - 存在しなければ追加し、先頭に配置
    // - 容量を超える場合は最後の要素を削除
}

// Size は現在のサイズを返す
func (c *LRUCache) Size() int {
    // TODO: 実装してください
}

// Clear はすべての要素を削除
func (c *LRUCache) Clear() {
    // TODO: 実装してください
}

// Keys はすべてのキーを返す（新しい順）
func (c *LRUCache) Keys() []string {
    // TODO: 実装してください
}

要件3: データグルーピングとインデックス

データのグルーピングとインデックス作成機能を実装してください。

ファイル: grouping/grouper.go

package grouping

type Person struct {
    ID    int
    Name  string
    Age   int
    City  string
    Email string
}

// GroupByCity は都市ごとにグループ化
func GroupByCity(people []Person) map[string][]Person {
    // TODO: 実装してください
}

// GroupByAge は年齢ごとにグループ化
func GroupByAge(people []Person) map[int][]Person {
    // TODO: 実装してください
}

// GroupByAgeRange は年齢層ごとにグループ化
func GroupByAgeRange(people []Person, rangeSize int) map[string][]Person {
    // TODO: 実装してください
    // 例: rangeSize=10 → "0-9", "10-19", "20-29", ...
}

// Index はIDでインデックスを作成
func Index(people []Person) map[int]Person {
    // TODO: 実装してください
}

// MultiIndex は複数フィールドでインデックス
func MultiIndex(people []Person) *PersonIndex {
    // TODO: 実装してください
}

type PersonIndex struct {
    byID    map[int]Person
    byEmail map[string]Person
    byCity  map[string][]Person
}

// FindByID はIDで検索
func (pi *PersonIndex) FindByID(id int) (Person, bool) {
    // TODO: 実装してください
}

// FindByEmail はメールアドレスで検索
func (pi *PersonIndex) FindByEmail(email string) (Person, bool) {
    // TODO: 実装してください
}

// FindByCity は都市で検索
func (pi *PersonIndex) FindByCity(city string) []Person {
    // TODO: 実装してください
}

要件4: セット操作

セット型とその操作を実装してください。

ファイル: set/set.go

package set

type Set map[string]struct{}

// New は空のセットを作成
func New(values ...string) Set {
    // TODO: 実装してください
}

// Add は要素を追加
func (s Set) Add(value string) {
    // TODO: 実装してください
}

// Remove は要素を削除
func (s Set) Remove(value string) {
    // TODO: 実装してください
}

// Contains は要素が含まれているか判定
func (s Set) Contains(value string) bool {
    // TODO: 実装してください
}

// Size は要素数を返す
func (s Set) Size() int {
    // TODO: 実装してください
}

// ToSlice はスライスに変換
func (s Set) ToSlice() []string {
    // TODO: 実装してください
}

// Union は和集合を返す
func (s Set) Union(other Set) Set {
    // TODO: 実装してください
}

// Intersection は積集合を返す
func (s Set) Intersection(other Set) Set {
    // TODO: 実装してください
}

// Difference は差集合を返す（sにあってotherにない）
func (s Set) Difference(other Set) Set {
    // TODO: 実装してください
}

// IsSubset はsがotherの部分集合か判定
func (s Set) IsSubset(other Set) bool {
    // TODO: 実装してください
}

// IsSuperset はsがotherの上位集合か判定
func (s Set) IsSuperset(other Set) bool {
    // TODO: 実装してください
}

// Equal は2つのセットが等しいか判定
func (s Set) Equal(other Set) bool {
    // TODO: 実装してください
}

期待される出力

// 単語カウント
text := "hello world hello"
counts := textanalyzer.WordCount(text)
// map[string]int{"hello": 2, "world": 1}

topWords := textanalyzer.TopWords(text, 2)
// []WordFreq{{"hello", 2}, {"world", 1}}

// LRUキャッシュ
cache := cache.NewLRUCache(2)
cache.Put("a", 1)
cache.Put("b", 2)
value, _ := cache.Get("a")  // 1, "a"が最近使用
cache.Put("c", 3)           // "b"が削除される
_, err := cache.Get("b")    // ErrNotFound

// グルーピング
people := []grouping.Person{
    {1, "Alice", 25, "Tokyo", "alice@example.com"},
    {2, "Bob", 30, "Osaka", "bob@example.com"},
    {3, "Carol", 25, "Tokyo", "carol@example.com"},
}
byCity := grouping.GroupByCity(people)
// map[string][]Person{
//     "Tokyo": {{1, "Alice", ...}, {3, "Carol", ...}},
//     "Osaka": {{2, "Bob", ...}},
// }

// セット
s1 := set.New("a", "b", "c")
s2 := set.New("b", "c", "d")
union := s1.Union(s2)          // {"a", "b", "c", "d"}
intersection := s1.Intersection(s2)  // {"b", "c"}

ボーナス課題

ボーナス1: タイムベースキャッシュ

TTL（Time To Live）付きキャッシュを実装してください。

package cache

import (
    "sync"
    "time"
)

type TTLCache struct {
    mu    sync.RWMutex
    cache map[string]*CacheItem
    ttl   time.Duration
}

type CacheItem struct {
    value      interface{}
    expiration time.Time
}

// NewTTLCache はTTLキャッシュを作成
func NewTTLCache(ttl time.Duration) *TTLCache {
    // TODO: 実装してください
    // バックグラウンドで期限切れアイテムを削除
}

// Get は値を取得（期限切れならnil）
func (c *TTLCache) Get(key string) interface{} {
    // TODO: 実装してください
}

// Set は値を保存（TTL付き）
func (c *TTLCache) Set(key string, value interface{}) {
    // TODO: 実装してください
}

// SetWithTTL は個別のTTLで保存
func (c *TTLCache) SetWithTTL(key string, value interface{}, ttl time.Duration) {
    // TODO: 実装してください
}

// Delete は削除
func (c *TTLCache) Delete(key string) {
    // TODO: 実装してください
}

// Clear はすべて削除
func (c *TTLCache) Clear() {
    // TODO: 実装してください
}

ボーナス2: グラフ構造（隣接リスト）

マップを使ったグラフ構造を実装してください。

package graph

type Graph struct {
    nodes map[string]*Node
    edges map[string]map[string]int  // from -> to -> weight
}

type Node struct {
    ID    string
    Value interface{}
}

// NewGraph はグラフを作成
func NewGraph() *Graph {
    // TODO: 実装してください
}

// AddNode はノードを追加
func (g *Graph) AddNode(id string, value interface{}) {
    // TODO: 実装してください
}

// AddEdge はエッジを追加（重み付き）
func (g *Graph) AddEdge(from, to string, weight int) error {
    // TODO: 実装してください
}

// RemoveNode はノードを削除
func (g *Graph) RemoveNode(id string) {
    // TODO: 実装してください
}

// Neighbors は隣接ノードを返す
func (g *Graph) Neighbors(id string) []string {
    // TODO: 実装してください
}

// HasPath はパスが存在するか判定（BFS）
func (g *Graph) HasPath(from, to string) bool {
    // TODO: 実装してください
}

// ShortestPath は最短パスを返す（BFS）
func (g *Graph) ShortestPath(from, to string) []string {
    // TODO: 実装してください
}

ボーナス3: トライ木（Prefix Tree）

マップを使ったトライ木を実装してください。

package trie

type Trie struct {
    root *TrieNode
}

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

// NewTrie はトライ木を作成
func NewTrie() *Trie {
    // TODO: 実装してください
}

// Insert は単語を挿入
func (t *Trie) Insert(word string) {
    // TODO: 実装してください
}

// Search は単語が存在するか検索
func (t *Trie) Search(word string) bool {
    // TODO: 実装してください
}

// StartsWith は指定プレフィックスで始まる単語が存在するか
func (t *Trie) StartsWith(prefix string) bool {
    // TODO: 実装してください
}

// AutoComplete はオートコンプリート候補を返す
func (t *Trie) AutoComplete(prefix string) []string {
    // TODO: 実装してください
}

// Delete は単語を削除
func (t *Trie) Delete(word string) bool {
    // TODO: 実装してください
}

評価基準

提出方法

submission/
├── go.mod
├── textanalyzer/
│   ├── analyzer.go
│   └── analyzer_test.go
├── cache/
│   ├── lru.go
│   └── lru_test.go
├── grouping/
│   ├── grouper.go
│   └── grouper_test.go
├── set/
│   ├── set.go
│   └── set_test.go
└── bonus/
    ├── ttl/
    ├── graph/
    └── trie/

ヒント

• 単語カウント: strings.Fieldsで分割、strings.ToLowerで正規化
• LRUキャッシュ: 双方向リンクリストとマップの組み合わせ
• グルーピング: rangeでループしてマップに追加
• セット: map[T]struct{}で省メモリ
• TTLキャッシュ: time.NewTickerで定期的にクリーンアップ
• グラフ: BFSにはキューを使う

テストケース

// textanalyzer/analyzer_test.go
func TestWordCount(t *testing.T) {
    text := "Hello world hello"
    counts := WordCount(text)

    if counts["hello"] != 2 {
        t.Errorf("Expected 2 occurrences of 'hello', got %d", counts["hello"])
    }
    if counts["world"] != 1 {
        t.Errorf("Expected 1 occurrence of 'world', got %d", counts["world"])
    }
}

// cache/lru_test.go
func TestLRUCache(t *testing.T) {
    cache := NewLRUCache(2)

    cache.Put("a", 1)
    cache.Put("b", 2)

    if v, err := cache.Get("a"); err != nil || v != 1 {
        t.Error("Failed to get 'a'")
    }

    cache.Put("c", 3)  // "b" should be evicted

    if _, err := cache.Get("b"); err != ErrNotFound {
        t.Error("Expected 'b' to be evicted")
    }
}

// set/set_test.go
func TestSetOperations(t *testing.T) {
    s1 := New("a", "b", "c")
    s2 := New("b", "c", "d")

    union := s1.Union(s2)
    if union.Size() != 4 {
        t.Errorf("Union size = %d; want 4", union.Size())
    }

    intersection := s1.Intersection(s2)
    if intersection.Size() != 2 {
        t.Errorf("Intersection size = %d; want 2", intersection.Size())
    }
}

学習リソース

• Go Maps in Action
• Go by Example - Maps
• Effective Go - Maps
• LRU Cache Implementation