Таблица продаж

Три дня подряд в небольшом кинотеатре записывали, сколько билетов продано на каждый из четырёх сеансов. Получилась таблица: три строки, по одной на день, и четыре столбца, по одному на сеанс.

Данные такие. Первый день: 3, 0, 2, 1. Второй день: 1, 4, 0, 2. Третий день: 2, 1, 3, 0.

Хранить такое удобно не линейной последовательностью, а двумерным массивом — прямоугольной таблицей. У такой таблицы две оси: строки и столбцы. Строк три, столбцов четыре. У каждой ячейки два номера: сначала номер строки, потом номер столбца. Строки нумеруются от 0 до 2, столбцы — от 0 до 3.

Слово «матрица» здесь означает именно прямоугольную таблицу, а не математический объект линейной алгебры. Нам важна структура: сетка ячеек, у каждой — пара координат.

Доступ к одной ячейке

Чтобы получить одну ячейку, нужно указать обе координаты: строку и столбец. Например, [1, 2] — это ячейка во второй строке, третьем столбце. В нашей таблице там стоит 0. Ячейка [0, 0] равна 3, [2, 3] равна 0, [1, 1] равна 4.

В принятой модели прямоугольного массива размеры таблицы известны, и вместе с координатами ячейки они позволяют найти нужный слот напрямую, без обхода соседей. Именно поэтому доступ к одной ячейке оценивается как O(1): не важно, берём мы [0, 0] или [2, 3], число шагов не зависит от положения ячейки в таблице. И ещё одно уточнение про порядок координат. Мы договорились писать [строка, столбец], и это удобная договорённость для наших таблиц, но она не универсальна. В разных областях встречается другой порядок — например, в работе с изображениями часто сначала указывают x (горизонталь), а потом y (вертикаль), что соответствует паре [столбец, строка]. Поэтому полезно не полагаться на привычку, а проверять, какой порядок принят в конкретном контексте.

Обход по строкам: сколько билетов продано за день

Первый вопрос, который хочется задать к этой таблице: сколько билетов продано за каждый день? День — это строка. Значит, нужно пройти по строке, сложить все её ячейки и вывести результат, потом перейти к следующей строке.

using System;

int[,] tickets = {
    { 3, 0, 2, 1 },
    { 1, 4, 0, 2 },
    { 2, 1, 3, 0 }
};
int rows = tickets.GetLength(0);
int cols = tickets.GetLength(1);
int total = 0;
for (int r = 0; r < rows; r++)
{
    int daySum = 0;
    for (int c = 0; c < cols; c++)
    {
        daySum += tickets[r, c];
    }
    Console.WriteLine("День " + r + ": " + daySum);
    total += daySum;
}
Console.WriteLine("Всего: " + total);

Вывод:

День 0: 6
День 1: 7
День 2: 6
Всего: 19

GetLength(0) возвращает число строк, GetLength(1) — число столбцов. Это способы узнать размеры таблицы, а не сами данные; мы пользуемся ими, чтобы не хардкодить тройку и четвёрку. Length, если бы мы её взяли, дала бы общее число ячеек — 12.

Во внешнем цикле переменная r — номер строки. Во внутреннем переменная c — номер столбца. Обращение tickets[r, c] даёт ячейку в текущей строке и текущем столбце. Внутренний цикл складывает все ячейки строки в daySum.

Сброс накопителя и его причина

Здесь стоит обратить внимание на одну деталь, от которой зависит правильность ответа. Переменная daySum объявлена внутри внешнего цикла, а не снаружи. Это значит, что на каждой новой строке она создаётся заново и начинает с нуля. Если бы мы объявили её снаружи, то к концу первой строки в ней накопилось бы 6, к концу второй — 13, а к концу третьей — 19, и мы бы получили растущий счётчик вместо суммы за день.

Переменная total, наоборот, объявлена снаружи внешнего цикла. Это общий накопитель, и он не сбрасывается между днями. В конце он показывает 19 — сумму по всей таблице.

Правило простое. Накопитель, который считает что-то для одной строки, должен начинать с нуля для каждой строки. Накопитель, который считает по всей таблице, живёт дольше всех.

Обход по столбцам: сколько билетов продано за сеанс

Теперь зададим другой вопрос: сколько билетов продано на каждый сеанс? Сеанс — это столбец. Значит, нужно пройтись по столбцу, сложить все его ячейки, потом перейти к следующему. Порядок циклов меняется: внешний теперь идёт по столбцам, а внутренний — по строкам.

using System;

