Выберите наиболее эффективный алгоритм обработки ваших данных, исходя из вашей конкретной ситуации.
Нам, программистам, часто приходится создавать прототипы, прежде чем начинать сложный проект. Во время этого процесса мы можем написать не самый эффективный код, и это нормально: важнее достичь рабочего состояния в кратчайшие сроки. Однако неизбежно приходит время приступить к кодированию развертываемой реализации идеи проекта. Это означает, что технические долги, которые, возможно, остались позади, теперь должны быть решены.
Более того, если вы специалист по данным, вы часто работаете с большими объемами информации одновременно. Поскольку обработка большого количества данных является ресурсоемкой и трудоемкой операцией, очень важно найти наиболее эффективный подход к проблеме. В этой статье я познакомлю вас с большой нотацией О и ее приложениями.
Перед выбором алгоритма
Учитывая проблему, существует бесчисленное множество возможных способов ее решения. Хотя на самом деле хороших очень мало. Как выбрать между алгоритмом А и алгоритмом Б? Сначала нужно проанализировать проблему.
- Ваш код должен запускаться несколько раз в секунду?
- Насколько вы планируете масштабировать свою систему?
- С каким типом данных вы будете работать?
Если ваша программа снова и снова вызывает одни и те же функции, вам обязательно нужно убедиться, что они не станут узким местом для всей системы. В этом случае даже небольшое увеличение скорости может иметь значение. Например, предположим, что вы написали функцию check_collisions() для своего физического движка, и ее выполнение занимает 20 миллисекунд. Вы можете рассчитать только около 50 физических кадров в секунду. Представьте теперь, что вам удалось сэкономить 3 миллисекунды времени выполнения, а это уже 59 кадров в секунду.
Масштабируемость — еще один важный фактор, который следует учитывать. Если вашему приложению приходится обрабатывать все большее количество данных, вам лучше выбрать алгоритм, способный обрабатывать их за разумное время и не требующий для работы чрезмерного объема памяти.
Говоря о данных, используете ли вы подходящие типы и структуры для своей конкретной задачи? Вы можете сэкономить большое количество оперативной памяти, просто заранее зная данные, с которыми имеете дело. Например, если вы храните возраст человека, вам не нужно использовать 4-байтовое целое число со знаком. Лучше использовать только беззнаковый байт, так как возраст никогда не бывает отрицательным и не превышает 255 лет (максимальное число, которое может храниться в одном байте).
Итак, как вы сравниваете различные алгоритмы с точки зрения производительности? Здесь пригодится нотация большого O.
Что такое нотация большого O?
Из Википедии нотация big O — это математическая нотация, описывающая предельное поведение функции, когда аргумент стремится к определенному значению или к бесконечности. В компьютерных науках нотация большого O используется для классификации алгоритмов в зависимости от того, как растут их требования к времени выполнения или пространству по мере увеличения размера входных данных. Другими словами, он измеряет временную или пространственную сложность функции. Это означает, что мы можем заранее знать, насколько хорошо алгоритм будет работать в конкретной ситуации.
Прежде чем приступить к коду, вот список простых правил, которым необходимо следовать при расчете временной или пространственной сложности алгоритма:
- Разделите свой алгоритм на отдельные операции или функции.
- Рассчитайте сложность каждой операции.
- Сложите получившиеся большие O.
- Удалите все константы и члены более низкого порядка. Оставьте только член высшего порядка (самый быстрорастущий), который будет большим O вашего алгоритма.
Чтобы было понятнее, давайте рассмотрим несколько конкретных примеров. Для примеров кода я буду использовать Python, так как у него простой синтаксис, похожий на английский, который может понять каждый. Кроме того, я собираюсь сосредоточиться на временной сложности, а не на пространственной сложности, чтобы статья была более краткой. В любом случае, действуют те же самые правила, поэтому мне показалось несколько излишним рассказывать об этом подробно.
Постоянная временная сложность
Начнем с простого случая в большой нотации O, постоянной временной сложности. Взгляните на этот код:
| input_number = 59 | |
| result = input_number * 2 | |
| print(f'The result is {result}') |
Время, необходимое для завершения этого расчета, не зависит от размера входных данных. Если бы число было равно 2, 60, 100 или 1000, оно не увеличило бы или не уменьшило бы, по крайней мере значительно, время выполнения. Он классифицируется с использованием большой нотации O как O(1), что означает, что он имеет постоянную временную сложность.
| input_number = 59 | |
| result = input_number * 2 | |
| result += input_number * 2 | |
| result += input_number * 2 | |
| result += input_number * 2 | |
| result += input_number * 2 | |
| result += input_number * 2 | |
| print(f'The result is {result}') |
То же самое относится и к этому фрагменту кода. Изменение input_number не повлияет на производительность алгоритма. Сумма всех операций составляет O(1+1+1+1+1+1) или O(6), но может быть приблизительно равно O(1), поскольку 6 — константа. Конечно, его выполнение занимает больше времени, чем в предыдущем примере, но большой O не измеряет точное время, необходимое для выполнения определенной задачи. Big O измеряет изменение производительности алгоритма по отношению к растущему размеру входных данных.
Математические операции, присваивания, логические операторы и вызовы функций приближаются к O(1), если их реализации также не зависят от размера входных данных. Вот список общих операций, которые считаются временными константами:
- Арифметические операции:
a + b, a — b, a * b, a++ ... - Назначения переменных:
a = 2, a += 3, a -= 4 ... - Индексация массива:
a[0], a[i] ..., гдеa— массив, аi— целое число. - Вызовы функций:
foo(), bar(arg) ...до тех пор, пока время их выполнения не сильно зависит от размера ввода. - Логические утверждения:
a && b, a and b, !a, not a, a || b, a or b ... - Доступ участника:
a.member, a.foo() ... - Побитовые операции:
a << b, a | b, a & b, a >> b ...
Индексация хеш-таблицы также в среднем оценивается O(1), как и массивы. Тем не менее, в очень редких случаях они могут достигать O(n).
Сложность времени итерации
Предположим, вам нужно выполнить итерацию по каждому элементу массива, например, чтобы подсчитать количество вхождений определенного значения.
| array = ['eggs', 'potatoes', 'milk', 'eggs', 'pasta', 'tomatoes', 'eggs'] | |
| counter = 0 | |
| for element in array: | |
| if element == 'eggs': | |
| counter += 1 | |
| print(f'Occurrences: {counter}') |
Время выполнения задачи зависит от количества n элементов массива, а именно прямо пропорционально. Временная сложность этого алгоритма может быть классифицирована как O(n), что означает, что при увеличении n время выполнения увеличивается линейно.
Мы можем игнорировать оператор if внутри цикла for, поскольку его временная сложность O(1) не сильно зависит от размера входных данных. Обратите внимание, что его производительность зависит от длины сравниваемых строк, но она не так важна, как длина array, поэтому ее можно игнорировать. Помните, что большое O дает приблизительное представление о поведении алгоритма, поскольку размер его входных данных стремится к бесконечности, а не о точных измерениях.
Постоянно вложенная итерация, экспоненциальная временная сложность
Скажем, вам нужно перебрать массив несколько раз, например, чтобы вычислить все возможные комбинации паролей длиной в два символа, используя только цифры от 0 до 9.
| characters = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] | |
| combinations = [] | |
| for char1 in characters: | |
| for char2 in characters: | |
| combinations.append(char1 + char2) | |
| print(f'Possible combinations: {combinations}') |
Очевидно, что время выполнения этого алгоритма зависит от количества возможных символов. А именно, он генерирует n² комбинаций, где n — количество возможных символов. Если бы вы добавили еще один символ, программе пришлось бы перебрать массив еще n раз. Временная сложность для этого подхода составляет O(n²).
Если бы вы добавили больше for циклов, чтобы увеличить длину пароля, временная сложность была бы O(nᶩ), где n — это количество for циклов, а l — это количество циклов. количество доступных символов. Например, три цикла оценивают O(n³), четыре цикла оценивают O(n⁴) и так далее.
Оператор combinations.append(char1 + char2) обычно можно приблизить к временной сложности O(1), несмотря на то, что на время его выполнения также может влиять размер входных данных, в зависимости от реализация функции. Говоря о списках Python, на самом деле это динамические массивы, поэтому их размер должен быть изменен по мере их роста. В любом случае, эта тема выходит за рамки данной статьи, поэтому я не буду на ней сильно заострять внимание.
Итерация по двум массивам, линейная временная сложность
Представьте, что теперь вам нужно перебрать два массива, чтобы найти, сколько у них общих элементов.
| array1 = ['bananas', 'kiwis', 'lemons', 'apples', 'pears', 'melons'] | |
| array2 = ['pineapples', 'apples', 'cherries', 'bananas', 'watermelons'] | |
| counter = 0 | |
| for element1 in array1: | |
| for element2 in array2: | |
| if element1 == element2: | |
| counter += 1 | |
| print(f'Common elements: {counter}') |
Временные требования этого алгоритма также зависят от количества n элементов для проверки. Для каждого элемента массива он должен выполнять итерацию по всему другому массиву. Например, если бы мы добавили элемент в array1, программе пришлось бы перебирать каждый элемент array2 еще раз.
Поскольку общее количество итераций равно произведению длины первого массива на длину второго, добавление элемента в один массив увеличит количество итераций на длину другого, поскольку частная производная от f(a,b) = a*b по отношению к a равно b, а по отношению к b равно a. Нотация большого O для этого алгоритма будет O(a*b), но ее можно упростить до O(n), рассматривая длину одного из двух массивов как константу.
Как упоминалось ранее, оператор if и приращение counter можно игнорировать при расчете временной сложности, поскольку они не зависят от размера входных данных.
Вложенная итерация, экспоненциальная временная сложность
Следующий алгоритм генерирует все возможные комбинации паролей для заданного набора символов при переменной длине пароля.
| characters = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] | |
| combinations = [] | |
| password_length = 4 | |
| # n-base number representation of the password | |
| # Create an array initialized with all 0 and with a size of password_length | |
| n_base_password = [0 for _ in range(password_length)] | |
| # Utility variable | |
| add_one = False | |
| # For every number between 0 and the number of characters elevated to the power of the password's length | |
| for _ in range(len(characters) ** password_length): | |
| # Create a new password string to be built | |
| password = '' | |
| # Iterate over indices from 0 to the password's length | |
| for i in range(password_length): | |
| # Normalize the n-based number and build the password string | |
| if add_one: | |
| n_base_password[i] += 1 | |
| add_one = False | |
| if n_base_password[i] == len(characters): | |
| n_base_password[i] = 0 | |
| add_one = True | |
| # Build the password string | |
| password += characters[n_base_password[i]] | |
| combinations.append(password) | |
| # Increment the first digit of the n-base number | |
| n_base_password[0] += 1 | |
| print(f'Possible combinations: {combinations}') |
Пусть n — длина пароля, а k — постоянное количество доступных символов, эта программа выполняет n*kⁿ итераций. Это связано с тем, что для каждой из kⁿитераций внешнего цикла for n других итераций выполняется внутренним циклом for. Остальные операции можно игнорировать.
Производная числа итераций n*kⁿ равна kⁿ+kⁿ*n*log(k), но может быть приближена к O(n *kⁿ), часто пишется как O(n*2ⁿ), по мере того, как размер ввода растет к бесконечности.
Логарифмическая временная сложность
Давайте теперь перейдем к очень популярному алгоритму: бинарный поиск. Учитывая отсортированный массив, он находит индекс указанного элемента, если он существует.
| def binary_search(array, target): | |
| left_index = 0 | |
| right_index = len(array) - 1 | |
| middle_index = 0 | |
| while left_index <= right_index: | |
| middle_index = (right_index + left_index) // 2 | |
| if array[middle_index] < target: | |
| left_index = middle_index + 1 | |
| elif array[middle_index] > target: | |
| right_index = middle_index - 1 | |
| else: | |
| return middle_index | |
| return -1 |
Двоичный поиск работает, отбрасывая половину массива на каждой итерации. Этот подход очень быстро сокращает элементы для поиска, несмотря на размер данного массива. Он набирает O(log(n)) по временной сложности и очень эффективен, когда речь идет о больших размерах входных данных, благодаря логарифмическому времени выполнения.
Факторная временная сложность
Один из наихудших возможных случаев, когда речь идет о большом O, — время выполнения факториала. Возьмите этот простой фрагмент кода в качестве примера:
| def factorial(number): | |
| for _ in range(number): | |
| print(number) | |
| factorial(number - 1) |
Для каждой итерации этой функции factorial вызывается несколько раз. Этот рекурсивный вызов приводит к тому, что цикл for выполняется снова и снова, пока number не достигнет нуля. Этот алгоритм действительно очень медленный, особенно в случае больших входных чисел. Временная сложность этой функции составляет O(n!).
Как выбрать правильный алгоритм
Когда пришло время взяться за проблему, важно выбрать алгоритм, который правильно подходит к ситуации. Может показаться очевидным, что вы должны выбрать минимально возможную временную сложность, верно? На самом деле это не так просто.
В зависимости от размера входных данных и конкретной реализации O(n) может быть даже быстрее, чем O(1). Взгляните на этот график:
В долгосрочной перспективе более низкие временные сложности всегда будут более эффективными, чем их более высокие аналоги. Однако есть момент, когда некоторые линии производительности перекрываются, на что следует обратить пристальное внимание, если вы намерены максимально оптимизировать свои программы.
Как вы можете видеть, ниже определенного порога, который полностью зависит от ситуации, некоторые алгоритмы, которые показывают худшие результаты в большом O, на самом деле имеют преимущество перед другими, которые могут работать лучше с большими размерами входных данных. Это означает, что вы должны сначала глубоко проанализировать и соответствующую среду, прежде чем прыгать на клавиатуре. В зависимости от данных, которые вам нужно обработать, график вашего алгоритма на этом уровне может выглядеть по-разному.
Заключение
Подводя итог, важно хорошо знать свою проблему и свои данные, чтобы применить наиболее эффективный алгоритм для ситуации. При планировании создания приложения вы должны учитывать, как оно будет работать по мере роста пользовательской базы и данных, и соответствующим образом адаптировать свой код.
К сожалению, не существует инструмента, подходящего для всех целей и ситуаций. Оптимизация заключается в использовании наиболее подходящего для конкретного случая, а не в том, чтобы сначала придерживаться того, что у вас может быть под рукой.
Даже если вы можете забить винт молотком, вы также можете использовать отвертку.
Надеюсь, вам понравилась эта статья. Если у вас есть вопрос или вы хотите что-то добавить, пожалуйста, поделитесь своими мыслями в комментариях. Я хотел бы знать ваше мнение.
Спасибо, что прочитали!
