Массивы

Массив как структура данных

Массив (англ. array) - структура данных, хранящая набор значений. Каждое значение из набора индексируется, т.е. значения имеют номера (индексы).

Простейший массив имеет следующий интерфейс

1. создать(A, N) -> массив A длины N - создание массива A размера N.
2. записать(A, i, x) - записывает значение x в i-ый элемент массива A.
3. считать(A, i) -> элемент массива A с индексом i - взятие элемента по индексу (чтение).
4. удалить(A) - удаление массива А.

Обычно индексами массива являются целые положительные числа, причём в непрерывном диапазоне. Например, 0, 1, 2,... N-2, N-1, где N - размер массива. В таком случае массив упорядочен по индексу и можно говорить, что массив также является последовательностью.

Для массива операции чтения и записи выполняются за O(1), т.е. время этих операций не зависит от количества элементов в массиве.

Массив в Python

Массив в Python

упорядоченная изменяемая последовательность...

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

...объектов произвольных типов

элементами массива являются Python-объекты. При этом допускается, чтобы в одном массиве хранились объекты разных типов.

Массивы в Python также называют списками или листами (англ. list). Терминология в других языках программирования, а также в теории алгоритмов может быть другая.

Список Python является гибким в использовании объектом. Как инструмент, программист может использовать списки, например, для создания элементов линейной алгебры: точек, векторов, матриц, тензоров. Или, например, для таблицы с некоторыми данными.

Важно заметить, что <class 'list'>, питоновский список, является универсальной структурой данных. В том числе, ей можно пользоваться как массивом (что мы и будем делать)! То есть, у этого объекта есть интерфейс, описанный в предыдущем разделе, причём с теми же асимптотиками, хотя возможности выходят гораздо за пределы простейшего массива.

Создание массива

>>> []
[]
>>> [0, 1, 2, 3, 4]
[0, 1, 2, 3, 4]
>>> ['sapere', 'aude']
['sapere', 'aude']
>>> ['Gravitational acceleration', 9.80665, 'm s^-2']
['Gravitational acceleration', 9.80665, 'm s^-2']
>>> type([0, 1, 2, 3, 4])
<class 'list'>

>>> A = [0] * 10
>>> A
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> type(A)
<class 'list'>

>>> A = [0] * 3  # [0, 0, 0]
>>> B = [1] * 3  # [1, 1, 1]
>>> C = [2] * 3  # [2, 2, 2]
>>> D = A + B + C
>>> D
[0, 0, 0, 1, 1, 1, 2, 2, 2]

>>> [0, 1] * 3
[0, 1, 0, 1, 0, 1]
>>> [0, 1] + [0, 1] + [0, 1]
[0, 1, 0, 1, 0, 1]

Элементы массива: доступ и изменение

Выше мы убедились, что массив это множество объектов различных типов, теперь убедимся, что это упорядоченная последовательность изменяемых объектов.

>>> ['Gravitational acceleration', 9.80665, 'm s^-2'][0]
'Gravitational acceleration'
>>> ['Gravitational acceleration', 9.80665, 'm s^-2'][1]
9.80665
>>> ['Gravitational acceleration', 9.80665, 'm s^-2'][2]
'm s^-2'
>>> l = [10, 20, 30]
>>> l[0]
10
>>> l[1]
20
>>> l[2]
30

>>> l
[10, 20, 30]
>>> l[3]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range

>>> l
[10, 20, 30]
>>> len(l)
3
>>> l[len(l) - 1]
30

>>> l
[10, 20, 30]
>>> l[-1]
30
>>> l[-2]
20
>>> l[-3]
10
>>> l[-4]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range

>>> l = [10, 20, 30]
>>> l
[10, 20, 30]
>>> l[0] = 0
>>> l
[0, 20, 30]
>>> l[2] = 55
>>> l
[0, 20, 55]

>>> l
[0, 20, 55]
>>> i = 0
>>> while i < len(l):
...     print(i, l[i])
...     i += 1
...
0 0
1 20
2 55
>>>

>>> l
[0, 20, 55]
>>> for i in range(len(l)):
...     print(i, l[i])
...
0 0
1 20
2 55

