Списки в PYTHON

Лекция №2. СПИСКИ в python СОДЕРЖАНИЕ 2.1 Списки (одномерные массивы) 2.2 Алгоритмы обработки массивов 2.3 Сортировка 2.1. Списки (одномерные массивы) Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер. Для работы с массивами нужно, в первую очередь, научиться: • выделять память нужного размера под массив; • записывать данные в нужную ячейку; • читать данные из ячейки массива. В языке Python нет такой структуры как «массив». Вместо этого для хранения группы однотипных объектов используют списки. Список в Python – это набор элементов, каждый из которых имеет свой номер (индекс). Нумерация всегда начинается с нуля, второй по счёту элемент имеет номер 1 и т.д. В отличие от обычных массивов в большинстве языков программирования список – это динамическая структура, его размер можно изменять во время выполнения программы (удалять и добавлять элементы), при этом все операции по управлению памятью берёт на себя транслятор. Список можно создать перечислением элементов через запятую в квадратных скобках, например, так: A = [1, 3, 4, 23, 5] Списки можно «складывать» с помощью знака «+», например, показанный выше список можно было построить так: A = [1, 3] + [4, 23] + [5] Сложение одинаковых списков заменяется умножением «*». Вот так создаётся список из 10 элементов, заполненный нулями: A = [0]*10 В более сложных случаях используют генераторы списков – выражения, напоминающие цикл, с помощью которых заполняются элементы вновь созданного списка: A = [ i for i in range(10) ] Как вы знаете, цикл for i in range(10) перебирает все значения i от 0 до 9. Выражение перед словом for (в данном случае – i) – это то, что записывается в очередной элемент списка для каждого i. В приведённом примере список заполняется значениями, которые последовательно принимает переменная i, то есть получим такой список: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] То же самое можно получить, если использовать функцию list для того, чтобы создать список из данных, которые получаются с помощью функции range: A = list ( range(10) ) Для заполнения списка квадратами этих чисел можно использовать такой генератор: A =[ i*i for i in range(10)] В конце записи генератора можно добавить условие отбора. В этом случае в список включаются лишь те из элементов, перебираемых в цикле, которые удовлетворяют этому условию. Например следующий генератор составляет список из всех простых чисел в диапазоне от 0 до 99: Часто в тестовых и учебных программах массив заполняют случайными числами. Это тоже можно сделать с помощью генератора: from random import randint A = [ randint(20,100) for x in range(10)] Здесь создается массив из 10 элементов и заполняется случайными числами из отрезка [20,100]. Для этого используется функция randint, которая импортируется из модуля random. Длина списка (количество элементов в нём) определяется с помощью функции len: N = len(A) Ввод и вывод массива Далее во всех примерах мы будем считать, что в программе создан список A, состоящий из N элементов (целых чисел). В этом списке хранится массив данных, поэтому под выражением «массив» мы будем подразумевать «однотипные данные, хранящиеся в виде списка». Переменная i будет обозначать индекс элемента списка. Если никакие подсказки нам не нужны, создать массив из N элементов и ввести их значения можно с помощью генератора списка: A = [ int(input()) for i in range(N) ] Здесь на каждом шаге цикла строка, введённая пользователем, преобразуется в целое число с помощью функции int, и это число добавляется к массиву. Возможен еще один вариант ввода, когда весь массив вводится в одной строке. В этом случае строку, полученную от функции input, нужно «расщепить» на части с помощью метода split: data = input() s = data.split() или сразу s = input().split() Например, если ввести строку "1 2 3 4 5", то после «расщепления» мы получим список ['1', '2', '3', '4', '5'] Это список символьных строк. Теперь поговорим о выводе массива на экран. Самый простой способ – вывести список как один объект: print ( A ) В этом случае весь список берётся в квадратные скобки, и элементы разделяются запятыми. Вывести массива на экран можно и поэлементно for i in range(N): print ( A[i], end = " " ) После вывода каждого элемента ставится пробел, иначе все значения сольются в одну строку (пробелы вставляются с помощью end = " "). Удобно записывать такой цикл несколько иначе: for x in A: print ( x, end = " " ) Здесь не используется переменная‐индекс i, а просто перебираются все элементы списка: на каждом шаге в переменную x заносится значение очередного элемента массива (в порядке возрастания индексов). Более быстрый способ – построить одну символьную строку, содержащую все элементы массива, и сразу вывести её на экран: print ( " ".join( [ str(x) for x in A] ) ) Функция join (англ. join – объединить) объединяет символьные строки, используя указанный перед точкой разделитель, в данном случае – пробел. Запись str(x) означает «символьная запись x». Таким образом, элементы массива записываются через пробел в одну символьную строку, и эта строка затем выводится на экран с помощью функции print. Перебор элементов Перебор элементов массива состоит в том, что мы в цикле просматриваем все элементы списка и, если нужно, выполняем с каждым из них некоторую операцию. Переменная цикла изменяется от 0 до N-1, где N – количество элементов массива, то есть в диапазоне range(N): for i in range(N): A[i] += 1 в этом примере все элементы массива A увеличиваются на 1. Если массив изменять не нужно, для перебора его элементов удобнее всего использовать такой цикл: for x in A: ... Здесь вместо многоточия можно добавлять операторы, работающие с копией элемент, записанной в переменную x. Обратите внимание, что изменение переменной x в теле цикла не приведёт к изменению соответствующего элемента массива A. Заметим, что для первой задачи (увеличить все элементы массива на 1) есть красивое решение в стиле Python, использующее генератор списка, который построит новый массив: A = [ x+1 for x in A ] Здесь в цикле перебираются все элементы исходного массива, и в новый список они попадают после увеличения на 1. Во многих задачах требуется найти в массиве все элементы, удовлетворяющие заданному условию, и как‐то их обработать. Простейшая из таких задач – подсчёт нужных элементов. Для решения этой задачи нужно ввести переменную‐счётчик, начальное значение которой равно нулю. Далее в цикле просматриваем все элементы массива. Если для очередного элемента выполняется заданное условие, то увеличиваем счётчик на 1. На псевдокоде этот алгоритм выглядит так: Предположим, что в массиве A записаны данные о росте игроков баскетбольной команды. Найдем количество игроков, рост которых больше 180 см, но меньше 190 см. В следующей программе используется переменная‐счётчик count: Теперь усложним задачу: требуется найти средний рост этих игроков. Для этого нужно дополнительно в отдельной переменной складывать все нужные значения, а после завершения цикла разделить эту сумму на количество. Начальное значение переменной Sum, в которой накапливается сумма, тоже должно быть равно нулю. Суммирование элементов массива – это очень распространённая операция, поэтому для суммирования элементов списка в Python существует встроенная функция sum: print ( sum(A) ) С её помощью можно решить предыдущую задачу более элегантно, в стиле языка Python: сначала выделить в дополнительный список все нужные элементы, а затем поделить их сумму на количество (длину списка). Для построения нового списка будем использовать генератор: B = [ x for x in A if 180 < x and x < 190 ] Условие отбора заключено в рамку. Таким образом, мы отбираем в список B те элементы из списка A, которые удовлетворяют этому условию. Теперь для вывода среднего роста выбранных игроков остается разделить сумму элементов нового списка на их количество: print ( sum(B) / len(B) ) Контрольные вопросы (для ответа на тест) 1. Что такое массив? Зачем нужны массивы? 2. Как вы думаете, почему в языке Python нет массивов, а вместо них используются списки? 3. Какие способы создания списков вы знаете? 4. Что такое генераторы списков? 5. Зачем нужны генераторы списков с условием? 6. Как построить список, состоящий из 15 единиц, с помощью генератора списка? 7. Как обращаться к отдельному элементу списка? 9. Как вывести список на экран? Приведите разные варианты решения этой задачи. 10. Как заполнить список случайными числами в диапазоне от 100 до 200? 11. С помощью каких функций можно найти сумму и количество элементов списка? 12. Сравните разные способы решения задачи о среднем росте игроков. 2.2 Алгоритмы обработки массивов Поиск в массиве Требуется найти в массиве элемент, равный значению переменной X, или сообщить, что его там нет. Алгоритм решения сводится к просмотру всех элементов массива с первого до последнего. Как только найден элемент, равный X, нужно выйти из цикла и вывести результат. Напрашивается такой алгоритм: Он хорошо работает, если нужный элемент в массиве есть, однако приведет к ошибке, если такого элемента нет – получится зацикливание и выход за границы массива. Поэтому в условие нужно добавить еще одно ограничение: i< N. Если после окончания цикла это условие нарушено, значит поиск был неудачным – элемента нет: Отметим одну тонкость. В сложном условии i < N и A[i]!= X первой должно проверяться именно отношение i < N. Если первая часть условия, соединенного с помощью операции «И», ложно, то вторая часть, как правило, не вычисляется – уже понятно, что всё условие ложно. Дело в том, что если i >= N, проверка условия A[i] != X приводит к выходу за границы массива, и программа завершается аварийно. Возможен ещё один поход к решению этой задачи: используя цикл с переменной, перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение. Для выхода из цикла используется оператор break, номер найденного элемента сохраняется в переменной nX. Если её значение осталось равным –1 (не изменилось в ходе выполнения цикла), то в массиве нет элемента, равного X. Последний пример можно упростить, используя особые возможности цикла for в языке Python: Итак, здесь мы выводим результат сразу, как только нашли нужный элемент, а не после цикла. Слово else после цикла for начинает блок, который выполняется при нормальном завершении цикла (без применения break). Таким образом, сообщение «Не нашли!» будет выведено только тогда, когда условный оператор в теле цикла ни разу не сработал. Возможен другой способ решения этой задачи, использующий метод (функцию) index для типа данных list, которая возвращает номер первого найденного элемента, равного X: nX = A.index(X) Тут проблема только в том, что эта строчка вызовет ошибку при выполнении программы, если нужного элемента в массиве нет. Поэтому нужно сначала проверить, есть ли он там (с помощью оператора in), а потом использовать метод index: Запись «if X in A» означает «если значение X найдено в списке A». Максимальный элемент Найдем в массиве максимальный элемент. Для его хранения выделим целочисленную переменную M. Будем в цикле просматривать все элементы массива один за другим. Если очередной элемент массива больше, чем максимальный из предыдущих (находящийся в переменной M), запомним новое значение максимального элемента в M. Остается решить, каково должно быть начальное значение M. Во‐первых, можно записать туда значение, заведомо меньшее, чем любой из элементов массива. Например, если в массиве записаны натуральные числа, можно записать в M ноль или отрицательное число. Если содержимое массива неизвестно, можно сразу записать в M значение A[0], а цикл перебора начать со второго счёту элемента, то есть, с A[1]: Вот еще один вариант: Он отличается тем, что мы не используем переменную‐индекс, но зато дважды просматриваем элемент A[0] (второй раз – в цикле, где выполняется перебор всех элементов). Поскольку операции поиска максимального и минимального элементов нужны очень часто, в Python есть соответствующие встроенные функции max и min: Ma = max ( A ) Mi = min ( A ) Теперь предположим, что нужно найти не только значение, но и номер максимального элемента. Казалось бы, нужно ввести еще одну переменную nMax для хранения номера, сначала записать в нее 0 (считаем элемент A[0] максимальным) и затем, когда нашли новый максимальный элемент, запоминать его номер в переменной nMax: Однако это не самый лучший вариант. Дело в том, что по номеру элемента можно всегда определить его значение. Поэтому достаточно хранить только номер максимального элемента. Если этот номер равен nMax, то значение максимального элемента равно A[nMax]: Для решения этой задачи можно использовать встроенные функции Python: сначала найти максимальный элемент, а потом его индекс с помощью функции index: В этом случае фактически придётся выполнить два прохода по массиву. Однако такой вариант работает во много раз быстрее, чем «рукописный» цикл с одним проходом, потому что встроенные функции написаны на языке C++ и подключаются в виде готового машинного кода, а не выполняются относительно медленным интерпретатором Python. Реверс массива Реверс массива – это перестановка его элементов в обратном порядке: первый элемент становится последним, а последний – первым. Из рисунка следует, что 0‐й элемент меняется местами с (N-1)‐м, второй – с (N-2)‐м и т.д. Сумма индексов элементов, участвующих в обмене, для всех пар равна N-1, поэтому элемент с номером i должен меняться местами с (N-1-i)‐м элементом. Кажется, что можно написать такой цикл: for i in range(N): поменять местами A[i] и A[N-1-i] однако это неверно. Посмотрим, что получится для массива из четырёх элементов: Как видите, массив вернулся в исходное состояние: реверс выполнен дважды. Поэтому нужно остановить цикл на середине массива: Для обмена можно использовать вспомогательную переменную c: или возможности Python: Эта операция может быть выполнена и с помощью стандартного метода reverse (в переводе с англ. – реверс, обратный) типа list: A.reverse() Сдвиг элементов массива При удалении и вставке элементов необходимо выполнять сдвиг части или всех элементов массива в ту или другую сторону. Массив часто рисуют в виде таблицы, где первый элемент расположен слева. Поэтому сдвиг влево – это перемещение всех элементов на одну ячейку, при котором A[1] переходит на место A[0], A[2] – на место A[1] и т.д. Последний элемент остается на своем месте, поскольку новое значение для него взять неоткуда – массив кончился. Алгоритм выглядит так: Обратите внимание, что цикл заканчивается при i=N-2 (а не N-1), чтобы не было выхода за границы массива, то есть обращения к несуществующему элементу A[N]. При таком сдвиге первый элемент пропадает, а последний – дублируется. Можно старое значение первого элемента записать на место последнего. Такой сдвиг называется циклическим. Предварительно (до начала цикла) первый элемент нужно запомнить во вспомогательной переменной, а после завершения цикла записать его в последнюю ячейку массива: Ещё проще выполнить такой сдвиг, используя встроенные возможности списков Python: Здесь использован так называемый срез – выделение части массива. Срез A[1:N] означает «все элементы с A[1] до A[N-1]», то есть не включая элемент с последним индексом. Таким образом, этот срез «складывается» со списком, состоящим из одного элемента A[0], в результате получается новый массив, составленный из «списков‐слагаемых». Чтобы такая система (исключение последнего элемента) была более понятной, можно представить, что срез массива выполняется по разрезам – границам между элементами: Таким образом, срез A[0:2] выбирает все элементы между разрезами 0 и 2, то есть элементы A[0] и A[1]. Если срез заканчивается на последнем элементе массива, второй индекс можно не указывать: A = A[1:] + [A[0]] Аналогично, A[:5] обозначает «первые 5 элементов массива» (начальный индекс не указан). Если не указать ни начальный, ни конечный индекс, мы получим копию массива: Acopy = A[:] Если использованы отрицательные индексы, к ним добавляется длина массива. Например, срез A[:-1] выбирает все элементы, кроме последнего (он равносилен A[:N-1]). А вот так можно выделить из массива три последних элемента: B = A[-3:] Заметим, что с помощью среза можно, например, выполнить реверс массива: A = A[::-1] Рассмотрим подробно правую часть оператора присваивания. Число «–1» обозначает шаг выборки значений, то есть, элементы выбираются в обратном порядке. Слева от первого и второго знаков двоеточия записывают начальное и конечное значения индексов; если они не указаны, считается, что рассматривается весь массив. Отбор нужных элементов Требуется отобрать все элементы массива A, удовлетворяющие некоторому условию, в новый массив B. Поскольку списки в Python могут расширяться во время работы программы, можно использовать такой алгоритм: сначала создаём пустой список, затем перебираем все элементы исходного массива и, если очередной элемент нам нужен, добавляем его в новый список: Здесь для добавления элемента в конец списка использован метод append. Второй вариант решения – использование генератора списка с условием. B = [x for x in A if x % 2 == 0 ] В цикле перебираются все элементы массива A, и только чётные из них включаются в новый массив. Особенности копирования списков в Python Как известно, имя переменной в языке Python связывается с объектом в памяти: числом, списком и др. При выполнении операторов A =[1, 2, 3] B = A две переменные A и B будут связаны с одним и тем же списком (рис. а), поэтому при изменении одного списка будет изменяться и второй, ведь это фактически один и тот же список, к которому можно обращаться по двум разным именам. На рис. б показана ситуация после выполнения оператора A[0] = 0: Эту особенность Python нужно учитывать при работе со списками. Если нам нужна именно копия списка (а не ещё одна ссылка на него), можно использовать срез, строящий копию: B = A[:] Теперь А и B – это независимые списки и изменение одного из них не меняет второй: Вместо среза можно было использовать функцию copy из модуля copy: Это так называемая «поверхностная» копия – она не создаёт полную копию, если список содержит какие‐то изменяемые объекты, например, другой список. Для полного копирования используется функция deepcopy из того же модуля: Контрольные вопросы (для ответа на тест) 1. Почему при поиске индекса максимального элемента не нужно хранить само значение максимального элемента? 2. Что такое реверс массива? 3. Как вы думаете, какую ошибку чаще всего делают начинающие, программируя реверс массива без использования встроенной функции? 4. Как вы думаете, какие проблемы (и ошибки) могут возникнуть при циклическом сдвиге массива вправо (без использования срезов)? 5. Что произойдет с массивом при выполнении следующего фрагмента программы: for i in range(N-1): A[i+1] = A[i] 6. Как (при использовании приведенного алгоритма поиска) определить, что элемент не найден? 7. Что такое выход за границы массива? Почему он может быть опасен? 8. Сравните разные методы отбора части элементов одного массива в другой массив. Какой из них вам больше нравится? Почему? 2.3 Сортировка Сортировка – это перестановка элементов массива в заданном порядке. Порядок сортировки может быть любым; для чисел обычно рассматривают сортировку по возрастанию (или убыванию) значений. Для массивов, в которых есть одинаковые элементы, используются понятия «сортировка по неубыванию» и «сортировка по невозрастанию». Возникает естественный вопрос: «зачем сортировать данные?». На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации. Программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах) и 2) сложные, но быстрые. Мы изучим два классических метода из первой группы и один метод из второй – знаменитую «быструю сортировку», предложенную Ч. Хоаром. Метод пузырька (сортировка обменами) Название этого метода произошло от известного физического явления – пузырёк воздуха в воде поднимается вверх. Если говорить о сортировке массива, сначала поднимается «наверх» (к началу массива) самый «лёгкий» (минимальный) элемент, затем следующий и т.д. Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно (меньший элемент «ниже»), то меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. (см. рисунок). Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так: Заголовок цикла тоже написан на псевдокоде. Обратите внимание, что на очередном шаге сравниваются элементы A[j] и A[j+1], поэтому цикл начинается с j=N-2. Если начать с j=N-1, то на первом же шаге получаем выход за границы массива – обращение к элементу A[N]. Поскольку цикл for в Python «не доходит» до конечного значения, мы ставим его равным «–1», а не 0: То есть, в записи range(N-2,-1,-1) первое число «–1» – это ограничитель (число следующее за конечным значением), а второе число «–1» ‐ шаг изменения переменной цикла. За один проход такой цикл ставит на место один элемент. Чтобы «подтянуть» второй элемент, нужно написать еще один почти такой же цикл, который будет отличаться только конечным значением j в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать: for j in range(N-2, 0 ,-1): if A[j+1]< A[j]: поменять местами A[j] и A[j+1] При установке следующего (3‐го по счёту) элемента конечное при вызове функции range будет равно 1 и т.д. Таких циклов нужно сделать N-1 – на 1 меньше, чем количество элементов массива. Почему не N? Дело в том, что если N-1 элементов поставлены на свои места, то оставшийся автоматически встает на своё место – другого места нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл: Записать полную программу вы можете самостоятельно. Часто используют более простой вариант этого метода, который можно назвать «методом камня» – самый «тяжёлый» элемент опускается в конец массива. Метод выбора Еще один популярный простой метод сортировки – метод выбора, при котором на каждом этапе выбирается минимальный элемент (из оставшихся) и ставится на свое место. Алгоритм в общем виде можно записать так: Здесь перестановка происходит только тогда, когда найденный минимальный элемент стоит не на своём месте, то есть i != nMin. Поскольку поиск номера минимального элемента выполняется в цикле, этот алгоритм сортировки также представляет собой вложенный цикл: «Быстрая сортировка» Методы сортировки, описанные в предыдущем параграфе, работают медленно для больших массивов данных (более 1000 элементов). Поэтому в середине XX века математики и программисты серьезно занимались разработкой более эффективных алгоритмов сортировки. Один из самых популярных «быстрых» алгоритмов, разработанный в 1960 году английским учёным Ч. Хоаром, так и называется – «быстрая сортировка» (англ. quicksort). Сортировка в Python Сортировка sort и sorted python 3 Sorted Функция sorted() - выполняет сортировку элементов списка и сохраняет новые значения в качестве копии. Исходный список или значение исходной переменной остается в том же виде, в котором было задано. Она использует алгоритм Timsort. Вот так можно построить новый массив B, который совпадает с отсортированным в порядке возрастания массивом A: B = sorted ( A ) По умолчанию выполняется сортировка по возрастанию (неубыванию). Для того, чтобы отсортировать массив по убыванию (невозрастанию), нужно задать дополнительный параметр reverse (от англ. «обратный»), равный True: B = sorted ( A, reverse = True ) Иногда требуется особый, нестандартный порядок сортировки, который отличается от сортировок «по возрастанию» и «по убыванию». В этом случае используют еще один именованный параметр функции sorted, который называется key (от англ. «ключ»). В этот параметр нужно записать название функции (фактически – ссылку на объект‐функцию), которая возвращает число (или символ), используемое при сравнении двух элементов массива. Предположим, что нам нужно отсортировать числа по возрастанию последней цифры (поставить сначала все числа, оканчивающиеся на 0, затем – все, оканчивающиеся на 1 и т.д.). В этом случае ключ сортировки – это последняя цифра числа, поэтому напишем функцию, которая выделяет эту последнюю цифру: def lastDigit ( n ): return n % 10 Тогда сортировка массива A по возрастанию последней цифры запишется так: B = sorted ( A, key = lastDigit ) Sort Метод sort() - принимает значения, меняет порядок и сохраняет заменяя ту информацию, которая существовала изначально. Изначально заданные данные изменяются и оказываются навсегда утерянными. Для демонстрации возьмем список из чисел Начальный порядок вернуть теперь нельзя, информация, содержащаяся в переменной, перезаписана. Контрольные вопросы (для ответа на тест) 1. Что такое сортировка? 2. На какой идее основан метод пузырька? метод выбора? 3. Объясните, зачем нужен вложенный цикл в описанных методах сортировки. 4. Сравните метод пузырька и метод выбора. Какой из них требует меньше перестановок? 5. Как нужно изменить приведенные алгоритмы, чтобы элементы массива были отсортированы по убыванию? 6. Какие встроенные средства сортировки массивов в Python вы знаете? 7. Как задать нестандартный порядок сортировки для функции sorted? 8. Чем отличаются функция sorted и метод sort для списков?