lab3.py

# ============================================================
# Хранение разреженных матриц — 5 форматов
# Матрица задаётся вручную (список строк, 0 = пустая ячейка)
# ============================================================

matrix = [
    [1, 0, 0, 0, 2, 0],
    [0, 0, 3, 4, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 8, 0, 5],
    [0, 0, 0, 0, 0, 0],
    [0, 7, 1, 0, 0, 6],
]

# ============================================================
# Вспомогательные функции
# ============================================================

def print_original(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    print("  Исходная матрица A:")
    print("  " + "-----" * cols)
    for row in matrix:
        print("  | " + "  ".join(f"{v:2}" for v in row) + " |")
    print("  " + "-----" * cols)
    total = rows * cols
    non_zero = sum(1 for r in matrix for v in r if v != 0)
    zero = total - non_zero
    print(f"\n  Всего элементов:     {total}")
    print(f"  Ненулевых:           {non_zero}")
    print(f"  Нулевых (пустых):    {zero}")
    print(f"  Разреженность:       {zero/total*100:.1f}% нулей")

def get_nonzero(matrix):
    """Возвращает список (row, col, value) для всех ненулевых элементов."""
    result = []
    for i, row in enumerate(matrix):
        for j, val in enumerate(row):
            if val != 0:
                result.append((i, j, val))
    return result

def print_array(name, arr):
    print(f"  {name}: [ " + "  ".join(f"{v}" for v in arr) + " ]")

# ============================================================
# 1. COO — Coordinate Format (Координатный формат)
#    Хранит три массива: Value, Row, Col
#    Каждый i-й элемент описывает одно ненулевое значение
# ============================================================

def coo(matrix):
    print("\n" + "=" * 60)
    print("  ФОРМАТ 1: COO (Coordinate Format)")
    print("=" * 60)
    print("  Идея: для каждого ненулевого элемента храним тройку")
    print("        (значение, номер строки, номер столбца).")
    print()

    nz = get_nonzero(matrix)

    values   = [v   for (i, j, v) in nz]
    rows     = [i   for (i, j, v) in nz]
    cols     = [j   for (i, j, v) in nz]

    print("  Перебор ненулевых элементов:")
    for (i, j, v) in nz:
        print(f"    A[{i}][{j}] = {v}")

    print()
    print_array("Value", values)
    print_array("Row  ", rows)
    print_array("Col  ", cols)
    print(f"\n  Память: {len(values) * 3} ячеек вместо {len(matrix)*len(matrix[0])}")

    return {"Value": values, "Row": rows, "Col": cols}

# ============================================================
# 2. CSR — Compressed Sparse Row (Сжатые строки)
#    Value   — все ненулевые значения слева направо, строка за строкой
#    Col     — столбцы этих значений
#    RowIndex — где в Value начинается каждая строка (длина = n_rows + 1)
# ============================================================

def csr(matrix):
    print("\n" + "=" * 60)
    print("  ФОРМАТ 2: CSR (Compressed Sparse Row)")
    print("=" * 60)
    print("  Идея: Value и Col — как в COO, но вместо Row-массива")
    print("        храним RowIndex: индекс начала каждой строки в Value.")
    print()

    values    = []
    col_idx   = []
    row_index = [0]

    for i, row in enumerate(matrix):
        count = 0
        for j, val in enumerate(row):
            if val != 0:
                values.append(val)
                col_idx.append(j)
                count += 1
        row_index.append(row_index[-1] + count)
        print(f"    Строка {i}: {count} ненулевых → RowIndex теперь {row_index}")

    print()
    print_array("Value   ", values)
    print_array("Col     ", col_idx)
    print_array("RowIndex", row_index)
    print(f"\n  Память: {len(values)*2 + len(row_index)} ячеек вместо {len(matrix)*len(matrix[0])}")
    print(f"  RowIndex[i+1] - RowIndex[i] = количество ненулевых в строке i")

    return {"Value": values, "Col": col_idx, "RowIndex": row_index}

# ============================================================
# 3. CSC — Compressed Sparse Column (Сжатые столбцы)
#    Аналог CSR, но по столбцам
#    Value   — ненулевые значения сверху вниз, столбец за столбцом
#    Row     — строки этих значений
#    ColIndex — где в Value начинается каждый столбец
# ============================================================

def csc(matrix):
    print("\n" + "=" * 60)
    print("  ФОРМАТ 3: CSC (Compressed Sparse Column)")
    print("=" * 60)
    print("  Идея: то же что CSR, но обходим матрицу по столбцам.")
    print()

    n_rows = len(matrix)
    n_cols = len(matrix[0])

    values    = []
    row_idx   = []
    col_index = [0]

    for j in range(n_cols):
        count = 0
        for i in range(n_rows):
            val = matrix[i][j]
            if val != 0:
                values.append(val)
                row_idx.append(i)
                count += 1
        col_index.append(col_index[-1] + count)
        print(f"    Столбец {j}: {count} ненулевых → ColIndex теперь {col_index}")

    print()
    print_array("Value   ", values)
    print_array("Row     ", row_idx)
    print_array("ColIndex", col_index)
    print(f"\n  Память: {len(values)*2 + len(col_index)} ячеек вместо {n_rows*n_cols}")

    return {"Value": values, "Row": row_idx, "ColIndex": col_index}

# ============================================================
# 4. DOK — Dictionary of Keys (Словарь ключей)
#    Словарь: (строка, столбец) → значение
#    Только ненулевые элементы
# ============================================================

def dok(matrix):
    print("\n" + "=" * 60)
    print("  ФОРМАТ 4: DOK (Dictionary of Keys)")
    print("=" * 60)
    print("  Идея: словарь, где ключ = (строка, столбец),")
    print("        значение = элемент матрицы. Нули не хранятся.")
    print()

    d = {}
    for i, row in enumerate(matrix):
        for j, val in enumerate(row):
            if val != 0:
                d[(i, j)] = val

    print("  Содержимое словаря:")
    for key, val in d.items():
        print(f"    ({key[0]}, {key[1]}) → {val}")

    print(f"\n  Доступ к элементу: dict.get((i, j), 0)")
    print(f"  Память: {len(d)} записей вместо {len(matrix)*len(matrix[0])}")

    return d

# ============================================================
# 5. ELLPACK (ELL)
#    Две матрицы одинакового размера (n_rows × max_nnz_per_row):
#      Value  — значения (строки дополнены нулями до одинаковой длины)
#      Column — номера столбцов (для нулей-заполнителей тоже 0)
#    max_nnz_per_row = максимальное кол-во ненулевых среди всех строк
# ============================================================

def ellpack(matrix):
    print("\n" + "=" * 60)
    print("  ФОРМАТ 5: ELLPACK (ELL)")
    print("=" * 60)
    print("  Идея: две матрицы размером (строки × макс.ненулевых в строке).")
    print("        Value — сами значения, Column — их столбцы.")
    print("        Короткие строки дополняются нулями (паддинг).")
    print()

    rows_data = []
    for i, row in enumerate(matrix):
        nz_in_row = [(j, val) for j, val in enumerate(row) if val != 0]
        rows_data.append(nz_in_row)

    max_nnz = max(len(r) for r in rows_data)
    print(f"  Максимум ненулевых в одной строке: {max_nnz}")
    print(f"  Размер каждой из двух матриц: {len(matrix)} × {max_nnz}")
    print()

    val_matrix = []
    col_matrix = []

    for i, nz_in_row in enumerate(rows_data):
        val_row = [v   for (j, v) in nz_in_row] + [0] * (max_nnz - len(nz_in_row))
        col_row = [j   for (j, v) in nz_in_row] + [0] * (max_nnz - len(nz_in_row))
        val_matrix.append(val_row)
        col_matrix.append(col_row)
        pad = max_nnz - len(nz_in_row)
        print(f"    Строка {i}: ненулевых={len(nz_in_row)}, паддинг={pad} → "
              f"Value={val_row}  Column={col_row}")

    col_w = 4
    print("\n  Матрица Value:")
    for row in val_matrix:
        print("    [ " + "  ".join(f"{v:{col_w}}" for v in row) + " ]")

    print("\n  Матрица Column:")
    for row in col_matrix:
        print("    [ " + "  ".join(f"{v:{col_w}}" for v in row) + " ]")

    print(f"\n  Память: {len(matrix) * max_nnz * 2} ячеек вместо {len(matrix)*len(matrix[0])}")

    return {"Value": val_matrix, "Column": col_matrix}

# ============================================================
# Запуск
# ============================================================

print("=" * 60)
print("  ХРАНЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ — 5 ФОРМАТОВ")
print("=" * 60)
print_original(matrix)

coo_result     = coo(matrix)
csr_result     = csr(matrix)
csc_result     = csc(matrix)
dok_result     = dok(matrix)
ell_result     = ellpack(matrix)

print("\n" + "=" * 60)
print("  ИТОГОВОЕ СРАВНЕНИЕ ФОРМАТОВ")
print("=" * 60)
n = len(matrix) * len(matrix[0])
nz = sum(1 for r in matrix for v in r if v != 0)
print(f"  Исходная матрица:  {n} ячеек  ({nz} ненулевых)\n")
print(f"  {'Формат':<10} {'Структура хранения':<40} {'Ячеек'}")
print(f"  {'-'*60}")
print(f"  {'COO':<10} {'Value + Row + Col':<40} {nz * 3}")
print(f"  {'CSR':<10} {'Value + Col + RowIndex':<40} {nz * 2 + len(matrix) + 1}")
print(f"  {'CSC':<10} {'Value + Row + ColIndex':<40} {nz * 2 + len(matrix[0]) + 1}")
print(f"  {'DOK':<10} {'dict (i,j)->v':<40} {nz} записей")
max_nnz = max(sum(1 for v in r if v != 0) for r in matrix)
print(f"  {'ELLPACK':<10} {'Value-матрица + Column-матрица':<40} {len(matrix) * max_nnz * 2}")