test message

Чем мутабельные объекты отличаются от иммутабельных?

В python объекты бывают мутабельные и иммутабельные. Значние иммутабельного объектра нельзя изменить после того, как он был создан, а значение мутабельного можно.

Рассмотрим на примере. В Python есть встроенная функция 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  словарь                   ☺️

Количество встроенных иммутабельных типов в python больше, но если вы захотите создать свой класс, он будет мутабельным.

Важно отличать мутабельность от иммутабельности, так как некоторые типы данных, например, dict или set, реализованы как хэш-таблицы. Когда вы добавляете элемент в множество, интерпретатор берет хэш от этого элемента и размещает значение по адресу, который совпадает с хэшом. Если мы попытаемся положить список в множество, то получим TypeError, потому что хэш бы изменился, когда изменился бы один из элементов списка:

TypeError: unhashable type: 'list'

Поэтому мутабельные объекты, такие как словари или списки, не могут быть ключами в словаре или элементами множества. А вот строки или числа могут. И это на самом деле очень естественно🐍

#перед_собесом #основы #типы_данных #мутабельность #иммутабельность

Какова сложность операции добавления элемента в список?

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

typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;

Здесь ob_item -- это непрерывный массив указателей на элементы списка, а allocated содержит длину массива. Вот и все, что нужно знать, чтобы отвечать на вопросы о сложности операций со списками.

Во-первых, отсюда сразу видно, что получить длину массива можно очень быстро, за O(1), потому что не нужно пересчитывать все элементы.

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)

В общем, чтобы отвечать на вопросы о сложности операций со списками, нужно понимать, как они устроены на низком уровне. Самые дорогие операции -- те, которые требуют обхода части или всего списка, например, поиск значения в списке, конкатенация, слайсинг, удаление или добавление элементов в начало списка. Самые экономные операции -- получение длины списка, операции с элементами в конце списка и со значениями по известному индексу.

В общем случае, сложность добавления элемента в список зависит от того, в середину массива мы добавляем элемент или в конец. Добавить элемент в начало или середину списка это O(n), но операция append() требует только O(1)🐍

#перед_собесом #low_level #типы_данных #списки #алгоритмы #сложность #hardcore

Что такое временная сложность алгоритма?

Часть 1.

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

Сведение умножения к сумме -- самый простой, наивный алгоритм умножения. А теперь я возьму мой рабочий ноут и попробую перемножить этим способом какие-нибудь большие числа, например, 4 * 10000000000:

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)

Но мы обнаружим, что скорость зависит от производительности машины, от ее архитектуры и загруженности в момент выполнения программы. Поэтому физическое время никак не поможет нам оценить эффективность алгоритма.

Чтобы уйти от физических свойств вычислителя, используют понятие сложности. Асимптотическая сложность алгоритма -- это то, как изменяется время исполнения в зависимости от объема входных данных. В этом определении намеренно не учитывается то, на каком устройте выполняется алгоритм: это может быть компьютер, калькулятор или даже человек. Такой абстрактный вычислитель называют машиной Тьюринга.

При этом разделяют сложность алгоритма в худшем и лучшем случае. Представьте, что мы хотим проверить, есть ли в списке число 42. Мы проверяем первый элемент на равенство 42, второй, третий… В лучшем случае первый элемент окажется искомым. В худшем -- последний. Поэтому обычно рассматривают сложность алгоритма в наилучшем, наихудшем случае, и в среднем. Как правило, пессимистическая оценка самая интересная из всех, потому что позволяет планировать объем ресурсов.

Временную сложность алгоритма в худшем случае выражают с использованием нотации «O» большое. В этом случае из рассмотрения исключают члены меньшего порядка и говорят об изменении используемых ресурсов при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения работы, для всех входов длины n не превосходит 5n^3 + 3n, то асимптотическая временная сложность равна O(n^3). 🤓

#сложность #теория_сложности #перед_собесом #часть

Что такое временная сложность алгоритма?

Часть 2.

Рассмотрим несколько примеров.

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

O(n)
Алгоритм, в котором мы идём по списку, чтобы узнать, есть ли в нем значение 42, в худшем случае требует O(n) операций, где n -- длина списка. Такую же сложность имеет сравнение строк, потому что по сути оно тоже требуют обхода всей строки.

O(log n)
Проверить, есть ли значение 42 в списке, можно быстрее, чем за O(n), если список отсортирован. Тогда можно проверить на равенство элемент из середины списка. Если он равен 42, то останавливаемся. Если больше -- значит, слева можно не искать, там значения только меньше. Будем продолжать проверку, выбирая каждый раз элемент из середины оставшегося отрезка. Этот алгоритм называют бинарным поиском и он имеет логарифмическую сложность, потому что количество вариантов уменьшается каждый раз на 2, как функция, обратная степенной (она же логарифм).

O(n log n)
Можно показать, что большинство алгоритмов сортировки имеют сложность n log(n). За время n log(n) работают сортировка слиянием, кучей, и быстрая сортировка. Еще есть теорема, которая говорит, что если сортировка основана на сравнении элементов, то быстрее, чем за n log(n) отсортировать элементы не получится.

