Комментарии 24
Дело в том, что объекты в Python делятся на те, что передаются по ссылке — list, set, dict, и те, что передаются по значению — int, float, str, tuple.
Да просто вторые - иммутабельные, отсюда всё и вытекает.
мне кажется, что Вы путаете подсчëт числа операций с асимптотическим анализом
Именно это и показывает функция сложности алгоритма O(N) — сколько элементов нужно обработать, столько операций и будет проделано.
К сожалению нет, O(N) показывает верхнюю границу ограничения функции, иначе говоря сложность алгоритма в наихудшем случае.
Если функция не собирается менять коллекцию которую ей передают на вход, то имеет смысл использовать соответствующую аннотацию типа(Sequence вместо list/tuple, Mapping вместо dict, AbstractSet вместо set)
def process_sequence(items: Sequence[...] = ()): # сюда можно передать как list/tuple, так и любую кастомную реализацию Sequence
...
def process_mapping(items: Mapping[..., ...] = {}): # так как мы не планируем менять входные данные, то изменяемый dict как значение по умолчанию не навредит
...
Если нужен пустой список по умолчанию, следует писать так:
def func3(val: int, l: Optional[list] = None): if not l: l = [] l.append(val) print(l)В Python действительно часто наиболее типичным значением по умолчанию является None - объект с неопределенным значением. Но, иногда None является допустимым значением, а иногда требуется определить случай “значение по умолчанию не задано”, либо, как в Вашем примере, когда аргумент l должны иметь значение в виде пустого списка или объявлять пустой список значением по умолчанию. В таком случае использование объекта None не может быть абсолютно допустимым значением. C этой точки зрения, типизации кода приведенного выше, представляется не очень хорошей практикой.
IMHO: Примером хорошей практики типизации случая, когда аргумент должен иметь значение в виде пустого списка или объявлять пустой список значением по умолчанию, может служить использование паттерна Sentinel Value, как в коде приведенном ниже.
from typing import Any
sentinel: Any = object()
def func3(val: int, l: list[int] = sentinel):
...Либо, вот так:
from unittest.mock import sentinel
NotSet = sentinel.NotSet
def func3(val: int, l: list[int] = NotSet):
...
кажется самый быстрый вариант
line = "".join(["i"] * 10_000)
Добрый вечер. А операция с join не дает дополнительной сложности алгоритму? А заполнение массива [None] x N?
А как Вы измеряете время?
У меня между.
line = ""
for i in range(10_000):
line += "i"
и
word = []
for i in range(10_000):
word.append("i")
line = "".join(word)
разница 10%, а не в 2 раза.
Примечание: ассемблер настолько близок к машинному коду, что фактически одному оператору ассемблера соответствует одна машинная инструкция (1:1). Таким образом, можно довольно точно оценить фактическую сложность алгоритма.
Это каким таким образом? Сложность как раз никак не связана с количеством написанных инструкций.
А с чем же связана?
Computational complexity:
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements.
В приведенном отрывке видимо имеются в виду реально выполненные во времени операции, хотя на мой вкус написано коряво. Вы же утверждаете, что сложность можно оценить буквально сосчитав количество операций на языке ассемблера (то есть в коде программы).
На n входных параметров у алгоритма n ассемблерных операций, у другого алгоритма на n входных параметров n*n ассемблерных операций, т.е. можно увидеть фактическую сложность алгоритма, если считать, что ассемблерная команда - это элементарная операция. Вы правильно написали: "Сложность как раз никак не связана с количеством написанных инструкций", - я же не утверждаю, что сложность как-то зависит от количества написанных строчек кода.
Кроме того, эта операция выполняется ещё и в цикле, то есть итоговая сложность этого алгоритма будет равна O(N*N).
Ох. Вы хоть проверяли?
In [1]: %%time
...: line = ""
...: for i in range(10_000):
...: line += "i"
Wall time: 1.68 ms
In [2]: %%time
...: line = ""
...: for i in range(100_000):
...: line += "i"
Wall time: 17.1 msКоличество увеличилось в 10 раз, время увеличилось в 10 раз. Какая это сложность?
Если кому-то интересно, в CPython есть оптимизация, что если у строки счетчик ссылок равен 1, то строка считается безопасной для изменения на месте и копирование не происходит на каждой итерации (для этого для строки изначально аллоцируется немного больше памяти, чтобы было куда её приращивать). Чтобы сломать этот механизм нужно сделать вторую ссылку на изменяемую строку:
In [3]: %%time
...: line = ""
...: for i in range(10_000):
...: line1 = line
...: line += "i"
Wall time: 3.49 ms
In [4]: %%time
...: line = ""
...: for i in range(100_000):
...: line1 = line
...: line += "i"
Wall time: 177 msТеперь время увеличивается в 50 раз, что ближе к O(n*n).
Привет!
У меня получились другие порядки времени, может ещё кто-нибудь проверить?
10_000 - 4.09 ms
100_000 - 285 ms
пруфы
Интересно, от чего это зависит, от процессора и/или версии Python?
CPU: Xeon E5-2650 v2
Python: 3.12.2
Понимаю, что зря, но текст вызывает сочувствие по отношению к Сберу...
Сложность алгоритмов и типичные ошибки в Python