Iterating Maps — Optimization Exercises¶

// Build once
type BiMap struct {
    forward  map[string]int    // key -> value
    inverted map[int][]string  // value -> []key
}

func NewBiMap(m map[string]int) *BiMap {
    inv := make(map[int][]string, len(m))
    for k, v := range m {
        inv[v] = append(inv[v], k)
    }
    return &BiMap{forward: m, inverted: inv}
}

func (b *BiMap) FindByValue(target int) []string {
    return b.inverted[target] // O(1)
}

// Now: 10000 lookups = 10000 O(1) operations instead of O(n) each

// Option 1: Reuse a pre-allocated map (clear between uses)
func normalizeInto(input string, m map[string]int) {
    for k := range m { delete(m, k) } // clear
    for _, word := range strings.Fields(input) {
        m[strings.ToLower(word)]++
    }
}

// Option 2: For comparison, avoid building second map
// Count words in first, then subtract for second:
func compare(a, b string) bool {
    ma := map[string]int{}
    for _, w := range strings.Fields(strings.ToLower(a)) { ma[w]++ }
    for _, w := range strings.Fields(strings.ToLower(b)) { ma[w]-- }
    for _, v := range ma {
        if v != 0 { return false }
    }
    return true
    // One map, not two — 50% fewer allocations
}

// Cache the sorted result; only re-sort when map changes
type RankedScores struct {
    scores  map[string]int
    sorted  []string // cached sorted keys
    version int
}

func (rs *RankedScores) UpdateScore(name string, score int) {
    rs.scores[name] = score
    rs.version++ // invalidate cache
    rs.sorted = nil
}

func (rs *RankedScores) TopN(n int) []string {
    if rs.sorted == nil { // rebuild only when needed
        type kv struct{ k string; v int }
        pairs := make([]kv, 0, len(rs.scores))
        for k, v := range rs.scores { pairs = append(pairs, kv{k, v}) }
        sort.Slice(pairs, func(i, j int) bool { return pairs[i].v > pairs[j].v })
        rs.sorted = make([]string, len(pairs))
        for i, p := range pairs { rs.sorted[i] = p.k }
    }
    if n > len(rs.sorted) { n = len(rs.sorted) }
    return rs.sorted[:n]
}

// Direct lookup is O(1) — no need to range
func (c *Config) IsProduction() bool {
    return c.settings["env"] == "production"
}
// If key might not exist:
func (c *Config) IsProduction() bool {
    v, ok := c.settings["env"]
    return ok && v == "production"
}
// Speedup: O(n) → O(1). For n=1M calls with map size 3: 3M→1M operations

func union(maps ...map[string]int) map[string]int {
    // Calculate total unique keys estimate for pre-allocation
    totalSize := 0
    for _, m := range maps { totalSize += len(m) }
    // Pre-allocate with estimated capacity
    result := make(map[string]int, totalSize) // overestimates but prevents rehashing
    for _, m := range maps {
        for k, v := range m {
            result[k] += v
        }
    }
    return result
}
// Without pre-allocation: map rehashes ~log2(100) = 7 times for 100 entries
// With pre-allocation: 0 rehashes — significant for large inputs

import "sync"

func drainAll(channels map[string]chan int) map[string][]int {
    var mu sync.Mutex
    results := map[string][]int{}
    var wg sync.WaitGroup

    for name, ch := range channels {
        name, ch := name, ch
        wg.Add(1)
        go func() {
            defer wg.Done()
            close(ch)
            local := []int{}
            for v := range ch { local = append(local, v) }
            mu.Lock()
            results[name] = local
            mu.Unlock()
        }()
    }
    wg.Wait()
    return results
}
// Parallel drain: 4 channels simultaneously instead of sequentially

// Option 1: Use struct as map key (no allocation)
type UserAction struct {
    UserID int
    Action string
}
var cache = map[UserAction]struct{}{}
func hotFunction(userID int, action string) {
    key := UserAction{userID, action} // stack-allocated struct, no alloc
    _ = cache[key]
}

