§ 9.3. Последовательности. Список и кортеж

Школьный курс C++
Содержание

Что такое последовательность и для чего она нужна?

Последовательность (англ. sequence) – это структура данных (англ. data structures), содержащая совокупность элементов с общим для всех элементов именем. В python существует две категории последовательностей: изменяемые (mutable) и неизменяемые (immutable). К первой относятся следующие типы: списки (list) и bytearray. Ко второй: строки (str), кортежи (tuple) и байты (bytes). Также к последовательностям относят числовой массив (array), который доступен в модуле collections.
Представьте, что вам для решения некоторой задачи (например, для обработки базы данных клиентов, описания координат объектов и проч.) требуется наличие в программе не 3-5 переменных, а 10, 100, 1000 или значительно больше! Работать в программе с таким количеством переменных просто невозможно. Проще определить их в виде единого объекта и обращаться, по мере необходимости, к отдельным его элементам, которые организованы простой нумерацией (иными словами, проиндексированы). Поскольку все элементы последовательности имеют общее имя, то к отдельному элементу можно получить доступ по имени и индексу, поэтому элемент последовательности называется также индексированной переменной. С таким массивом данных работать очень удобно, так как он обрабатывается как единое целое с помощью циклов.
На этом уроке мы рассмотрим три типа последовательностей: list, tuple и array.

Списки. Тип list

Определение. Работа с элементами

Список может содержать любое количество любых объектов, в том числе и вложенные списки. Определить пустой список довольно просто:

L = []

Здесь L – имя списка (в данном случае – пустого). Если нужно инициализировать список, то элементы списка нужно перечислить в квадратных скобках через запятую:

L = [1, 1000, 'a', 3.14]

Каждый элемент списка имеет номер (индекс), первый элемент имеет индекс [0] (L[0]). Использовать в программе элементы списка можно также, как и обычные переменные.

s = L[0] + L[1] # s => 1001
L[0] = round(L[3] * 3 ** 0.5 / 2, 2) # L[0] => 2.72
L[1] //= 2 # L[1] => 500
L[2] *= 3 # L[2] => 'aaa'
Перебор и вывод элементов

Получить последовательный доступ ко всем элементам массива можно с помощью цикла for. Но теперь цикл for используется по своему прямому назначению – обходу последовательности. Выведем все элементы списка L:

for i in L:
    print(i)

В отличие от последовательности range, элементы списка сохраняются в памяти, поэтому в цикле их можно изменять:

Программа 9.3.1
L = [3, 2, 5, 7, 1, 4, 9, 6, 8]
for j in L:
    if not j % 2:
        j *= 3
    else:
        j += 5 
    print(j, end='')

Вывод

8 6 10 12 6 12 14 18 24

Если в цикле, при решении задачи, необходимо осуществлять доступ только к определенным элементам (например, с четным индексом), то необходимо использовать цикл с range(), а индексы перебирать с помощью переменной цикла:

Программа 9.3.2
L = [3, 2, 5, 7, 1, 4, 9, 6, 8]
for j in range(0, len(L), 2):
    L[j] *= 10 
print(L)

Вывод

[30, 2, 50, 7, 10, 4, 90, 6, 80]

Для указания границы списка (последнего индекса) в range() применяется функция len(), которая возвращает длину последовательности.
Если форматирование вывода списка не требуется, то его можно вывести в неформатированном виде, по имени, как показано в примере выше.

Ввод элементов с клавиатуры

С клавиатуры элементы списка можно ввести двумя способами:

  1. ввести список целиком, разделяя элементы символом-разделителем (обычно пробелом);
  2. вводить список поэлементно с помощью цикла.

В первом случае используется метод split() класса str, который возвращает список строк:

L = input().split()

Числовой список можно получить более сложным выражением:

L = map(float, input().split())

Здесь используются еще две функции: функция преобразования float() (если необходимо получить список действительных чисел) и функция map(), которая применяет данную функцию к каждому элементу списка, полученному с помощью метода split().
Список является динамическим массивом. С помощью различных методов класса list можно изменять размер массива вставляя или удаляя элементы в различных позициях. Для добавления элементов в конец списка используется метод append(). Если список создается на основе пустого списка, то заполнение списка можно организовать следующим кодом:

Программа 9.3.3
L = [] # Создаем пустой список
n = int(input()) # определяем количество элементов
for j in range(n): # получаем список целых чисел
    L.append(int(input()))
Создание списка на основе последовательности range

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

Программа 9.3.4
L = list(range(10, 100, 10))
print(L)

Вывод

[10, 20, 30, 40, 50, 60, 70, 80, 90]
Заполнение списка случайными числами

