#!/usr/bin/env python3
"""Dense vs sparse: the recommender matrix, DDIA 2e Ch. 4 (DataFrames/Matrices).

The book turns a relational table of movie ratings into a users x movies matrix
(Figure 3-9) for linear-algebra-based recommendation. Real ratings matrices are
almost all empty -- a user rates a tiny fraction of all movies -- so storing the
matrix densely (a number for every cell, rated or not) wastes almost everything.
A sparse representation stores only the ratings that exist.

We build one ratings matrix both ways and compare memory: a dense float32 array
vs a CSR (compressed sparse row) matrix. Then we work out the break-even density
and what the same ratio looks like at Netflix scale.

Run it:
    uv run --with numpy --with scipy python3 sparse_matrix.py
(Deterministic seed -> the sizes reproduce exactly.)
"""
import numpy as np
from scipy import sparse

USERS = 10_000
MOVIES = 5_000
DENSITY = 0.01          # 1% of cells are rated (Netflix was ~1.2%)


def main():
    n_cells = USERS * MOVIES
    n_ratings = int(n_cells * DENSITY)
    rng = np.random.default_rng(42)

    rows = rng.integers(0, USERS, size=n_ratings)
    cols = rng.integers(0, MOVIES, size=n_ratings)
    vals = rng.integers(1, 6, size=n_ratings).astype(np.float32)   # 1..5 stars

    # Dense: a float32 for every cell, rated or not.
    dense = np.zeros((USERS, MOVIES), dtype=np.float32)
    dense[rows, cols] = vals
    dense_bytes = dense.nbytes

    # Sparse CSR: store only the ratings that exist (value + column index + row pointers).
    csr = sparse.csr_matrix((vals, (rows, cols)), shape=(USERS, MOVIES))
    csr_bytes = csr.data.nbytes + csr.indices.nbytes + csr.indptr.nbytes

    mb = 1e6
    print(f"ratings matrix: {USERS:,} users x {MOVIES:,} movies = {n_cells:,} cells")
    print(f"density: {DENSITY*100:.1f}%  ({csr.nnz:,} ratings) -- like a real recommender "
          f"(Netflix was ~1.2%)\n")
    print("memory to hold the matrix:")
    print(f"    dense  (float32, every cell)          = {dense_bytes/mb:8.1f} MB")
    print(f"    sparse (CSR: value + col + row ptr)    = {csr_bytes/mb:8.1f} MB")
    print(f"    -> sparse is {dense_bytes/csr_bytes:.0f}x smaller\n")

    # Break-even: CSR stores 2 numbers per rating (value f32 + index i32 = 8 bytes)
    # vs dense 4 bytes/cell, so CSR wins below 50% density.
    print("break-even: CSR stores ~2 numbers per rating, so it saves memory below")
    print(f"            ~50% density; here the saving is 1/(2 x {DENSITY}) = {1/(2*DENSITY):.0f}x.")

    # Netflix-scale analytic (too big to allocate densely here).
    nu, nm, d = 480_500, 17_770, 0.0118
    dense_nf = nu * nm * 4
    sparse_nf = int(nu * nm * d) * 8 + (nu + 1) * 4
    print(f"\nat Netflix scale ({nu:,} x {nm:,}, {d*100:.2f}% dense), analytic:")
    print(f"    dense  ~ {dense_nf/1e9:.0f} GB   vs   sparse ~ {sparse_nf/1e9:.1f} GB  "
          f"({dense_nf/sparse_nf:.0f}x)")


if __name__ == "__main__":
    main()