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 называется функцией порядка.

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)

х в с: O (n)

мин (с), макс (с): O (n)

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

Deque операции

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)

Дополнение: O (1)

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

Расширить: O (k)

Extendleft: O (k)

Pop: O (1)

Поплефт: O (1)

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

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

Операции над множествами

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

х в с: 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 - это максимум (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) или хэш-таблицу Python O (1).

Для более перейдите по ссылке ниже ... Python Speed Up

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

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

Наихудшая временная сложность сортировки вставкой Θ (n ^ 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}. Давайте рассмотрим тот же пример сортировки вставок здесь. Временная сложность сортировки вставкой может быть записана как Ω (n), но это не очень полезная информация о сортировке вставкой, так как нас обычно интересует наихудший случай, а иногда и средний случай.