Печать массива

Чтобы распечатать элементы массива в столбец, воспользуйтесь циклом for, как в разделе выше.

Если нужно распечатать массив в строку, то воспользуйтесь функцией print:

>>> A = [0, 1, 2, 3]
>>> print(*A)
0 1 2 3

Здесь знак * это операция развёртывания коллекции по аргументам функции. Функция print принимает на вход сколько угодно аргументов и действие выше эквиваленто следующему:

>>> print(A[0], A[1], A[2], A[3])
0 1 2 3

Ремарка о строках

На самом деле, мы уже ранее сталкивались с массивами в предудыщих лабораторных, когда использовали строковый метод str.split:

>>> s = "ab cd ef1 2 301"
>>> s.split()
['ab', 'cd', 'ef1', '2', '301']

Т.е. str.split, по умолчанию, разбивает строку по символам пустого пространства (пробел, табуляция) и создаёт массив из получившихся "слов".

Загляните в help(str.split), чтобы узнать, как изменить такое поведение, и разбивать строку, например, по запятым, что является стандартом для представления таблиц в файлах csv (comma separated values).

Методом, являющимся обратным к операции str.split является str.join. Он "собирает" строку из массива строк:

>>> s
'ab cd ef1 2 301'
>>> l = s.split()
>>> l
['ab', 'cd', 'ef1', '2', '301']
>>> l[-1] = '430'
>>> l
['ab', 'cd', 'ef1', '2', '430']
>>> ','.join(l)
'ab,cd,ef1,2,430'
>>> ' -- '.join(l)
'ab -- cd -- ef1 -- 2 -- 430'

Работа с двумерными массивами

Как вам рассказали, в массиве мы можем хранить различные данные. В том числе в ячейке массива можем хранить другой массив. Давайте предположим, что в каждой ячейке массива размера N у нас будет храниться другой массив размера M. Таким образом мы можем построить таблицу или матрицу размера N x M.

Создание двумерного массива (матрицы) размера N x M в питоне:

a = []
for _ in range(n):
  a.append([0] * m)

или

a = [[0] * m for _ in range(n)]

Обращение к элементами двумерного массива:

a[i][j] = 5

Контест №5

Ссылки на контесты

• Начинающие (участвовать)
• Основные (участвовать)
• Продвинутые (участвовать)

Массивы в Python, часть 2

Создание массива

>>> arithm = [ x for x in range(10) ]
>>> squares = [ x**2 for x in range(10) ]
>>> arithm
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

>>> A = [ i * j for i in range(1, 5) for j in range(1, 5)]
>>> A
[1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16]
>>> odd_squares = [ i**2 for i in range(10) if i % 2 == 1 ]  # массив из квадратов нечётных чисел
>>> odd_squares
[1, 9, 25, 49, 81]

>>> A = [int(input()) for i in range(5)]  # считывание массива размера 5 с клавиатуры
9
0
-100
2
74
>>> A
[9, 0, -100, 2, 74]

>>> list("sapere aude")
['s', 'a', 'p', 'e', 'r', 'e', ' ', 'a', 'u', 'd', 'e']
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> s = input()
1 2 -1 93 100
>>> s
'1 2 -1 93 100'
>>> A = list(map(int, s.split()))
>>> A
[1, 2, -1, 93, 100]

Изменение массива

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

>>> fibs = []
>>> fibs.append(1)
>>> fibs
[1]
>>> fibs.append(1)
>>> fibs
[1, 1]
>>> fibs.append(2)
>>> fibs
[1, 1, 2]
>>> fibs.append(3)
>>> fibs
[1, 1, 2, 3]

>>> fibs = [1, 1, 2, 3]
>>> fibs
[1, 1, 2, 3]
>>> fibs.pop()
3
>>> fibs
[1, 1, 2]
>>> fibs.pop()
2
>>> fibs
[1, 1]

>>> A = [1, 9, 10, 3, -1]
>>> A
[1, 9, 10, 3, -1]
>>> A.insert(0, 'i')
>>> A
['i', 1, 9, 10, 3, -1]
>>> A.insert(5, 'i2')
>>> A
['i', 1, 9, 10, 3, 'i2', -1]

