Pull to refresh

Comments 27

«Mutable» & «Immutable» переводятся как «Изменяемые» и «Не изменяемые» — давайте попробуем следить за чистотой русского языка там, где это не только возможно, но и нужно.
Да, оно там, дальше по тексту, расшифровывается, но почему-бы сразу нормально не написать?
Спасибо за замечание!
Не учел этот момент, так как в основном читаю англоязычные источники и не был уверен в устоявшейся терминологии на русском языке. Тем более, смутило, что однокоренные слова, как «мутация», «мутагенез» и т.п. присутствуют в русском языке.
Сделал правки по тексту статьи, кроме схем, таблиц и комментариев к ним.
В русском языке «мутагенез» это специфический медико-биологический термин. Термин «мутация» более широко принят, но опять-таки, термин медицинский, описывающий более сложное понятие, чем описываемая в тексте возможность изменять содержимое текущего объекта.
Приняв во внимание количество проголосовавших за Ваш комментарий и осознав важность проблемы, переделал также схему и таблицу и расшифровки к ним, чтобы везде стояли корректные русские варианты названий. Остальной текст статьи был исправлен еще днем.
а вот ключи — не изменяемые и уникальные, поэтому, например, мы не можем сделать ключом словаря список, но можем кортеж.

не совсем верно, попробуйте в качестве ключа словаря или элемента множества сделать такой кортеж — (1, [2, 3], 4). Помимо неизменяемости должна быть хэшируемость.
Большое спасибо за замечание, Вы действительно правы — Ваш пример не хешируем, я сейчас подумаю как это лучше сформулировать и внесу уточнения в статью, с указанием Вашей помощи.

В свое оправдание, скажу, что даже официальный глоссарии Python вводит в заблуждение, причем в обеих версиях:
https://docs.python.org/3/glossary.html#term-hashable
https://docs.python.org/2/glossary.html#term-hashable

"All of Python’s immutable built-in objects are hashable<...> Immutable objects include numbers, strings and tuples. "
Тут больше вопрос в том, как берется хэш от коллекций. Вроде как он берется рекурсивно, от каждого элемента коллекции.
Спасибо. Интересно. Вот бы ещё добавить про эффективность [типа О(N)] используемых в каждой коллекции алгоритмов добавления, удаления и т.д. Иногда это важно.
Важный момент, согласен, но, к сожалению, данный вопрос не планируется к рассмотрению в моих статьях, по крайней мере в ближайшем будущем.
Очень жаль. Для меня ценность ваших статей сильно снизилась. Представленная информация и так в каждой книге по питону есть. А вот с эффективностью что-то никто не хочет париться…
С вопросами данного цикла статей мне приходилось непосредственно сталкиваться, большинство ошибок, от которых я предостерегаю, я в свое время совершал сам. Многие нюансы, казалось бы очевидных вопросов, при написании статьи открылись в новой стороны, так что польза такой систематизации информации в одном месте безусловно есть, даже если все это можно найти по-отдельности в учебниках и систематизировать самостоятельно.

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

При этом, мне интересна и эта тема, так как есть интерес к применению в дальнейшем Python в Data Science, но на данный момент эта задача не является для меня первостепенным приоритетом, поэтому и говорю, что в ближайшем будущем на углубление в этом направлении времени у меня точно не хватит.
Спасибо. Я вас понимаю. Ниже приведены ссылки на материалы. Рекомендую добавить эти ссылки в статью.
И уточню маленький нюанс: не высокопроизводительные вычисления, а большие объёмы данных. Попробуйте по 1 млн записей в каждый тип коллекции добавить…
А к вопросу систематизации — можно было бы добавить про особенности коллекций из пакета collections. Там есть интересные вещи, которые не так часто освещаются. Тот же defaultdict, например
Спасибо за предложение!
Да, там есть весьма интересные вещи и эта тема хорошо соответствует тематике данной серии.
Я пока сам не разбирался глубоко с этим модулем, но постараюсь после публикации уже запланированных материалов вернуться к этому вопросу.
Да уже всё сделано по части асимптотик: тыц1, тыц2.

Lists:
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | l[i]         | O(1)         |
Store         | l[i] = 0     | O(1)         |
Length        | len(l)       | O(1)         |
Append        | l.append(5)  | O(1)         |
Pop          | l.pop()      | O(1)         | same as l.pop(-1), popping at end
Clear         | l.clear()    | O(1)         | similar to l = []

Slice         | l[a:b]       | O(b-a)         | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend        | l.extend(...)| O(len(...))   | depends only on len of extension
Construction  | list(...)    | O(len(...))   | depends on length of ...

check ==, !=  | l1 == l2     | O(N)          |
Insert        | l[a:b] = ... | O(N)         |
Delete        | del l[i]     | O(N)         | 
Remove        | l.remove(...)| O(N)         | 
Containment   | x in/not in l| O(N)         | searches list
Copy          | l.copy()     | O(N)         | Same as l[:] which is O(N)
Pop          | l.pop(i)     | O(N)         | O(N-i): l.pop(0):O(N) (see above)
Extreme value | min(l)/max(l)| O(N)         | searches list
Reverse          | l.reverse()  | O(N)         |
Iteration     | for v in l:  | O(N)          |