Для решения целого ряда задач требуется получать массивы случайных чисел. Процесс заполнения списка случайными числами полностью аналогичен процессу заполнения списка поэлементно в цикле.
Решим задачу на вывод элементов по заданному условию.
Задача 1. Дан массив случайных чисел, состоящий из 20 элементов. Вывести сначала только элементы с четными индексами, а затем с нечетными, но в обратном порядке.

Программа 9.3.5
from random import seed, randint
seed()
L = []
for j in range(20):
    L.append(randint(10, 99))
print(L)
for j in range(0, len(L), 2):
    print(L[j], end=' ')
print()
for j in range(len(L) - 1, 0, -2):
    print(L[j], end=' ')

Возможный вывод

[76, 10, 67, 92, 18, 55, 97, 62, 31, 78, 27, 96, 27, 92, 46, 25, 24, 12, 98, 30]
76 67 18 97 31 27 27 46 24 98 
30 12 25 92 96 78 62 55 92 10 

Рассмотрим пример решения задачи на поиск и обмен значениями между элементами.
Задача 2. Дан массив случайных чисел, состоящий из 20 элементов. Определить позицию минимального элемента (если их несколько, то ближайшего к началу) массива и обменять его с первым элементом.

Программа 9.3.6
from random import seed, uniform
seed()
L = []
for j in range(20):
    L.append(uniform(10, 99))
for j in L:
    print('{:.2f}'.format(j), end=' ')
min, i = 100., 0
for j in range(0, len(L)):
    if L[j] < min:
        min, i = L[j], j
L[0], L[i] = L[i], L[0]
print()
for j in L:
    print('{:.2f}'.format(j), end=' ')

Возможный вывод

89.08 47.11 25.65 96.44 50.68 92.20 47.47 57.85 18.89 15.39 20.69 81.34 14.09 59.68 94.78 90.95 21.32 55.82 69.44 33.67 
14.09 47.11 25.65 96.44 50.68 92.20 47.47 57.85 18.89 15.39 20.69 81.34 89.08 59.68 94.78 90.95 21.32 55.82 69.44 33.67

В подобных задачах необходимо показать массивы исходный и модифицированный.

Кортежи. Тип tuple

Кортеж – это неизменяемая последовательность элементов различного типа. Хотя кортеж поддерживает базовые операции для всех последовательностей (см. ниже), но его основное назначение – это передача данных в функции и возвращение данных из функций в виде единого объекта так, как мы это сделали в программе 9.2.7 предыдущего урока. Мы также использовали кортеж для организации циклических вычислений (например, в программе 9.1.7). Существуют и другие сферы применения кортежа в python с которыми мы познакомимся позднее. Хотя для создания кортежа используются круглые скобки, на самом деле, кортеж создает запятая, поэтому скобки часто опускают. Операция обмена данными между объектами, которую мы применяли не раз, в действительности является операцией распаковки кортежа:

T = (1, 2, 3)
(a, b, c) = T
print(a, b, c)

Скобки используются только в том случае, когда в качестве аргумента кортеж передается явно, а не по имени:

fun((1, 2, 3))

Кортеж может быть создан на основе любой последовательности, например:

L = [1, 2, 3]
S = 'abc'
Tl = tuple(L)
print(Tl)
Ts = tuple(S)
print(Ts)

Вывод

(1, 2, 3)
('a', 'b', 'c')
Не взирая на то, что элементы кортежа неизменяемы, элементом кортежа может быть список, а его элементы изменить можно.

Общие операции последовательностей

Изменяемые и не изменяемые последовательности имеют общие операции, которые перечислены в таблице ниже.