O(n^2)
За время n^2 работает обход двумерного массива, это можно представить себе как обход таблицы n * n. И ещё за это же время работают некоторые не очень эффективные по времени алгоритмы сортировки, например, сортировка пузырьком

Для разработчика важно иметь интуицию насчет временной сложности алгоритмов, потому что за счет неэффективности вычислений можно загубить производительность самого мощного железа, как это случилось, когда калькулятор побил мой мощный ноутбук. Поэтому этой науке уделяется большое внимание в разработке. 95%, что на собеседовании вам предложат алгоритмическую задачу и попросят оценить время выполнения вашего решения.

Если вы хотите углубиться в теорию алгоритмов, то я советую специализацию Алгоритмы и структуры данных на Курсере. Теория здесь изложена доступно и в курсе есть задачи, чтобы набить руку. А еще есть Стенфордский учебник по теории сложности, он написан замечательным языком и в нем прекрасные примеры. 🎓

#сложность #теория_сложности #перед_собесом #часть

Как писать резюме

Если вы хотите продать на рынке труда свое время и навыки, то резюме -- это не только рассказ о том, как вы дошли до такой жизни, но и ваш продающий текст. Я пишу резюме, чтобы показать читателю, что могу быть ему полезна и убедить пригласить меня на собеседование. Других задач у резюме нет.

Сделайте так, чтобы каждая строчка резюме работала на две эти цели и уберите из текста все, что вас к ним не приближает. Например, мое первое образование экономическое и если я иду на backend разработку, у меня нет причин о нем говорить. Но для финтех компаний у меня есть вторая версия:) То же с водительскими правами: в hh есть это поле, но его не обязательно заполнять, если не идете разрабатывать беспилотный автомобиль. Работа грузчиком или кассиром тоже не имеет отношения к программированию. Не мешайте читателю понять, стоит ли с вами поговорить лично.

Каждая запись в моем резюме отвечает на вопросы, что я сделала на прошлой работе (именно <<сделала>>, а не <<делала>>) и чему при этом научилась. Работали на проекте -- опишите этот опыт. В своей первой компании я задержалась на 2,5 года, но там можно было менять проекты или работать над несколькими в параллель. Эти опыты разные и о каждом из них я рассказываю отдельно.

Говорят, что резюме не читают больше двух минут. Иногда люди впервые знакомились с моим резюме прямо на собеседовании:) Поэтому лучше не переваливайте за вторую печатную страницу, человек может туда просто не добраться. Если вы фрилансили и делали каждый проект по несколько недель, то лучше сгруппируйте эти опыты в запись <<разное>> и опишите в общих чертах, какие навыки за это время получили. Все-таки резюме это выжимка.

Если не уверены, что убрать, а что оставить, исследуйте! Закиньте в десяток релевантных мест одну версию документа, а в остальные другую. Вряд ли рекрутеры будут очень счастливы, но отклики покажут, какая версия работает в вашем случае. Кстати, я записываю в табличку, куда я уже отсылала резюме, а куда нет, чтобы не забывать, с кем на какой стадии находятся трудовые отношения.

Не бойтесь белых пятен в резюме. Все начинают в разное время, пробуют себя в новом, заводят детей, поэтому перерывы в карьере -- частая история. Они никак не повлияют на то, как вы будете вести себя на новом месте. У меня за все время так и не спросили, где потерялись четыре года эконома.

Клеить ли фотографию в резюме? Со стороны трудовой этики, ваша внешность не должна интересовать работодателя. С другой стороны, если на резюме есть ваше лицо, то за текстом читателю легче увидеть человека, поэтому выбор за вами.

В конце резюме люди часто пишут о своих коммуникационных навыках и умении работать в команде. Это штамп. Если хотите рассказать о себе, лучше напишите, что вы гордитесь своим ребенком, ходите в горы или играете на гитаре. Это сделает резюме более человечным, чем безликое <<умение работать в команде>>. Или дайте в этом поле ссылку на свой гитхаб, публичные выступления или статьи, если они есть. Но если вы все же решили эти строчки оставить, подготовьтесь к вопросам типа <<расскажите о ситуации, в которой вы проявили коммуникационные навыки>>.

И еще об оформлении: в нашей культуре люди читают сверху вниз и слева направо. Можно организовать резюме в две колонки, можно в одну. Запрограммируйте опыт человека, который будет идти глазами по тексту. Что он увидит в первую очередь? Что потом? К каким выводам он скорее всего придет? Если не уверены, как верстать лучше, верстайте проще.

В общем, резюме это ваша визитка, первое, что о вас узнает работодатель. Пишите честно и по делу, не загромождайте его деталями и не сокращайте слишком. Если сомневаетесь, исследуйте. И спланируйте впечатление, которое хотите произвести на читателя: цель резюме это сделать так, чтобы наниматель захотел поговорить с вами лично.

#резюме #ищем_работу #soft_skillz #начинающим

Чем == отличается от is?

== проверяет, одинаковые ли значения у переменных.
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. 🐍

#основы #identity_vs_equality #перед_собесом #типы_данных