7. Предпросчет. Префикс суммы. Префикс суммы в двумерном массиве.

1. Предпросчет

Очень важный совет будущим программистам: сначала изучите и проанализируйте условие задачи, продумайте, какие вам понадобятся объекты (или классы) для хранения и обработки данных, в каком виде должны быть данные, чтобы ваша программа быстрее обрабатывала запросы пользователей, пропишите основные модули программы и для каждого модуля определитесь с входными и выходными данными и задачами (задачей), которую он будет решать, поставьте ограничения по времени обработки данных, то есть по сложности реализуемых алгоритмов, оцените необходимые ресурсы, в общем, порисуйте схемы и картинки на листах бумаги или в графическом редакторе и только потом приступайте к написанию кода.

Сегодня мы поговорим о том, что иногда полезно предварительно обработать исходные данные, чтобы потом гораздо быстрее получать ответы на запросы. Насколько это важно, можно понять на примере интернета. Если бы поисковая система (например, Google) начинала искать сайты по строке запроса пользователя в момент запуска запроса, ответа мы бы ждали в лучшем случае несколько часов (скорее даже дней). Для того, чтобы за считанные доли секунды получать отклики на запросы клиентов, поисковым системам приходится выполнять массу работы, которая скрыта от обычных пользователей.

На самом деле с предпросчетом в алгоритмах мы свами уже сталкивались. Та же предварительная сортировка данных, которая позволяет за О (log n) вместо O (n) искать элементы в массиве – это вариант предпросчета, то есть мы выполнили заранее какие-то, не всегда очевидные, вещи для того, чтобы потом быстрее отвечать на основные массовые запросы к программе. Причем идеи предпросчета могут быть совсем не очевидными.

Рассмотрим несколько примеров:

2. Проверка чеков (префикс суммы)

Мы создаем экономическую стратегию в новом жанре. Игрок выступает в роли управляющего магазином и по общим итогам денежной выручки за день понимает, что один из кассиров «не чист на руку», проще говоря подворовывает. На одном из кассовых аппаратов по чекам обнаружился серьезный обман покупателей: чеки выбивались на большую сумму, чем стоили товары, и с покупателей брались лишние деньги, которые к тому же в итоге уходили мимо кассы. Проблема в том, что за этим кассовым аппаратом работали разные кассиры. Радует то, что игрок точно знает с какого и по какой номер чека работал каждый кассир. Итак, для того, чтобы вывести жулика на чистую воду, игроку надо уметь быстро считать, на какую сумму выбиты чеки с такого-то по такой-то номер.

Входные данные: список чеков, в котором для каждого указана денежная сумма товаров в чеке в рублях без копеек. Далее вводится число k – количество запросов, а затем в каждом запросе start и end – номера начального и конечного чеков, для которых надо вывести ответ. Номер чека совпадает с порядковым номером числа в массиве (чеки нумеруются с 1).

Выходные данные: k чисел – сумма товаров в чеках от start до end (включая и тот и другой). Данные корректны, то есть start и end не выходят за пределы массива.

Создадим новую структуру данных (массив), который назовем префикс суммы. Он позволит нам очень быстро отвечать на запросы – за О (1) для каждого запроса.

Фрагмент кода программы:

private static int[] _checks = new int[] {10,11,15,7,21,11,3,7,9,14,15,6,14,10,5};
private static int[] _prefix = new int[_checks.Length];

public static void Main(string[] args)
{
    PrefixSum();
    Inquiries();
}

private static void PrefixSum()
{
    _prefix[0] = _checks[0];
    for (int i = 1; i < _prefix.Length; i++)
    {
        _prefix[i] = _prefix[i - 1] + _checks[i];
    }

    for (int i = 0; i < _checks.Length; i++)
    {
        Console.Write(_checks[i] + " ");
    }
    Console.WriteLine();

    for (int i = 0; i < _prefix.Length; i++)
    {
        Console.Write(_prefix[i] + " ");
    }

    Console.WriteLine();
}

