use-sparse-set

use-sparse-set

When to Use

• Infinite or very large coordinate spaces
• Only a few elements are "active" at any time
• Need O(1) membership testing
• Natural union/intersection operations apply
• Game of Life, sparse matrices, active cell tracking

When NOT to Use

• Dense data where most cells have values
• Need array indexing or slicing
• Matrix operations (use numpy)

The Pattern

Use Python sets to represent sparse collections. Only store elements that exist/matter.

# Instead of 2D array:
# grid = [[0]*1000 for _ in range(1000)]  # Wastes memory

# Use set of coordinates:
active_cells = {(3, 5), (10, 20), (100, 200)}

# Operations are natural
(5, 5) in active_cells  # O(1) membership
active_cells.add((7, 7))  # O(1) add
active_cells |= other_set  # Union
active_cells &= valid_region  # Intersection

Example (from pytudes Life.ipynb)

Cell = Tuple[int, int]
World = Set[Cell]  # Only live cells stored

# Initial state - just the active cells
glider = {(1, 0), (2, 1), (0, 2), (1, 2), (2, 2)}

def neighbors(cell):
    """All 8 neighbors of a cell."""
    x, y = cell
    return [(x+dx, y+dy)
            for dx in [-1, 0, 1]
            for dy in [-1, 0, 1]
            if (dx, dy) != (0, 0)]

def neighbor_counts(world):
    """Count neighbors for all relevant cells."""
    from collections import Counter
    return Counter(n for cell in world for n in neighbors(cell))

def next_generation(world):
    """Game of Life: 3 neighbors = born, 2-3 = survive."""
    counts = neighbor_counts(world)
    return {cell for cell, count in counts.items()
            if count == 3 or (count == 2 and cell in world)}

# Can handle any size - sparse representation!
huge_world = {(1000000, 1000000), (1000001, 1000000)}
next_gen = next_generation(huge_world)  # Works fine

Key Principles

1. Only store what exists: Empty cells don't consume memory
2. Infinite space is free: No bounds needed
3. Set operations map to problems: Union = combine, intersection = overlap
4. Tuples are hashable: Coordinates work as set elements
5. Counter for aggregation: Count "votes" from neighbors