Sort          | l.sort()     | O(N Log N)    | key/reverse mostly doesn't change
Multiply      | k*l          | O(k N)        | 5*l is O(N): len(l)*l is O(N**2)


Sets:
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Length        | len(s)       | O(1)         |
Add           | s.add(5)     | O(1)         |
Containment   | x in/not in s| O(1)         | compare to list/tuple - O(N)
Remove        | s.remove(5)  | O(1)         | compare to list/tuple - O(N)
Discard       | s.discard(5) | O(1)         | 
Pop           | s.pop(i)     | O(1)         | compare to list - O(N)
Clear         | s.clear()    | O(1)         | similar to s = set()

Construction  | set(...)     | O(len(...))   | depends on length of ...
check ==, !=  | s != t       | O(len(s))     | same as len(t): False in O(1) if
                                                   the lengths are different
<=/<          | s <= t       | O(len(s))     | issubset
>=/>          | s >= t       | O(len(t))     | issuperset s <= t == t >= s
Union         | s | t        | O(len(s)+len(t))
Intersection  | s & t        | O(len(s)+len(t))
Difference    | s - t        | O(len(s)+len(t))
Symmetric Diff| s ^ t        | O(len(s)+len(t))

Iteration     | for v in s:  | O(N)         |
Copy          | s.copy()     | O(N)         |

Sets have many more operations that are O(1) compared with lists and tuples.


Dictionaries: dict and defaultdict
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | d[k]         | O(1)         |
Store         | d[k] = v     | O(1)         |
Length        | len(d)       | O(1)         |
Delete        | del d[k]     | O(1)         |
get/setdefault| d.method     | O(1)         |
Pop           | d.pop(k)     | O(1)         |
Pop item      | d.popitem()  | O(1)         |
Clear         | d.clear()    | O(1)         | similar to s = {} or = dict()
View          | d.keys()     | O(1)         | same for d.values()

Construction  | dict(...)    | O(len(...))   | depends # (key,value) 2-tuples

Iteration     | for k in d:  | O(N)          | all forms: keys, values, items

So, most dict operations are O(1).
Круто! Вот это бы в статью добавить. Хотя бы в виде ссылок.
Согласен, хорошая идея! Добавил ссылки в конце статьи.

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

Спасибо за предложение.
Тема добавления точно будет затронута в следующей статье серии, а также тема конкатенации (объединения) коллекций — уже имеются готовые наброски.
Касательно удаления элементов, там не так много нюансов, изначально эта тема не планировалась, но я подумаю и постараюсь включить и эти моменты в следующую статью.
У вас неточность в первой таблице:
>>> a = {}
>>> a
{}
>>> type(a)
<class 'dict'>
>>> b = {'a', 'b'}
>>> type(b)
<class 'set'>
Там в таблице пустые скобочки { } только в строке словаря, так как они создают пустой словарь.
Для множества указан пример {elm1, elm2} — при перечислении значений через запятую в { } создается множество.
Ну и вариант создания словаря из пар ключ: значение {key: value, } указан.
Более того, подобное замечание есть ниже под таблицей (UPD с благодарностью morff ), там как раз приведен пример практически идентичный Вашему.
> .copy() — метод возвращает неглубокую (не рекурсивную) копию

кому нужна неполная копия? какое-то странное поведение по умолчанию, почему так?
Во-первых, глубокая копия затратнее как по времени выполнения, так и по занимаемой памяти. Иногда — сильно затратнее.
Во-вторых, зря вы думаете, что поверхностная копия никому не нужна. Я легко могу себе представить ситуацию, когда полезно иметь пару списков, которые содержат те же объекты, но один из них — с небольшими вариациями.
Во-первых, какая разница затратнее или нет если только она делает то что нужно?
Во-вторых, не умею читать ваши представления, может поделитесь в текстовом виде?
Ну, например так:

Есть список объектов. Нужно эти объекты как-то обработать — все из списка, но в каком-то определённом заранее неизвестном порядке. Причём оригинальный список должен сохраниться, из него удалять объекты нельзя.

Вполне разумное решение — создать поверхностную копию списка и работать с ней, удаляя обработанные объекты из неё.

Это первое, что пришло в голову.
Вот для таких извращённых случаев должен быть метод вроде fastcopy, а copy должен делать полную копию и не требовать нагугливать deepcopy всякие
Ну не знаю, по мне так естественным поведением для copy является именно то, что сочли таким авторы языка.

Коллекции хранят не содержимое объектов, а ссылки на них. Соответственно, копироваться должно именно то, что лежит в коллекции.
А вот рекурсивный обход с копированием внутренней структуры каждого вложенного элемента — это сложная и отдельная процедура, которая не является просто копированием.
Sign up to leave a comment.

Articles