Таблица 1. Общие операции последовательностей
Операция Описание
x in s True, если елемент x есть в последовательности s
x not in s True, если елементa x нет в последовательности s
s + t Объединение двух последовательностей s и t
s * n Добавление к s копии s, n раз
s[i] Индексирование элементов, начиная с 0
s[i:j:k] Срез* от i до j с шагом k
len(s) Длина последовательности s
min(s) Минимальный элемент последовательности s
max(s) Максимальный элемент последовательности s
s.index(x[, i[, j]]) позиция первого вхождения x в s (начиная с i (входит) и заканчивая j (не входит)
s.count(x) Количество вхождений x в s
*Срезы мы рассмотрим на следующем уроке

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

L.index(min(L))

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

Модификаторы списка

Наряду с общими операциями для всех последовательностей, класс list имеет набор модифицирующих методов, которые изменяют список. Эти методы перечислены в таблице ниже.

Таблица 2. Методы List
Метод Описание
L.append(x) Добавляет элемент в конец списка. Эквивалентно L[len(L):] = [x]
L.extend(iterable) Расширяет список, добавляя все элементы из коллекции iterable. Эквивалентно L[len(L):] = iterable
L.insert(i, x) Вставляет элемент в заданной позиции. Первый аргумент является индексом элемента перед которым осуществляется вставка
L.remove(x) Удаляет из списка первый элемент, значение которого равно х. Возвращается ошибка, если такой элемент не будет найден
L.pop([i]) Удаляет элемент в данной позиции i и возвращает его. Если не указан индекс, L.pop() удаляет и возвращает последний элемент из списка. (Квадратные скобки означают, что параметр является необязательным)
L.clear() Удаляет из списка все его элементы. Эквивалентно del L[:]
L.sort(key=None, reverse=False) Сортировка списка
L.reverse() Реверс элементов списка (расположение элементов меняется на обратный порядок)
L.copy() Возвращает неполную копию списка. Эквивалентно L[:]

Числовой массив array

Списки очень удобны для работы с массивами, но, ввиду того, что объект list – это динамический массив, а элементами этого массива могут быть одновременно объектами разного типа, list имеет низкую эффективность по используемой памяти при работе с простыми типами. Осознавая это, разработчики python создали специальный класс эффективных изменяемых числовых массивов array.

Следует иметь в виду, что и list, и array имеют практически равную эффективность по скорости работы с простыми типами. Т. о. переходить к работе с array нужно только в том случае, если нужна эффективность по памяти, а ширина типа не будет превосходить соответствующей ширины простого типа.

Эта последовательность вынесена в одноименный модуль – array (иными словами, array не является стандартным типом). Каким же образом разработчики добились большей эффективности? Всё просто: объект массива содержит данные только одного числового типа (см. таблицу ниже). Это является “слабой” типизацией в python, что приводит к классическому построению структуры данных так, как это реализовано в языках со строгой типизацией. Т. е. данные хранятся в одной области памяти, в соседних ячейках, поскольку ячейки памяти выровнены в сответствии с шириной типа. При этом числовые типы определяются так, как определяются числовые типы в языках C/C++. Во время создания объекта конструктор принимает один обязательный аргумент – “код символа”. Это символ указывающий на тип данных элементов создаваемого массива.

Таблица 3. Коды типов array
Код Тип С/С++ Тип python Ширина
b signed char int 1
B unsigned char int 1
u wchar_t int 2
h signed short int 2
H unsigned short int 2
i signed int int 2
I unsigned int int 2
l signed long int 4
L unsigned long int 4
q signed long long int 8
Q unsigned long long int 8
f float float 4
d double float 8

Поскольку array изменяемая последовательность, то для неё определены методы (в данном классе), которые являются общими и для других изменяемых последовательностей, например: append, count, index, insert, remove и др. Конструктор array имеет также необязательный аргумент последовательность-инициализатор (таковым может быть, например, list, содержащий числовые данные):

array.array(typecode[, initializer])

Наиболее употребительные методы, определенные для array, приведены в таблице 4. Рассмотрим пример.
Задача 3. Дан массив 20 целых чисел и целые числа K и L (1 ≤ K ≤ L ≤ N). Найти среднее арифметическое элементов массива с номерами от K до L включительно.

Программа 9.3.7
from array import *
from random import seed, randint
seed()
ar = array('i') # тип элементов соответствует типу int C++
for j in range(20): # заполняем случайными числами
    ar.append(randint(10, 99))
print('Исходный массив:')
for j in ar: # выводим
    print(j, end=' ')
print()
k = int(input('k = '))
l = int(input('l = '))
s = 0
for j in range(k, l+1):
	s += ar[j]
print(s / (l-k+1), sep = '\n')

Возможный вывод

Исходный массив:
93 18 82 93 28 95 97 17 98 55 59 70 49 69 46 71 23 76 21 86 
k = 2
l = 11
69.4
Таблица 4. Некоторые методы array
Метод Описание
ar.append(x) Добавляет элемент в конец масива
ar.extend(iterable) Расширяет массив, добавляя все элементы из коллекции iterable (код типа должен совпадать)
ar.insert(i, x) Вставляет элемент в заданной позиции. Первый аргумент является индексом элемента перед которым осуществляется вставка
ar.remove(x) Удаляет из массива первый элемент, значение которого равно х. Возвращается ошибка, если такой элемент не будет найден
ar.pop([i]) Удаляет элемент в данной позиции i и возвращает его. Если не указан индекс, ar.pop() удаляет и возвращает последний элемент из массива
ar.reverse() Реверс элементов массива (расположение элементов меняется на обратный порядок)
ar.fromfile(f, n) Читает n элементов из файлового объекта f и добавляет их в конец массива. Если доступно меньше, чем n элементов, то возбуждается исключение EOFError, но доступные элементы будут добавлены.
ar.tofile(f) Записывает все элементы в файловый объект f
ar.fromlist(list) Добавляет элементы из списка list
ar.tolist() Преобразует массив в список с теми же элементами

Альтернативой для быстрой работы с числовыми массивами является сторонняя разработка – библиотека NumPy, которая предлагает широкий математический инструментарий, а также значительно более эффективную работу с линейными и многомерными массивами как по памяти, так и по скорости выполнения. Но, поскольку данная библиотека не принадлежит среде python, в школьном курсе она рассматриваться не будет.

Задачи с массивами

Рассмотрим несколько типичных задач на использование массивов в программе. В задачах, представленных ниже, используется массив случайных (целых) чисел. Массив обязательно выводится после заполнения. Реализация задач представлена в виде функций.

I. Поиск или подсчет элементов по критерию

Задача 4. Дан массив из 50 элементов L и число r. Найти элемент массива, который наиболее близок к числу r (т. е., такой элемент k, для которого величина |k – r| является минимальной).

Программа 9.3.8
from random import seed, randint
seed()
L = []
for j in range(50):
    L.append(randint(10, 99))
print(L)

def fun(r, L):
    elem = None
    mind = 100
    for j in range(0, len(L)):
        if abs(L[j] - r) < mind:
            mind = abs(L[j] - r)
            elem = j 
    return elem # Возвращаем позицию элемента

R = int(input('R = '))
print('Элемент - L[{:}] => {:}'
      .format(fun(R, L), L[fun(R, L)]))

Возможный вывод

[44, 84, 21, 54, 19, 84, 21, 93, 36, 26, 68, 22, 48, 88, 76, 44, 65, 55, 26, 95, 14, 65, 91, 90, 45, 92, 50, 22, 51, 16, 13, 32, 33, 75, 29, 73, 15, 84, 67, 20, 21, 43, 68, 36, 35, 62, 78, 67, 63, 95]
R = 30
Элемент - L[34] => 29
II. Анализ элементов массива

Задача 5. Дан массив из 50 элементов L определить в массиве самую длинную цепочку равных между собой элементов и позицию с которой она начинается.

Программа 9.3.9
from random import seed, randint
seed()
L = []
for j in range(50):
    L.append(randint(0, 1))
print(L)

def f(L):
    maxd = 0
    k, i = 0, None
    for j in range(0, len(L)-1):        
        if L[j] == L[j + 1]: # Если соседние элементы равны,
            k += 1 # то считаем длину цепочки
        else:
            k += 1 # добавляем оставшийся
            if k > maxd: # Проверяем длину цепочки:
                maxd = k # если нашли длиннее, то сохраняем длину
                i = j # и позицию последнего элемента
            k = 0 # обнуляем счетчик   
    return maxd, i + 1 - maxd # возвращаем кортеж

d, n = f(L) # Распаковка кортежа
print('Начало цепочки - L[{:}], длина - {:}'
      .format(n, d))

Возможный вывод

[0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0]
Начало цепочки - L[43], длина - 5
III. Преобразование массива

Задача 6. Дан массив из 50 элементов L. Развернуть в обратном порядке элементы находящиеся между L[k] и L[m] элементами, включительно (k < m).

Программа 9.3.10
from random import seed, randint
seed()
L = []
for j in range(50):
    L.append(randint(10, 99))
print(L)

def Swap(a, b):
    return (b, a)

def rot(k, m, L):
    for j in range((m - k + 2) // 2):
        L[k + j], L[m - j] =\
            Swap(L[k + j], L[m - j])

k = int(input('k = '))
m = int(input('m = '))
rot(k, m, L)
print(L)

Возможный вывод

[57, 12, 79, 23, 65, 53, 59, 11, 31, 24, 90, 80, 51, 81, 63, 89, 41, 97, 87, 94, 18, 66, 11, 73, 31, 15, 97, 22, 50, 51, 53, 78, 56, 13, 80, 24, 19, 19, 25, 34, 68, 53, 16, 94, 72, 48, 11, 49, 52, 18]
k = 2
m = 8
[57, 12, 31, 11, 59, 53, 65, 23, 79, 24, 90, 80, 51, 81, 63, 89, 41, 97, 87, 94, 18, 66, 11, 73, 31, 15, 97, 22, 50, 51, 53, 78, 56, 13, 80, 24, 19, 19, 25, 34, 68, 53, 16, 94, 72, 48, 11, 49, 52, 18]

Приложение

Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Обсуждение закрыто.