>>> B = ['popme', 1, 0, 'popme2', 3, -100]
>>> B.pop(0)
'popme'
>>> B
[1, 0, 'popme2', 3, -100]
>>> B.pop(2)
'popme2'
>>> B
[1, 0, 3, -100]

Соединение и копирование массивов

Массивы можно соединять in place, т.е. перезаписывая, с помощью метода list.extend:

>>> A = [0, 1, 2]
>>> B = [3, 4, 5]
>>> id(A)
4337064576
>>> A.extend(B)
>>> id(A)
4337064576
>>> A
[0, 1, 2, 3, 4, 5]
>>> B
[3, 4, 5]

Заметим, что оператор + для списков создаёт новый список.

С копированием массивов нужно быть осторожным. Python никогда не осуществляет копирование явно:

>>> A = [0, 1, 2]
>>> B = A
>>> B[1] = 'take_care!'
>>> A
[0, 'take_care!', 2]
>>> B
[0, 'take_care!', 2]
>>> A is B
True

В строчке B = A лишь создаётся ещё одна ссылка на объект [0, 1, 2], которая присваивается переменной B. В итоге A и B будут указывать на один и тот же объект.

Чтобы создать копию, необходимо поэлементно создать новый массив из исходного. Например, с помощью функции list() или метода list.copy:

>>> A = [0, 1, 2]
>>> B = list(A)
>>> C = A.copy()
>>> A is B
False
>>> A is C
False
>>> B is C
False
>>> A
[0, 1, 2]
>>> B
[0, 1, 2]
>>> C
[0, 1, 2]

Приведённые способы копирования работают для списков, содержащих неизменяемые объекты. Если же вы работаете с двумерным массивом или чем-то более сложным, то функцию явного копирования стоит написать самому, либо воспользоваться функцией copy.deepcopy из библиотеки copy.

Питонизмы

Конструкции с использованием while и for, изложенные в первой части лабораторной, имеют аналоги практически во всех языках программирования. Они универсальны, стандартны, переносимы из языка в язык.

Этот раздел относится только к особенностям языка Python.

Не злоупотребляйте питонизмами, наша цель - освоить алгоритмы и структуры данных, а не Python.

В языке Python цикл for на самом деле является синтаксическим сахаром, поддерживающим концепцию итерируемого объекта. Его обобщённый синтаксис выглядит примерно так:

for item in any_iterable:
    # тело цикла

Здесь item это выбранное программистом имя переменной итерирования, которая доступна в теле цикла. В начале каждой итерации в эту переменную помещается значение из any_iterable. Под any_iterable может стоять любой итерируемый объект.

Знакомые нам примеры итерируемых объектов:

• range - генератор арифметической последовательности, for "просит" новые значения у генератора, пока те не закончатся
• str - строковый тип, итерирование происходит по символам
• list - список, итерирование происходит по элементам

Таким образом, pythonic way пробега по списку может выглядеть так:

>>> l
[0, 20, 55]
>>> for elem in l:
...     print(elem)
...
0
20
55

Отсюда видно, что программист в таком случае теряет удобный способ получить индекс элемента, если он ему нужен.

Под подобные мелкие задачи существует множество "питонизмов" - специфических для языка Python инструментов.

Один из примеров - enumerate - позволяет программисту получить в цикле индекс итерации (!) (а не индекс элемента) и сам элемент.

При таком использовании номер итерации совпадает с индексом элемента:

>>> l
[0, 20, 55]
>>> for i, elem in enumerate(l):
...     print(i, elem)
...
0 0
1 20
2 55

Код приведённый для enumerate выше, аналогичен универсальным:

>>> l
[0, 20, 55]
>>> for i in range(len(l)):
...     elem = l[i]
...     print(i, elem)
...
0 0
1 20
2 55

>>> l
[0, 20, 55]
>>> i = 0
>>> while i < len(l):
...     elem = l[i]
...     print(i, elem)
...     i += 1
...
0 0
1 20
2 55