Почему ваши петли такие медленные

Вступление

В удивительном, а иногда и устрашающем мире программирования программисты используют множество инструментов для решения проблем. Один из таких инструментов, который часто используется для структур данных, - это цикл. Цикл, конечно, может относиться к циклу while, for и неохотно; рекурсивный цикл. Проблема с циклами в том, что они могут быть серьезным препятствием для производительности, однако они являются неотъемлемой частью многих операций программирования.

Независимо от того, что вы программируете, наверняка будет несколько разных способов сделать это. Хотя конечная цель может быть сохранена, почти наверняка будет другой путь, чтобы ее достичь. Это также означает, что разные подходы могут занять гораздо больше времени или памяти, чтобы получить одно и то же решение. Это обе вещи, о которых программист должен знать, и хотя может быть трудно достичь идеальной функции с высокой производительностью, которая использует наименьший возможный объем памяти, есть несколько способов, которыми можно улучшить их циклы на этом пути, чтобы чтобы улучшить эту производительность. Кроме того, в компьютерных науках есть формульное свойство, которое мы можем использовать для оценки эффективности функции, и оно называется

Обозначение Big O.

Обозначение Big O

Так что же такое нотация Big O и как мы можем использовать ее для улучшения наших навыков программирования? Нотация Big O - это математическая форма, описывающая поведение функции при численном увеличении аргумента. Например, скажем, у нас есть базовая функция суммирования в Python:

def summation(n):
    total = 0
    for number in n:
        total += number
    return(total)

Чем длиннее список «n», тем больше раз эта функция будет нуждаться в цикле и выполнении операций сложения и утверждения. Как вы понимаете, очень вероятно, что добавление новых итераций в этот список связано с очень линейным уравнением. По мере того, как диапазон n увеличивается, время компиляции увеличивается. Я решил перенести это в Jupyter, чтобы лучше визуализировать это, поэтому, если вы хотите просмотреть записную книжку, которую я использовал, вы можете здесь:

Это функция, которую я использовал для проверки различного количества чисел, передаваемых через эту функцию:

def test_speed(numbers):
    results = {}
    for number in numbers:
        start = time.time()
        total = summation(list(range(1, number)))
        end = time.time()
        results[number] = end - start
    return(results)

Функция использует модуль времени, чтобы получить количество времени, которое занимает каждое суммирование. Он передает список диапазона между единицей и числом, что означает, что мы сможем определить, сколько значений проходит через цикл, добавляя новые числа в наш список чисел. Давайте попробуем!

measurements = test_speed([1000, 10000, 100000, 10000000])
print(measurements)

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

speeds = measurements.values()
ns = measurements.keys()

Теперь я создам фрейм данных, используя эти данные:

import pandas as pd
df = pd.DataFrame({"Speed": speeds, "Count": ns})

И, наконец, я построю его с помощью Plot.ly:

import plotly.express as px
fig = px.line(df, x="Count", y="Speed", title='Summation Over Time')
fig.show()

Наша функция на самом деле является линейно сложной, по крайней мере, с точки зрения времени обработки. В нотации Big O это называется O (n). O представляет наши эксплуатационные расходы, в этом примере, поскольку наша нотация Big O - O (n), мы могли бы получить наши эксплуатационные расходы для данной суммы, вычитая два числа, которые были пропущены через нашу функцию, которые представляют собой один числовой шаг. подальше друг от друга.

Есть также некоторые другие популярные нотации Big O, которые очень распространены в компьютерном программировании. O (1) - это базовая линия, что означает, что количество входов не имеет значения. Это базовый уровень всякий раз, когда вы создаете какую-либо функцию, как если бы, например, не было цикла, и, возможно, одна операция, вполне вероятно, что O (1) будет тем, с чем вы имеете дело. Другой - O (log n), где немного больше налога, но с большим количеством итераций плато цикла. Это популярно в методах цикла, которые требуют частой инициализации, но не так много операций за цикл.

Следующее обозначение O - это O (n log n), O (n log n) также обычно линейно, но обычно имеет гораздо более крутой наклон, чем O (n). O (n²) - экспоненциальный рост, то есть каждая итерация будет стоить в квадрате операционных затрат предыдущих n. Тогда есть O (2 ^ n), что еще хуже, и, как правило, является экспоненциальным ростом, только с гораздо более крутым наклоном, поскольку показатель степени теперь равен количеству итераций. Наконец, есть O (n!). Это факториал числа n. Особенность факториалов в том, что они очень быстро выходят из-под контроля. Хотя вычисление факториала пяти может занять секунды, на вычисление факториала действительно большого числа могут потребоваться годы. Это еще более верно для типичной рекурсивной реализации факториалов в компьютерном программировании. Как вы могли догадаться, это означает, что время вычисления резко увеличивается с увеличением n. Я нашел отличную визуализацию в Интернете, но я не могу добавить ее в эту работу без нарушения прав, поэтому вместо этого я предоставлю ссылку для просмотра здесь. Визуализация отлично показывает, как выглядит каждая нотация, и действительно подчеркивает различия между ними.

Заключение

Нотация Big O - это основной продукт современных вычислений, поскольку он довольно часто используется для анализа эффективности функций. Что можно сделать с информацией, которую предоставляет Big O? Что ж, есть очевидный недостаток у некоторых функций, которые попадают в нотацию с резким увеличением, когда дело доходит до работы с большим количеством значений. Конечно, есть функции, которые должны вести себя таким образом и принимают гораздо меньше значений, чем другие, поэтому намерение использовать с функцией и то, для чего она на самом деле предназначена, во многом влияет на то, действительно ли Big O действительно важен. часть вашей функции для визуализации.

При этом нотация Big O, безусловно, является ценным инструментом. Его можно использовать для анализа того, насколько критичным может быть состояние функции, а также обычно применяется для проверки масштабируемости функции. Масштабируемость важна для большого бизнеса, и функции, которые по своей сути немасштабируемые, могут быть проблематичными, когда они доводятся до более крупного масштаба, поэтому изучение таких показателей производительности, безусловно, полезно для того, чтобы узнать больше о том, насколько хорошо приложение конкретной функции к данной проблеме. Спасибо за чтение!