В этой статье мы сделаем небольшой шаг к пониманию алгоритмов, которыми нужно пользоваться, чтобы взять два балла за 27 номер на ЕГЭ по информатике. Возьмем некоторую задачу, попробуем написать программное решение "в лоб", а затем попробуем немного подумать и оптимизировать алгоритм. Также ценим скорость работы обеих программ.
Постановка задачи
По большому количеству данных о колебании некоторой величины с течением времени построили график:
Величина изменяется со временем, причем ее значение "прыгает". Можно отследить общую тенденцию изменения величины со временем (оно носит синусоидальный характер), но решительно невозможно более точно сказать, чему она равна в конкретный момент времени.
Хотелось бы уменьшить количество данных, чтобы построенный график не был таким "лохматым". Можно, к примеру, строить график по каждому сотому значению из наших данных. Но такой подход рискует отобразить неточную картину (см. рисунок)
На рисунке "лохматый" синус попытались аппроксимировать с помощью малого количества значений - при t = 0, 20, 40, 60, 80, 100. Полученный красный график мало говорит об истинном поведении исходной функции.
Поэтому более разумно построить приближенный график по некоторым усредненным значениям. Например, с помощью метода скользящего среднего.
Метод скользящего среднего
Метод заключается в построении графика функции, для которой значение в каждой точке будет равно среднему арифметическому k значений исходной функции. Параметр k называется "окном усреднения".
Окно-диапазон из k значений "скользит" по списку исходных значений, высчитываются остальные средние величины (на рисунке точками обозначены не все, а каждое сотое среднее значение):
Пример
Пусть исходные данные таковы: A = [1, 5, 3, 7, 8, 3, 4]. Выберем окно усреднения k=3. Тогда нужно перебрать все идущие подряд тройки из списка данных и посчитать по ним среднее арифметическое значение:
- [1, 5, 3] - 1 + 5 + 3 = 9, среднее 9/3 = 3;
- [5, 3, 7] - 5 + 3 + 7 = 15, среднее 15/3 = 5;
- [3, 7, 8] - 3 + 7 + 8 = 18, среднее 18/3 = 6;
- [7, 8, 3] - 7 + 8 + 3 = 18, среднее 18/3 = 6;
- [8, 3, 4] - 8 + 3 + 4 = 15, среднее 15/3 = 5.
Список усредненных данных: [3, 5, 6, 6, 5]. Заметим, что в исходном списке А было 7 значений, а в усредненном их 5. В общем случае при количестве исходных значений len(A) = n количество элементов результирующего списка составит n - k + 1, где k - величина окна усреднения.
Посмотрим, как данные из примера будут выглядеть на графике:
Наивный алгоритм для метода скользящего среднего
Простой в реализации неоптимальный алгоритм, первым приходящим в голову, называется "наивным". Решение незнакомых задач рекомендуют начинать с его построения, и заниматься оптимизацией только при необходимости (на экзамене нужно решить задачу и получить правильный ответ, а не решить красиво, чтобы экзаменаторы обзавидовались вашему непревзойденному стилю программирования).
Самым простым кажется подобное решение:
- создаем пустой список, в который позже запишутся результаты осреднения.
- пробегаем по индексам элементов, которые будут началом "окна".
- перебираем элементы, находящиеся внутри окна. Суммируем их, делим сумму на k и добавляем найденное значение в результирующий список.
Тестирование данного алгоритма на большом количестве данных показывает его время работы при разном количестве исходных данных (каждый раз берем величину окна сглаживания k = 200):
- t = 0.053 c при n = 6000
- t = 0.098 c при n = 12000
- t = 0.201 c при n = 24000
- t = 0.393 c при n = 48000
Эти вычисления вы можете повторить сами, файлы с исходными данными и с моей программой найдете по ссылке.
Заметим, что время выполнения программы увеличивается в два раза с увеличением количества данных в два раза (то есть время линейно зависит от количества данных).
В КЕГЭ файлы с исходными данными вполне могут содержать несколько миллионов строк. Нехитрые подсчеты показывают, что при n = 1000000 время выполнения программы составит 8,83 с. Вы скажете, что это немного. Но подобные задачи предполагают увеличение значения, соответствующего окну сглаживания. В задаче 7275 с kompege.ru такое значение составляет 12000 - в 60 раз больше нашего k = 200. Тогда и время выполнения программы увеличится в 60 раз и будет составлять не 8,83 с, а 8,83 мин. А это уже ощутимо!
Оптимизация алгоритма метода скользящего среднего
Решим тестовую задачу еще раз ручками. Исходные данные A = [1, 5, 3, 7, 8, 3, 4], окно усреднения k=3 (листайте галерею, читайте комментарии под картинками).
Еще раз посмотрим на картинку с рекуррентной формулой для вычисления суммы:
Здесь переменной a обозначен список с исходными данными, а переменной summ - список сумм, по которым легко вычислить среднее значение для каждого окна, разделив соответствующую сумму на k.
Нужно обозначить, что переменная i принимает значения от 1 до n - k - тогда при i = n-k формула примет вид
summ_(n-k) = summ_(n-k-1) + a_(n-1) - a_(n-k-1).
Здесь после символа _ написан нижний индекс. При i = n-k мы прибавляем к сумме элемент a_(n-1) - последний элемент в списке длиной n при нумерации элементов с нуля.
Опишем алгоритм решения данной задачи:
- Вычисляем сумму первых k элементов, в итоговый список добавляем их среднее арифметическое - частное от деления этой суммы на k.
- В цикле пробегаем по i от 1 до n - k. Каждый раз от суммы отнимаем элемент a_(i-1) и прибавляем a_(i_k-1). Делим обновленную сумму на k и добавляем полученное среднее в итоговый список.
Пример кода, соответствующего данному алгоритму:
Теперь проверим время выполнения этого кода на больших данных:
- t = 0.004 c при n = 6000
- t = 0.006 c при n = 12000
- t = 0.013 c при n = 24000
- t = 0.024 c при n = 48000
Скорость тоже линейно зависит от n, но растет намного медленнее, чем в реализации наивного алгоритма. При такой скорости программа решит задачу с n=1000000 исходных данных при k = 200 за 0,5 с. А если увеличим еще и k в 60 раз, то за 0,5 мин. Сократили время выполнения программы в 17 раз - очень даже неплохо!
Программу можно найти здесь, рядом с реализацией неоптимального алгоритма и исходными данными.
Подытожим
- Решать задание 27 из КЕГЭ можно наивным алгоритмом, но с высокой долей вероятности ответ удастся получить только для файла А c небольшим количеством исходных данных. Время выполнения такой программы для файла B может превысить время, отведенное на экзамен.
- Для получения ответа для файла B придется оптимизировать программу с помощью математического вывода рекуррентного соотношения.
На чем тренироваться?
На кошках номерах с kompege.ru:
6760, 6638, 6320, 6097