int[,] tickets = {
    { 3, 0, 2, 1 },
    { 1, 4, 0, 2 },
    { 2, 1, 3, 0 }
};
int rows = tickets.GetLength(0);
int cols = tickets.GetLength(1);
for (int c = 0; c < cols; c++)
{
    int sessionSum = 0;
    for (int r = 0; r < rows; r++)
    {
        sessionSum += tickets[r, c];
    }
    Console.WriteLine("Сеанс " + c + ": " + sessionSum);
}

Вывод:

Сеанс 0: 6
Сеанс 1: 5
Сеанс 2: 5
Сеанс 3: 3

Проверим руками. Столбец 0: 3 + 1 + 2 = 6. Столбец 1: 0 + 4 + 1 = 5. Столбец 2: 2 + 0 + 3 = 5. Столбец 3: 1 + 2 + 0 = 3. Сумма по всем четырём столбцам — 19, как и при обходе по строкам. Порядок обхода не меняет общий итог, потому что в обоих случаях мы заглядываем в каждую ячейку ровно один раз. Меняется только то, как мы группируем результаты: по дням или по сеансам.

Трассировка первых двух строк

Прогоним первый пример руками на первых двух строках, чтобы увидеть, что происходит с накопителями.

Строка 0. r = 0. daySum = 0. Идём по столбцам. c = 0: tickets[0, 0] = 3, daySum = 3. c = 1: tickets[0, 1] = 0, daySum = 3. c = 2: tickets[0, 2] = 2, daySum = 5. c = 3: tickets[0, 3] = 1, daySum = 6. Печатаем «День 0: 6». Прибавляем 6 к total, total = 6.

Строка 1. r = 1. daySum снова 0 — объявление внутри внешнего цикла сбросило её. c = 0: tickets[1, 0] = 1, daySum = 1. c = 1: tickets[1, 1] = 4, daySum = 5. c = 2: tickets[1, 2] = 0, daySum = 5. c = 3: tickets[1, 3] = 2, daySum = 7. Печатаем «День 1: 7». Прибавляем 7 к total, total = 13.

На третьей строке daySum снова начнётся с нуля и дорастёт до 6, а total станет 19. Именно потому, что накопитель пересоздаётся на каждой итерации внешнего цикла, каждая строка считается независимо от предыдущей.

Размеры и стоимость

Разберёмся с двумя способами узнать размеры таблицы. GetLength(0) возвращает число строк, GetLength(1) — число столбцов. Это размеры по каждой оси в отдельности. А Length — общее число ячеек, произведение строк на столбцы. В нашей таблице Length равна 12, а не 3: Length не число строк, а именно общее количество ячеек.

Обозначить n = r * c можно всегда: это просто общее число ячеек таблицы, и в нашей модели оно равно произведению числа строк на число столбцов. Если r и c положительны, оба полных обхода — и по строкам, и по столбцам — укладываются в O(r * c), то есть в O(n): каждая ячейка посещается ровно один раз. Для полной программы полезно помнить, что кроме внутренних посещений есть ещё внешние итерации и вывод. Первая программа делает O(1 + r + r * c) работы: единица — на подготовку и общий итог, r — на внешние итерации и печать дневных сумм, r * c — на сами ячейки. Вторая программа делает O(1 + c + r * c): внешних итераций теперь c, а посещений столько же. Оценка O(n²) возникает не из факта двух вложенных циклов, а из конкретной связи размеров. Если таблица квадратная n на n и через n обозначена длина стороны, то r * c = n², и полный обход стоит O(n²). Если же через n обозначено общее число ячеек, та же работа — O(n). Смотреть надо на то, что именно растёт.

Про память: при печати сумм мы держим лишь несколько переменных — счётчики и один накопитель. Это O(1) вспомогательной памяти, вне зависимости от размера таблицы. Если же мы решим сохранить все r дневных сумм, чтобы потом что-то с ними сделать, потребуется r ячеек — это O(r) памяти, и это уже выход, а не вспомогательная память.

Где легко ошибиться

Ошибки в работе с таблицами повторяются из раза в раз, и полезно знать их в лицо.

Первая ошибка — путаница строк и столбцов на неквадратной таблице. Разберём её в двух направлениях, потому что они ведут к разным последствиям. Пусть таблица 3 на 4: rows = 3, cols = 4. Если во внутреннем цикле написать условие c < rows вместо c < cols, то есть c < 3, то мы пройдём столбцы 0, 1, 2, а столбец 3 просто пропустим. Никакого обращения к c = 3 не произойдёт — цикл остановится раньше. Программа не сломается, но результат будет неполным: последний столбец не попадёт ни в одну сумму. Если же во внешнем цикле написать r < cols вместо r < rows, то есть r < 4, то на итерации r = 3 мы попытаемся обратиться к строке 3, которой при rows = 3 не существует: допустимые номера строк — 0, 1, 2. Здесь уже выход за границы и ошибка во время выполнения. Оба случая опасны по-своему: первый даёт тихо неверный ответ, второй — явный сбой. Именно поэтому полезно мысленно проверять, какая переменная и до какого предела крутится.

