
Size: a a a
id()
. В реализации CPython она возвращает адрес, по которому объект находится в памяти. Создадим список и посмотрим, в ячейке с каким номером он окажется. >>>beatles = [“Ringo”, “Paul”, “John”, “George”]
>>>id(beatles)
140181376779336
Видим, что список лежит по адресу 140181376779336. Теперь изменим какой-нибудь элемент списка и посмотрим, изменился ли адрес.>>>beatles[0] = “Pete”
>>>beatles
[“Pete”, “Paul”, “John”, “George”]
>>>id(beatles)
140181376779336
Видим, что адрес списка не меняется, если мы изменяем элементы, которые в него входят. Теперь создадим в памяти строку >>>bass = "Paul"и добавим в нее что-нибудь
>>>id(bass)
140068833595776
>>>bass += " McCartney"
>>>bass
Paul McCartney
>>>id(bass)
140068833600432
Видим, что адрес строки изменился. Класс Описание Мутабелен?Количество встроенных иммутабельных типов в python больше, но если вы захотите создать свой класс, он будет мутабельным.
---------------------------------
bool булевый тип ☹️
int целочисленный тип ☹️
float число с плавающей запятой ☹️
list список ☺️
tuple кортеж ☹️
str строка ☹️
set множество ☺️
dict словарь ☺️
TypeError: unhashable type: 'list'Поэтому мутабельные объекты, такие как словари или списки, не могут быть ключами в словаре или элементами множества. А вот строки или числа могут. И это на самом деле очень естественно🐍
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
Здесь ob_item
-- это непрерывный массив указателей на элементы списка, а allocated
содержит длину массива. Вот и все, что нужно знать, чтобы отвечать на вопросы о сложности операций со списками. len(a) # O(1)
Ещё сразу понятно, что при такой реализации стоимость индексирования не зависит от длины списка или значения индекса, так как изменить значение по известному номеру ячейки тоже можно тоже за O(1). a[10] = 5 # O(1)
А вот чтобы найти значение в списке, придется обходить каждую ссылку и проверять содержимое на равенство. Поэтому проверить вхождение -- операция дорогая, в худшем случае O(n). 5 in a # O(n)
Добавление одиночных элементов в конец списка (метод append()
) в большинстве случаев работает за O(1). Но здесь есть одна деталь: место в памяти для массива указателей аллоцируется заранее. И когда занятый объем памяти истощается, интерпретатор выделяет ещё примерно 15% от объема массива. Эта периодическая экспансия время от времени несколько замедляет добавление новых элементов в список, поэтому об O(1) можно говорить условно. a.append(5) # ~O(1)
Еще одна распространенная потребность это конкатенировать списки, например, с помощью оператора +
. Сложность конкатенации линейно зависит от длины присоединяемого списка: если его длина 100 элементов, то нужно 100 раз добавить в конец новый элемент. a + b # ~O(k)
Чтобы получить доступ к элементам слайса a[i:j]
, нужно итерироваться между индексами i и j. Поэтому сложность такой операции O(k), где k -- длина слайса. А вот удалить слайс это O(n), из-за необходимости сдвинуть все следующие за удаленным участком элементы на новые места, здесь n -- длина всего массива.a[i:j] # ~O(k)
del a[i:j] # ~O(n)
Метод, который получает и удаляет последний элемента списка pop()
, имеет сложность O(1), в то время как pop(i)
элемента из середины списка требует O(n). Почему так? Потому что после того, как один указатель был удален из середины или начала, нужно передвинуть все следующие за ним на 1 позицию вперёд. А когда элемент был удален из конца массива, этого делать не нужно. По этой же причине введение или элемента в середину списка тоже дорогая операция и требует O(n) операций.
a.pop() #O(1)
a.pop(i) #O(n)
a.insert(i, item) #O(n)
Обобщим:Операция Сложность
----------------------
len(a) O(1)
a[i] O(1)
a[10] = 5 O(1)
5 in a O(n)
a.append(5) ~O(1)
a + b O(k)
a[i:j] O(k)
del a[i:j] O(n)
a.pop() O(1)
a.pop(i) O(n)
a.insert(i, item) O(n)
В общем, чтобы отвечать на вопросы о сложности операций со списками, нужно понимать, как они устроены на низком уровне. Самые дорогие операции -- те, которые требуют обхода части или всего списка, например, поиск значения в списке, конкатенация, слайсинг, удаление или добавление элементов в начало списка. Самые экономные операции -- получение длины списка, операции с элементами в конце списка и со значениями по известному индексу. append()
требует только O(1)🐍sum = 0
for i in range(0, 10000000000):
sum += 4
print(sum)
Если я попробую посчитать то же самое на калькуляторе, то замечу, что лаптоп отрабатывает заметно медленнее, несмотря на то, что он мощнее. Почему? Потому что для умножения чисел существует несколько алгоритмов, а я выбрала самый неэффективный из них. Ещё есть, например, метод Карацубы, или алгоритм на основе преобразования Фурье. В калькуляторах обычно используется второй, и он требует значительно меньше операций, чем наивный.import time
start = time.time()
my_awesome_alg()
end = time.time()
print(end - start)
Но мы обнаружим, что скорость зависит от производительности машины, от ее архитектуры и загруженности в момент выполнения программы. Поэтому физическое время никак не поможет нам оценить эффективность алгоритма.==
проверяет, одинаковые ли значения у переменных.is
проверяет, указывают ли переменные на один и тот же объект.a = [1, 2, 3]Теперь создадим новый словарь с помощью копирования:
b = a
b is a # True
b == a # True
b = a[:]Но из-за того, что мы скопировали в новый объект все значения старого, то содержимое двух словарей все равно совпадает:
b is a # False
>>> b == a # TrueТо есть,
a is b
по сути то же, что id(a) == id(b)
. Поэтому если a is b
вернет True
, это будет значить, что и содержимое у них одинаковое. Просто потому что это один и тот же объект.is
, а не ==
:a = 42Дело в том, что класс
a is None # False
None
реализован как синглтон. Это значит, что экземпляр этого класса существует в интерпретаторе в единственном числе и все неопределенные значения указывают на него. a = NoneДля некоторых классов оператор
b = None
a is b # True
==
тоже сработает, но так лучше не делать, потому что в пользовательских классах этот оператор можно переопределить и выстрелить себе в ногу получить интересные результаты. Поэтому в PEP8 и рекомендуют проверять на значение None
именно с помощью is
. 🐍fish = {
"move": "water",
"eat": "insects",
"say": None
}
Используя конструктор явно: snail = dict(
eat=”leaves”,
move=”ground”,
say=None
)
Или инициализируя его кортежами: cow = dict([
(“move”, “ground”),
(“eat”, “grass”),
(“say, “moo”)
])
Четвертый, с помощью генераторных выражений (версия интерпретатора 3.5 и выше):>>> animals = [“snail”, “fish”, “cow”]
>>> {animal: it for it, animal in enumerate(animals)}
{'snail': 0, 'fish': 1, 'cow': 2}
Этот трюк еще бывает полезен, если нужно поменять местами ключи и значения:>>> {v: k for k, v in animals.items()}
{1: 'snail', 2: 'fish', 3: 'cow’}
Только будьте осторожны, потому что ключи в словаре должны быть уникальны. Если какие-то значения исходного словаря совпадали, то, когда они станут ключами нового, дубликаты исчезнут. >>> animals = ["frog", "snail", "bird"]
>>> numbers = [1, 2, 3]
>>> dict(zip(animals, numbers))
{'snail': 2, 'frog': 1, 'bird': 3}
Почему так много? Потому что каждый удобен под свой случай.🐍>>>
capitals = ['Beijing', 'New Delhi']
Добавим в него ещё город и сделаем diff двух файлов перед коммитом. >>>
capitals = ['Beijing', 'New Delhi', 'Mexico City']
Инструмент подсветит строчку и будет сложнее понять, какой именно элемент добавили, особенно если список длинный. Поэтому лучше писать: >>>
capitals = [
'Beijing',
'New Delhi'
'Mexico City'
]
Так на diff'е будет видно, какой именно элемент появился, и делать ревью тоже будет проще. Кстати, вы заметили, что я забыла запятую? Это частая ошибка, и довольно неприятная, потому что при этом не только не будет брошено исключение, но и объединятся две последние строки: >>>
capitals
['Beijing', 'New DelhiMexico City']
Упс😕. Строки, не разделенные запятой, в Python конкатенируются. Это удобно для того, чтобы размещать в коде длинные тексты без переноса строки: >>>
why_so = ('Это очень очень '
'очень длинная строка или '
'документ на вашем сайте.')
>>> why_so
'Это очень очень очень длинная строка или документ на вашем сайте.'
Но иногда это играет с разработчиками злую шутку. Поэтому, чтобы не забывать добавлять запятую в предпоследнем элементе, хорошей практикой считается всегда ставить запятую в конце коллекции:>>>
capitals = [
'Beijing',
'New Delhi',
'Mexico City',
]
Она не повлияет на выполнение программы, зато уменьшит вероятность ошибки программиста. При этом diff будет читаться лучше, потому что утилита подсветит только новую строку. Что?! Почему
>>> a = 10
>>> b = 300
>>> a is 10
True
>>> b is 300
False
a
указыввет на свое значение, а b
y нет? x = 10
, то вообще-то получаем ссылку на объект, который уже существует в памяти: Причем это касается любых значений, которые приводятся к целым числам этого диапазона. Можно завести число хоть в двоичном виде, хоть в hex, кеширование все равно будет работать:
>>> c = 1
>>> id(1)
94492411548416
>>> id(c)
94492411548416
Числа вне диапазона - 5, 256 интерпретатор тоже будет пытаться оптимизировать, но только если они находятся в одной строке (или одном файле). В командной строке интерпретатора так не работает:
>>> id(19)
94579033949504
>>> id(0b10011)
94579033949504
>>> id(0o23)
94579033949504
>>> id(0x13)
94579033949504
а так будет:
>>> d = 400
>>> d is 400
False
В общем и целом то, что нужно запомнить -- это что небольшие числа в интерпретаторе хранятся не так, как большие и что с ними следует пользоваться оператором
>>> e = 500; f = 500
>>> e is f
True
==
, а не is
.
items = [‘a’, ‘b’, ‘c’]
i = 0
while i < len(items):
print(items[i])
i += 1
Что с ним не так?items[3]
, заменив <
на <=
;
for item in items:
print(item)
Это решение enumerate()
, которая предоставляет и сам элемент и его индекс:
for i, item in enumerate(items):
print(i)
В общем, если вам в Python цикле нужно делать операции не с индексами, а с самими объектами, то средства языка позволяют писать чистый и менее подверженный ошибкам код. Если индексы все же нужны, выбирайте enumerate()
: пользоваться индексами напрямую — это не pythonic. _, v in my_dict.items():
pass
он обычно теряется. Что это за переменная _
?
>>> a + b
20
>>> _
20
>>> _ * 2
40
В интерпретаторе это позволяет вообще не писать названия переменных и работать быстрее:
>>> list()
[]
>>> _.append(‘чепуха’)
>>> _.append(‘небылица’)
>>> _.append(‘выдумка’)
>>> _
[‘чепуха’, ‘небылица’, ‘выдумка’]
При этом _
-- абсолютно валидное имя. Настолько, что в скриптах его принято использовать для dummy-переменных, значениями которых пользоваться не собираются. Например:
for _ in range(4):
print(“Шутка, повторенная дважды, становится в 4 раза смешнее”)
Или вот так: _, c = ['чепуха', 'небылица', 'выдумка']
print(‘{} {}’.format(a, c))
'чепуха, выдумка'
С другой стороны, если заводите переменную, значение которой вам не нужно, подумайте, стоит ли вообще это делать. В самом первом примере
for _, v in my_dict.items():
pass
можно было с тем же успехом использовать values()
. _
две функции: Нет никаких причин так делать, кроме одной: имя, которое вы хотите дать переменной, конфликтурет с именем встроенной функции или ключевого слова в Python. В PEP8, документе, который закрепляет соглашения по кодстайлу в Python, написано следующее:
my_argument_ = 10
single_trailing_underscore_
: используется по соглашению для избежания конфликтов с ключевыми словами языка, например:Поэтому в этом примере лучше просто написать
Tkinter.Toplevel(master, class_='ClassName')
my_argument
, без подчеркивания. А вот если вам понадобится, например, что-то из id
, class
, del
, ..., то можно добавить _
. Правда, даже в этом случае я сама обычно выбираю более объясняющее имя, например, person_id
, class_name
, delimeter
, чтобы не путать коллег и сделать код более читаемым.
sports ={
'Nikolai':{
'weight':92,
'height':187,
'age':32
},
'Natasha':{
'weight':65,
'height':170,
'age':24
},
'Boris':{
'weight':87,
'height':180,
'age':28
}
}
max(sports, key=lambda k: sports[k]['age'])
Ждем, что при каждом новом вызовы функции список снова будет пустым. На самом же деле:
>>> def foo(data=[]):
... data.append(5)
... return data
Вот это поворот! Причина такого поведения в том, что в Python значения дефолтных аргументов вычисляются только один раз -- при объявлении функции. То есть, после того, как инструкция
>>> foo()
[5]
>>> foo()
[5, 5]
>>> foo()
[5, 5, 5]
def
выполнена, список data
уже создан. При этом пока функция существует, пересоздаваться список больше не будет. Это объясняет и вот такое поведение: Видно, что, когда мы передали другой список в
>>> foo(data=[1, 2, 3])
[1, 2, 3, 5]
>>> foo()
[5, 5, 5]
foo()
, к нему добавилось значение 5. При этом аргумент по умолчанию не изменился. None
: Такое определение создает новый список в локальном неймспейсе. Теперь все чисто😏
>>> def bar(data=None):
... if data is None:
... data = []
... data.append(5)
... return data
На самом деле это поведение можно обратить в свою пользу. Пусть, например, в программе есть функция, которая долго вычисляет результат. Можно кешировать параметры и результат вычисления, и, если функцию вызывают еще раз с теми же парметрами, просто возвращать заранее посчитанный ответ.
>>> bar()
[5]
>>> bar()
[5]
>>> bar(data=[1, 2, 3])
[1, 2, 3, 5]
Сохранение результатов для предотвращения повторных вычислений называется мемоизацией.
def baz(arg1, arg2, _cache={}):
# Если есть в кеше, выходим
if (arg1, arg2) in _cache:
return _cache[(arg1, arg2)]
# Вычисляем результат
result = ...
# Сохраняем в кеш
_cache[(arg1, arg2)] = result
return result
else
в цикле while
:Если выполнить этот цикл, то мы получим:
>>> i = 1
>>> while i < 4:
... print(i)
... i += 1
... else:
... print('Вышли из цикла!')
Здесь блок
1
2
3
Вышли из цикла!
else
выполняется только тогда, когда условие выхода из цикла перестает быть верным. Особенность здесь в том, что если вывалиться из цикла через break
или через исключение, то блок else
выполняться не будет. while
, но и с циклами for
:И так же можно с try-except блоками. На самом деле исключения в Python это не try-except-finally, а try-except-else-finally, ниже пример:
>>> for value in values:
... if value == 4:
... print('Нашли!:)')
... break
... else:
... print('Не нашли:(')
А если задать
>>> num = 0
>>> try:
... result = 1 / num
... except ZeroDivisionError:
... print('Деление на ноль!')
... else:
... print('Конечное число.')
... finally:
... print('Вычисления закончены.')
...
Деление на ноль!
Вычисления закончены.
num = float('Inf')
, то в результате деления мы получим 0 и вывод будет:Блок
Конечное число.
Вычисления закончены.
finally
выполняется в любом случае. А else
можно использовать, если нужно выполниь еще какой-то код в случае отсутствия исключений. Например, это может быть полезно в тестах, когда мы хотим логгировать как в случае падения теста на исключении, так и в случае, если исключений брошено не было. else
отрабатывает в случае <<штатного>> завершения цикла. Еще else
можно использовать в try-except блоке, чтобы выполнить какой-то код только в случае успешного выполнения блока try
. Во всех случаях использование else
позволяет более гибко управлять потоком выполнения 🐍
a = [1, 2, 3, 4]
b = [5, 6, 7, 8]
то по понятным причинам может объединить их быстрее, чем поэлементным перебором. Эта модификация сортировки называется galloping, поскольку в этом режиме алгоритм переносит на новое место не один элемент, а сразу несколько. Досортировки и слияния повторяются до тех пор, пока не достигается полная упорядоченность входного массива.