private static void Inquiries()
{
    Console.Write("Введите количество запросов k=");
    int k = Convert.ToInt32(Console.ReadLine());
    for (int i = 0; i < k; i++)
    {
        Console.WriteLine("Запрос №" + ( i + 1));
        Console.Write("Введите номер первого чека:");
        int start = Convert.ToInt32(Console.ReadLine()) - 1;
        Console.Write("Введите номер последнего чека:");
        int end = Convert.ToInt32(Console.ReadLine()) - 1;
        if (start == 0)
        {
            Console.WriteLine("Сумма = " + _prefix[end]);
        }
        else
        {
            Console.WriteLine("Сумма = " + (_prefix[end] - _prefix[start - 1]));
        }
    }
}

Вопрос: Что изменить в алгоритме, если надо учесть, что числа в массиве могут быть достаточно большими (например, суммы до деноминации)?

3. Префикс суммы на двумерном массиве

А если нам надо быстро находить сумму чисел в прямоугольной области двумерного массива?

Входные данные: двумерный массив чисел. Далее вводится число k – количество запросов, а затем в каждом запросе x1, y1, x2, y2 – координаты прямоугольной области (включая x1, y1, x2, y2), для которой надо вывести сумму.

Данные корректны, то есть координаты не выходят за пределы массива.

Выходные данные: k чисел – сумма товаров в чеках от start до end (включая и тот и другой).

Вопрос: Оцените сложность той части алгоритма, которая выводит ответ на один запрос.

Фрагмент кода программы:

private static int[,] _array =
{
    {0, 0,  0,  0}, 
    {0, 1,  2,  3}, 
    {0, 4,  5,  6}, 
    {0, 7,  8,  9}, 
    {0, 10, 11, 12}
};
private static int[,] _prefix = new int[_array.GetLength(0), _array.GetLength(1)];

public static void Main(string[] args)
{
    Print(_array);
    PrefixSum();
    Inquiries();
}

private static void Print(int[,] array)
{
    for (int i = 0; i < array.GetLength(0); i++)
    {
        for (int j = 0; j < array.GetLength(1); j++)
        {
            Console.Write(quot;{array[i, j]} \t");
        }

        Console.WriteLine();
    }

    Console.WriteLine();
}

private static void PrefixSum()
{
    _prefix[0, 0] = _array[0, 0];

    for (int i = 1; i < _prefix.GetLength(0); i++)
    {
        _prefix[i, 0] = _prefix[i - 1, 0] + _array[i, 0];
    }

    for (int i = 1; i < _prefix.GetLength(1); i++)
    {
        _prefix[0, i] = _prefix[0, i - 1] + _array[0, i];
    }

    for (int i = 1; i < _prefix.GetLength(0); i++)
    {
        for (int j = 1; j < _prefix.GetLength(1); j++)
        {
            _prefix[i, j] =_prefix[i - 1, j] + _prefix[i, j - 1] - _prefix[i - 1, j - 1] + _array[i, j];
        }
    }

    Print(_prefix);
}

private static void Inquiries()
{
    Console.Write("Введите количество запросов k=");
    int k = Convert.ToInt32(Console.ReadLine());
    for (int i = 0; i < k; i++)
    {
        Console.WriteLine("Запрос №" + i);
        Console.Write("Введите X1:");
        int x1 = Convert.ToInt32(Console.ReadLine());
        Console.Write("Введите Y1:");
        int y1 = Convert.ToInt32(Console.ReadLine());
        Console.Write("Введите X2:");
        int x2 = Convert.ToInt32(Console.ReadLine());
        Console.Write("Введите Y2:");
        int y2 = Convert.ToInt32(Console.ReadLine());

        int summa=_prefix[x2,y2]-_prefix[x1-1,y2]-_prefix[x2,y1-1]+_prefix[x1-1,y1-1];

        Console.WriteLine("Сумма = " + summa);
    }
}

Итоги занятия