[МУЗЫКА] [МУЗЫКА] Посмотрим пример задачи, которая позволит нам научиться как-то обрабатывать достаточно эффективно элементы списка. Например, мы хотим считать список чисел. Напомню, что это делается вот такой хитрой конструкцией: list (map (int, input(). split() )). Со временем запомните. Напомню, input — считали строку, split — нарезали ее на слова, map int — к этому списку применили функцию int, то есть каждое слово отдельно превратили в число, и list, чтобы из этого итерируемого объекта получился список. Всё, теперь у нас есть список чисел, и мы хотим поудалять из него все нечетные числа. Давайте, чтобы это нельзя было сделать, просто выводя числа по одному, еще и развернуть их потом задом наперед, тогда точно нам придется всё хранить или выдумывать какую-то рекурсию, чего мы сейчас делать не хотим. Удаляем, сначала все нечетные числа, потом разворачиваем. Какая первая идея нам может в голову прийти? Перебираем все индексы нашего списка. Для этого можно воспользоваться range от len, от нашего списка, то есть мы перебираем все числа от 0, от нулевого начального элемента нашего списка, до len, до конца, до последнего элемента. Считаем их индексы. Если у нас число, стоящее на этом месте, a [i] нечетное, то есть остаток от деления на 2 не равен 0, то что мы будем делать? Давайте его сделаем pop (i). Напомню, что метод pop удаляет элемент с этой позиции. Казалось бы, все логично, замечательно, мы договорились развернуть список, но давайте не будем этого делать. Это специально, чтобы не дать возможности, то есть когда мы в задачах просим вас развернуть все элементы, после того как вы что-то сделали с ними, это чтобы вы не читерили и не выводили их по одному. Я не обманываю, не пытаюсь обмануть тестирующую систему, поэтому не будем такое искусственное ограничение придумывать и просто выведем весь список. Давайте посмотрим. Итак, давайте сначала только четные числа проверим, что у нас ничего не портится, список выводится. Если мы добавим звездочку, то он еще и красиво будет выводиться. По крайней мере, если там есть только четные числа, у нас ничего не сломалось. Теперь посмотрим, сломается ли, если у нас будут нечетные числа, не будет ли оно правильно работать. Оно сломалась совсем, оно говорит: list index out of range. Вот она ошибка, совершенно непонятно, что это такое. Казалось бы, только что все работало. Как ловить такого рода ошибки? Начинаем веселый, занимательный процесс отладки по шагам. Ставим breakpoint в начале интересной части программы, запускаем отладку, вводим какие-нибудь данные. У нас было 1, 2, 3, так и оставим, и будем выполнять по шагам. Здесь у нас функции нет, поэтому можно пользоваться любыми step, например, step out, чтобы точно никуда не попасть. Итак, i = 0. Вот мы сейчас видим значение этой переменной, и список, какой у нас сейчас есть. Так, в if мы заходим, число нечетное, и удаляем этот элемент. Отлично, элемент удалился, вроде бы все хорошо. Но на следующем шаге цикла i уже = 1, то есть на двойку, которая сейчас стоит в нулевом месте, мы вообще уже даже не посмотрим. Давайте поймем все-таки, почему она ломается, то есть то, что это неправильно, уже понятно. Почему она совсем ломается, это мы сейчас узнаем. Итак, здесь что у нас оказалось? i = 1, теперь это показывает на тройку, и тройка тоже удаляется из списка, все хорошо. Но теперь i становится = 2, то есть то значение, та длина списка, которую мы посчитали в for один раз, она посчиталась в самом начале, она была равна трем, запомнилась, и теперь, когда мы меняем список, эта длина не пересчитывается заново. Сейчас оно, естественно, сломается, потому что мы посмотрим на какой-то элемент, вот мы уже провалились в обработку ошибки. В общем, ничего интересного нас здесь не ждет, поэтому мы можем вернуться обратно и подумать, как это можно исправить. for не меняет то, что посчитал однажды. Как сделать, чтобы менял? Изменить это на while. Давайте попробуем переделать, for нам больше не пригодится, начинаем мы считать с нуля теперь, как мы это делали раньше. Пока очередное значение i меньше, чем длина нашего списка. И теперь, когда мы в while это делаем, у нас каждый раз будет сравниваться значение с актуальной длиной списка уже, и переменную i нужно увеличивать. Давайте вспомним, у нас была какая еще проблема, кроме того, что все ломалось? У нас была проблема, что мы пропускали некоторые элементы. Почему? Потому, что мы элемент, стоящий на i-том месте, удалили и перешли к i плюс первому. А у нас же элементы передвинулись, и мы на следующий за ним элемент вообще никогда не посмотрим. Если у нас будет два нечетных числа подряд, то все будет работать плохо. Как мы будем избавляться от этой проблемы? В случае, если число нечетное, будем его удалять, а в случае, если четное, будем переходить к следующему. Давайте теперь убедимся, что оно заработало. Сразу я возьму тест, где у нас есть несколько нечетных чисел подряд, чтобы проверить, что от этой проблемы мы тоже избавились. Теперь оно работает, то есть нам пришлось пойти на вот такие ухищрения из-за того что цикл for, однажды посчитав, куда ему идти, сгенерировав этот объект, уже его не пересчитывает, если объект изменяется. Об этом нужно помнить и таких ситуаций избегать. Теперь подумаем об эффективности того, что мы написали. Здесь у нас много раз вызывается функция pop. Напомню, функция pop работает за длину списка, то есть сколько элементов в списке есть, столько операций нам нужно совершить, потому что на i-тое место нужно по одному передвигать эти элементы. Это очень медленно. Часто, если вам нужно что-то поудалять из списка, то есть у вас есть какая-то задача оставить часть списка, применяется такой метод: мы создаем новый список пустой, давайте я все удалю ненужное нам. Напишем заново, так намного проще. Мы создаем пустой список и кладем туда только нужный элемент. Всё, вот такой подход. Что мы сделаем? Мы можем пройтись прямо вот таким образом, то есть now_in a. Поочередно на место now будут подставляться значения из списка a. Если now, то, что сейчас, это уже не index, это уже конкретный элемент списка текущий. Если он четный, тогда будем добавлять его в новый список, у нас он называется b. Вот и всё. Проверяем. Значит, отлично. У нас напечатались только четные числа. Хотя памяти при таком подходе тратится больше, то есть нам в худшем случае понадобится вдвое больше памяти, мы будем хранить, если все числа были четные, мы будем хранить их в списке a и постепенно накопим их же в списке b. Но время мы значительно экономим, потому что функция append — добавление в конец, работает за фактически одну операцию. Если в худшем случае в предыдущем решении мы могли потратить n квадрат операций, где n — это длина списка, то здесь будет всего n операций, что намного лучше. Поэтому в большинстве задач, где вам нужно отфильтровать какие-то элементы списка, оставить только нужные, удалить ненужные, подход — создать пустой список и постепенно добавлять в него нужные элементы — часто оказывается эффективным, как по времени, а памяти, будем надеяться, что хватит. Поэтому этим подходом нужно пользоваться и в некоторых задачах им явно нужно воспользоваться. Мы старались сделать так, чтобы если вы пытались удалять элементы, это не пройдет по времени, вы получите time limit. Где-то, может быть, это и пройдет, но, тем не менее, старайтесь пользоваться подходящим методом, памяти у вас ограничение большое, а вот времени — маленькое. Этот прием на практике тоже часто применяется, потому что он хорош. Когда вы будете разрабатывать уже какие-то настоящие программы, не забывайте о нем и пользуйтесь. На следующем занятии мы изучим еще один метод списков. Это сортировка. Работать с отсортированными данными во многих задачах намного удобнее, и вам это наверняка пригодится. Пока что сортировкой пользоваться нельзя, поэтому даже если вы вдруг ее знаете, постарайтесь решить задачи, не используя ее, хотя это может быть и длиннее, и сложнее, но зато позволит вам хорошо разобраться со списками. [МУЗЫКА] [МУЗЫКА]
