🧠 Продвинутая задача на C++ — Оптимальный доступ к матрице с кешированием

Задача:
У вас есть матрица N x M, хранящаяся в виде одномерного массива (row-major).
Нужно реализовать класс Matrix, поддерживающий:
- Быстрый доступ get(i, j) и set(i, j, value)
- Локальность данных при сканировании по строкам и по столбцам
- При этом: сравнить производительность строкового и столбцового прохода

int main() {
    Matrix mat(10000, 10000);
    // Заполнить матрицу числами
    for (int i = 0; i < 10000; ++i)
        for (int j = 0; j < 10000; ++j)
            mat.set(i, j, i + j);

    // Сумма по строкам
    long long row_sum = 0;
    for (int i = 0; i < 10000; ++i)
        for (int j = 0; j < 10000; ++j)
            row_sum += mat.get(i, j);

    // Сумма по столбцам
    long long col_sum = 0;
    for (int j = 0; j < 10000; ++j)
        for (int i = 0; i < 10000; ++i)
            col_sum += mat.get(i, j);
}

Вопрос:
Почему сканирование по строкам быстрее, чем по столбцам, даже если данные одинаковые?

---

Разбор:

class Matrix {
private:
    int rows, cols;
    std::vector<int> data;

public:
    Matrix(int r, int c) : rows(r), cols(c), data(r * c) {}

    int get(int i, int j) const {
        return data[i * cols + j];
    }

    void set(int i, int j, int value) {
        data[i * cols + j] = value;
    }
};

Ответ:
Память в C++ выделяется линейно.
В std::vector<int> data, элементы строки хранятся подряд в памяти.
То есть mat[0][0], mat[0][1], ..., mat[0][9999] идут подряд.

Когда мы сканируем по строкам, процессор использует кеш строк памяти эффективно.
Когда же мы сканируем по столбцам, мы прыгаем по памяти через cols шагов → кеш не успевает подгружать нужные блоки → больше cache misses → медленнее.

---

🧠 Вывод:
- Даже при правильном коде, порядок доступа к памяти критически важен
- Понимание устройства кеша CPU помогает писать реально быстрый код
- Такие задачи полезны для подготовки к системному программированию, оптимизации и собеседованиям

#cpp #performance #cache #memory #optimize