// Option 2: Pre-compute/intern strings if userID and action sets are small
var actionCache = map[string]struct{}{"click": {}, "view": {}, "buy": {}}
// Use canonical string references

// Option 3: Integer encoding for small bounded sets
// encode userID*1000 + actionIndex as a single int key
var actionIdx = map[string]int{"click": 0, "view": 1, "buy": 2}
var cache2 = map[int]struct{}{}
func hotFunction2(userID int, action string) {
    key := userID*1000 + actionIdx[action]
    _ = cache2[key]
}

// Build a set (map) for O(1) lookup
var blacklistSet map[string]struct{}

func init() {
    blacklist := []string{"spam@evil.com", "bad@actor.net", "fraud@scam.org"}
    blacklistSet = make(map[string]struct{}, len(blacklist))
    for _, email := range blacklist {
        blacklistSet[email] = struct{}{}
    }
}

func isBlacklisted(email string) bool {
    _, ok := blacklistSet[email] // O(1)
    return ok
}
// Speedup: O(n) → O(1) per check
// For 1000-entry blacklist checking 1M emails: 1B ops → 1M ops (1000x)

// Grades are bounded integers 0-100: use array (slice) instead of map
func countGrades(grades []int) [101]int {
    var freq [101]int
    for _, g := range grades {
        if g >= 0 && g <= 100 {
            freq[g]++
        }
    }
    return freq
}

func printDistribution(grades []int) {
    freq := countGrades(grades)
    for score, count := range freq { // array range: cache-friendly!
        if count > 0 {
            fmt.Printf("%d: %d\n", score, count)
        }
    }
}
// Benefits:
// - [101]int on stack: 0 heap allocations
// - Array access: O(1) with perfect cache behavior
// - Iteration: cache-friendly sequential access
// - 100x more memory-efficient than map for dense integer ranges

// Option 1: Pre-allocate with capacity hint per template
func processBatch(templates map[string]map[string]int, multiplier int) []map[string]int {
    results := make([]map[string]int, 0, len(templates))
    for _, tmpl := range templates {
        result := make(map[string]int, len(tmpl)) // pre-sized — no rehash
        for k, v := range tmpl {
            result[k] = v * multiplier
        }
        results = append(results, result)
    }
    return results
}

// Option 2: If multiplier 1 (pure copy): use maps.Clone (optimized)
import "maps"
func cloneBatch(templates map[string]map[string]int) []map[string]int {
    results := make([]map[string]int, 0, len(templates))
    for _, tmpl := range templates {
        results = append(results, maps.Clone(tmpl))
    }
    return results
}

// Option 3: Structural sharing — return views with lazy multiplier
type MultipliedMap struct {
    base       map[string]int
    multiplier int
}
func (m *MultipliedMap) Get(k string) int { return m.base[k] * m.multiplier }
// Zero copy! Multiplier applied on read only

// LRU cache with bounded size
type LRUCache struct {
    mu       sync.Mutex
    capacity int
    cache    map[string]*entry
    order    []string // simple LRU tracking (use container/list for O(1))
}

type entry struct {
    value []byte
}

func NewLRU(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[string]*entry, capacity),
        order:    make([]string, 0, capacity),
    }
}

func (c *LRUCache) GetOrCompute(key string, compute func() []byte) []byte {
    c.mu.Lock()
    defer c.mu.Unlock()

    if e, ok := c.cache[key]; ok {
        return e.value
    }

    if len(c.cache) >= c.capacity {
        // Evict oldest (first in order)
        oldest := c.order[0]
        c.order = c.order[1:]
        delete(c.cache, oldest)
    }

    v := compute()
    c.cache[key] = &entry{v}
    c.order = append(c.order, key)
    return v
}

// Production: use github.com/hashicorp/golang-lru or similar