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 для представления временной сложности сортировки вставкой, мы должны использовать два оператора для лучшего и худшего случаев:

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

Синтаксис

Параметры

Примечания