Python Language
Скорость программы Python

нотация

Основная идея

Нотация, используемая при описании скорости вашей программы Python, называется нотой Big-O. Допустим, у вас есть функция:

def list_check(to_check, the_list):
    for item in the_list:
        if to_check == item:
          return True
    return False

Это простая функция для проверки того, находится ли элемент в списке. Чтобы описать сложность этой функции, вы скажете O (n). Это означает «порядок n», поскольку функция O известна как функция Order.

O (n) - обычно n - количество элементов в контейнере

O (k) - обычно k - значение параметра или количество элементов в параметре

Список операций

Операции: средний случай (предполагает, что параметры генерируются случайным образом)

Добавить: O (1)

Копировать: O (n)

Del slice: O (n)

Удалить элемент: O (n)

Вставка: O (n)

Получить элемент: O (1)

Установить элемент: O (1)

Итерация: O (n)

Получить срез: O (k)

Установить срез: O (n + k)

Расширение: O (k)

Сортировка: O (n log n)

Умножить: O (nk)

x в s: O (n)

min (s), max (s): O (n)

Получить длину: O (1)

Операции Deque

Дека - это двойная очередь.

class Deque:
def __init__(self):
    self.items = []

def isEmpty(self):
    return self.items == []

def addFront(self, item):
    self.items.append(item)

def addRear(self, item):
    self.items.insert(0,item)

def removeFront(self):
    return self.items.pop()

def removeRear(self):
    return self.items.pop(0)

def size(self):
    return len(self.items)

Операции: средний случай (предполагает, что параметры генерируются случайным образом)

Добавить: O (1)

Appendleft: O (1)

Копировать: O (n)

Расширение: O (k)

Extendleft: O (k)

Поп: O (1)

Popleft: O (1)

Удалить: O (n)

Повернуть: O (k)

Установить операции

Операция: средний случай (предполагает произвольные параметры): худший случай

x в s: O (1)

Разность s - t: O (len (s))

Пересечение s & t: O (мин (len (s), len (t))): O (len (s) * len (t)

Множественное пересечение s1 & s2 & s3 & ... & sn:: (n-1) * O (l) где l max (len (s1), ..., len (sn))

s.difference_update (t): O (len (t)): O (len (t) * len (s))

s.symetric_difference_update (t): O (len (t))

Симметрическая разность s ^ t: O (len (s)): O (len (s) * len (t))

Union s | t: O (len (s) + len (t))

Алгоритмические обозначения ...

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

Помните правило 80/20 : во многих полях вы можете получить 80% результата с 20% усилий (также называемое правилом 90/10 - это зависит от того, с кем вы говорите). Всякий раз, когда вы собираетесь оптимизировать код, используйте профилирование, чтобы узнать, где это 80% времени выполнения, поэтому вы знаете, где сосредоточить свои усилия.

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

Используйте правильные алгоритмы и структуры данных: не используйте алгоритм сортировки пузырьков O (n2), чтобы сортировать тысячу элементов, когда есть доступная операционная система O (n log n). Точно так же не храните тысячу элементов в массиве, который требует поиска O (n), если вы можете использовать двоичное дерево O (log n) или хэш-таблицу O (1) Python.

Для более подробной информации см. Ссылку ниже ... Python Speed ​​Up

Следующие 3 асимптотические обозначения в основном используются для представления временной сложности алгоритмов.

1. Обозначение : тета-нотация ограничивает функции сверху и снизу, поэтому она определяет точное асимптотическое поведение. Простым способом получить обозначение Тэта выражения является падение младших членов и игнорирование ведущих констант. Например, рассмотрим следующее выражение. 3n3 + 6n2 + 6000 = Θ (n3) Отбрасывание членов младшего порядка всегда отлично, потому что всегда будет n0, после которого Θ (n3) имеет более высокие значения, чем Θn2), независимо от используемых констант. Для данной функции g (n) обозначим Θ (g (n)) следующее множество функций. Θ (g (n)) = {f (n): существуют положительные константы c1, c2 и n0 такие, что 0 <= c1 g (n) <= f (n) <= c2 g (n) для всех n> = n0} Вышеприведенное определение означает, что если f (n) является тетой g (n), то значение f (n) всегда находится между c1 g (n) и c2 g (n) при больших значениях n (n> = n0). Определение theta также требует, чтобы f (n) была неотрицательной при значениях n, больших n0.

2. Big O Notation : нота Big O определяет верхнюю границу алгоритма, она ограничивает функцию только сверху. Например, рассмотрим случай сортировки вставки. В худшем случае требуется линейное время в лучшем случае и квадратичное время. Мы можем с уверенностью сказать, что временная сложность сортировки Insertion равна O (n ^ 2). Заметим, что O (n ^ 2) также охватывает линейное время. Если мы используем обозначение ation для представления временной сложности сортировки Insertion, мы должны использовать два утверждения для лучших и худших случаев:

1. Худшая временная сложность Сортировка Вставки - Θ (n ^ 2).
2. Наилучшая временная сложность Сортировка вставки - Θ (n).

Обозначение Big O полезно, когда у нас есть только верхняя граница по временной сложности алгоритма. Много раз мы легко находим верхнюю границу, просто просматривая алгоритм. O (g (n)) = {f (n): существуют положительные константы c и n0 такие, что 0 <= f (n) <= cg (n) для всех n> = n0}

3. Ω Обозначение : так же, как примечание Big O обеспечивает асимптотическую верхнюю границу функции, обозначение Ω дает асимптотическую нижнюю границу. Ω Обозначение <может быть полезно, когда мы имеем нижнюю границу по временной сложности алгоритма. Как обсуждалось в предыдущем сообщении, наилучшая производительность алгоритма обычно не полезна, нотация Omega является наименее используемой нотацией среди всех трех. Для данной функции g (n) обозначим через Ω (g (n)) множество функций. Ω (g (n)) = {f (n): существуют положительные константы c и n0 такие, что 0 <= cg (n) <= f (n) для всех n> = n0}. Давайте рассмотрим тот же пример сортировки Insertion. Сложность времени сортировки вставки может быть записана как Ω (n), но это не очень полезная информация о сортировке вставки, поскольку нас обычно интересуют наихудший случай, а иногда и средний случай.