use-sparse-set

name: use-sparse-set description: "For sparse data: infinite grids, large spaces with few active elements, membership testing, set operations on coordinates or states."

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

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