Вторая — путаница порядка координат. Писать tickets[c, r] вместо tickets[r, c] — значит поменять строку и столбец местами. Иногда это даёт визуально правдоподобный, но неверный результат, особенно на квадратной таблице, где обе размерности совпадают.

Третья — знак сравнения. Цикл с условием r <= rows вместо r < rows выходит за пределы массива, потому что допустимые индексы строк — от 0 до rows − 1.

Все эти ошибки объединяет одно: они связаны с границами. Поэтому полезно вслух проверять, где начинается и где заканчивается каждая ось.

Пустые размеры

Разберём краевые случаи внимательно, потому что здесь легко спутать число посещённых ячеек с полной работой программы. Таблица 0 на 4: ноль строк, четыре столбца. Ячеек нет ни одной, читать нечего. Внешний цикл по строкам с условием r < rows = 0 не выполнится ни разу, внутренний тоже. Но программа всё равно завершится и что-то напечатает: общий итог будет равен нулю, и на экране появится «Всего: 0». То есть работа не нулевая — есть подготовка, есть финальная печать. Просто посещений ячеек не было.

Таблица 3 на 0: три строки, ноль столбцов. Ячеек по-прежнему нет, но внешний цикл по строкам выполнится три раза. Внутренний цикл не запустится ни разу, потому что cols = 0. Для каждой строки дневная сумма останется нулём, и программа напечатает три строки: «День 0: 0», «День 1: 0», «День 2: 0», а затем «Всего: 0». Второй пример — обход по столбцам — на таблице 0 на 4 поведёт себя зеркально: внешний цикл по столбцам выполнится четыре раза, и мы получим четыре сеансовых нуля, а не пустоту. В обоих случаях важно не отождествлять «нет ячеек» с «нет работы»: внешние проходы и печать выполняются независимо от того, есть ли что читать.

Отсюда практический вывод: считать, что «нет ячеек» автоматически означает «нет работы», неверно. Внешние проходы и печать могут выполняться, даже когда читать нечего. А доступ к первой ячейке [0, 0] возможен только при r > 0 и c > 0 одновременно. Если хотя бы одна из размерностей нулевая, первой ячейки нет.

Нерегулярные строки

Иногда данные не укладываются в прямоугольную таблицу. Например, в первый день было четыре сеанса, во второй — два, в третий — пять. Прямоугольная таблица 3 на 4 здесь не подходит: в ней должно быть одинаковое число столбцов во всех строках.

В таком случае можно хранить не таблицу целиком, а последовательность строк разной длины — по одной строке на день. У каждой строки своя длина, и обход идёт по каждой строке отдельно, до её собственного конца.

В русском псевдокоде это выглядит так:

ДЛЯ каждой строки в наборе строк:
    сумма = 0
    ДЛЯ каждой ячейки в этой строке:
        сумма += ячейка
    КОНЕЦ ДЛЯ
    напечатать сумму
КОНЕЦ ДЛЯ

Внутренний предел — длина текущей строки, а не какая-то общая. Сумма всех ячеек — сумма длин всех строк. Никакого единого прямоугольника здесь нет, и это нормально: иногда данные удобнее хранить именно так. Когда прямоугольник подходит — он удобен, когда нет — есть другие формы.

Небольшая практика

Попробуйте ответить на такой вопрос. В таблице 3 на 4 мы хотим узнать, в каком дне продано больше всего билетов. Как это сделать, не заводя отдельную структуру для дневных сумм?

Ответ на практический вопрос: нужно идти по строкам, для каждой считать сумму, сравнивать её с текущим максимумом и запоминать не только значение, но и номер дня, где оно встретилось. Если новая сумма строго больше текущего максимума, обновляем и значение, и номер. Если равна — оставляем как было: тогда при нескольких днях с одинаковым максимумом мы сохраняем первый из них. Вспомогательной памяти при этом нужно O(1): накопитель для текущей строки, текущий максимум и номер лучшего дня. Для наших данных лучший день — с индексом 1, то есть второй: его сумма равна 7, тогда как у первого и третьего по 6. Хранить все дневные суммы тоже можно, но не обязательно, и выбор между O(1) и O(r) памяти не меняет обхода: время остаётся O(r * c) в обоих вариантах.