Чистыйкод дляпродолжающи х
 Скачать 7.85 Mb.
|
|
Почему низкие порядки и коэффициенты не важны Низкие порядки исключаются из подсчета шагов, потому что они становятся менее значимыми с увеличением размера n. Если список books из приведенной функции readingList() увеличивается с 10 до 10 000 000 000 (10 миллиардов), количество шагов увеличится с 23 до 20 000 000 003. При достаточно больших n эти три до- полнительных шага ни на что не влияют. При увеличении объема данных большой коэффициент меньшего порядка может игнорироваться по сравнению с высокими порядками. При определенном разме- ре n более высокие порядки всегда будут медленнее низких порядков. Допустим, имеется функция quadraticExample() с порядком O(n 2 ) и она состоит из 3n 2 шагов. Другая функция linearExample() с порядком O(n) состоит из 1000n шагов. Не- важно, что коэффициент 1000 больше коэффициента 3; с ростом n квадратичная операция O(n 2 ) станет медленнее линейной операции O(n). Реальный код не столь важен, но он может выглядеть примерно так: def quadraticExample(someData): # n - размер someData for i in someData: # n шагов for j in someData: # n шагов print('Something') # 1 шаг print('Something') # 1 шаг print('Something') # 1 шаг def linearExample(someData): # n - размер someData for i in someData: # n шагов for k in range(1000): # 1 * 1000 шагов print('Something') # (уже подсчитано) Функция linearExample() имеет большой коэффициент (1000) по сравнению с коэффициентом (3) функции quadraticExample() . Если размер входных данных n равен 10, то функция O(n 2 ) вроде бы работает быстрее — всего 300 шагов по срав- нению с 10 000 шагами функции O(n). Но нотация «О-большое» в основном описывает эффективность алгоритма при большом объеме работы. Когда n достигнет размера 334 и выше, функция quadraticExample() всегда будет медленнее функции linearExample() . Даже если linearExample() равна 1000000n шагов, функция quadraticExample() все равно будет медленнее, когда n достигнет 333 334. В какой-то момент операция O(n 2 ) всегда становится медленнее O(n), или низшей операции. Чтобы убедиться в этом, 280 Глава 13.Измерение быстродействия и анализ сложности алгоритмов взгляните на график нотации «О-большое» на рис. 13.3. На графике представлены все основные порядки нотации «О-большое». По оси x представлен размер данных x, а по оси y — время выполнения, необходимое для выполнения операции. Вр ем я Данные n² n log n n log n 1 Рис. 13.3. График порядков нотации «О-большое» Как видно из графика, время выполнения более высоких порядков растет быстрее, чем время низких порядков. Хотя низкие порядки могут иметь более высокие ко- эффициенты, из-за которых они изначально показывают большие затраты времени, рано или поздно высокие порядки их обойдут. Примеры анализа «О-большое» Определим порядки «О-большое» для некоторых примеров функций. В этих при- мерах будет использоваться параметр books , который представляет собой список строк с названиями книг. Функция countBookPoints() вычисляет оценку на основании количества книг в списке. Большинство книг получает одно очко, а книги определенного автора получают два очка: def countBookPoints(books): points = 0 # 1 шаг for book in books: # n * шагов в цикле points += 1 # 1 шаг for book in books: # n * шагов в цикле Определение порядка сложности нотации «О-большое» вашего кода 281 if 'by Al Sweigart' in book: # 1 шаг points += 1 # 1 шаг return points # 1 шаг Количество шагов достигает 1 + (n × 1) + (n × 2) + 1, что преобразуется в 3n + 2 после объединения подобных членов. После исключения составляющих низких порядков и коэффициентов мы приходим к O(n), то есть к линейной сложности, независимо от того, сколько раз перебираются книги — один, два или миллиард. До настоящего момента все примеры, в которых использовался один цикл, имели линейную сложность, но обратите внимание: все эти циклы выполнялись n раз. Как показывает следующий пример, цикл в коде не всегда подразумевает линейную сложность (которая характеризует циклы, перебирающие входные данные). Функция iLoveBooks() выводит сообщения «I LOVE BOOKS!!!» и «BOOKS ARE GREAT!!!» 10 раз: def iLoveBooks(books): for i in range(10): # 10 * шагов в цикле print('I LOVE BOOKS!!!') # 1 шаг print('BOOKS ARE GREAT!!!') # 1 шаг Функция содержит цикл for , но этот цикл не перебирает список books и выполняет 20 шагов независимо от размера books . Можно переписать это как 20(1). После исключения коэффициента 20 остается O(1), то есть постоянная сложность. Все логично: функция выполняется за одно и то же время независимо от n (размера списка books). Затем рассмотрим функцию cheerForFavoriteBook() , которая ищет любимую книгу в списке books : def cheerForFavoriteBook(books, favorite): for book in books: # n * шагов в цикле print(book) # 1 шаг if book == favorite: # 1 шаг for i in range(100): # 100 * шагов в цикле print('THIS IS A GREAT BOOK!!!') # 1 шаг Цикл for book перебирает список books , для чего требуется n шагов, умноженных на количество шагов в цикле. Этот цикл включает вложенный цикл for , который выполняется 100 раз. То есть цикл for book выполняется 102 × n, или 102n раз. По- сле исключения коэффициента выясняется, что cheerForFavoriteBook() все еще остается линейной операцией O(n). Коэффициент 102 может показаться слиш- ком большим, чтобы его игнорировать, но примите во внимание следующее: если favorite не встречается в списке books , эта функция выполнит только 1n шагов. Влияние коэффициентов может изменяться в таких пределах, что их трудно рас- сматривать как содержательные. 282 Глава 13.Измерение быстродействия и анализ сложности алгоритмов Затем функция findDuplicateBooks() просматривает список books (линейная опе- рация) по одному разу для каждой книги (другая линейная операция): def findDuplicateBooks(books): for i in range(books): # n шагов for j in range(i + 1, books): # n шагов if books[i] == books[j]: # 1 шаг print('Duplicate:', books[i]) # 1 шаг Цикл for i перебирает весь список books , выполняя шаги в цикле n раз. Цикл j также перебирает часть списка books , хотя из-за исключения коэффициентов это также считается операцией с линейным временем. То есть цикл for i выполняет n × n операций, а именно n 2 . Как следствие, findDuplicateBooks() является опера- цией с полиномиальным временем O(n 2 ). Вложенные циклы сами по себе не подразумевают полиномиальной операции, но такой сложностью обладают вложенные циклы, в которых оба цикла выполняют n итераций. В результате будут выполнены n 2 шагов, а это подразумевает опера- цию O(n 2 ). Рассмотрим более сложный пример. Алгоритм бинарного поиска, упоминавшийся ранее, основан на поиске значения (назовем его needle ) в середине отсортирован- ного списка (назовем его haystack ) 1 . Если элемент needle не найден, мы переходим к поиску в первой или второй половине haystack в зависимости от того, в какой половине мы рассчитываем найти needle . Процесс повторяется, поиск ведется в по- стоянно уменьшающихся половинах, либо пока не будет найден элемент needle , либо пока не будет сделан вывод о том, что в haystack его нет. Обратите внимание: бинарный поиск работает только в том случае, если элементы haystack следуют в порядке сортировки. def binarySearch(needle, haystack): if not len(haystack): # 1 шаг return None # 1 шаг startIndex = 0 # 1 шаг endIndex = len(haystack) - 1 # 1 шаг haystack.sort() # ??? шагов while start <= end: # ??? steps midIndex = (startIndex + endIndex) // 2 # 1 шаг if haystack[midIndex] == needle: # 1 шаг # Значение needle найдено. return midIndex # 1 шаг elif needle < haystack[midIndex]: # 1 шаг # Искать в первой половине. 1 Needle — иголка, haystack — стог сена (англ). — Примеч. ред. Определение порядка сложности нотации «О-большое» вашего кода 283 endIndex = midIndex - 1 # 1 шаг elif needle > haystack[mid]: # 1 шаг # Искать во второй половине. startIndex = midIndex + 1 # 1 шаг Две строки binarySearch() оценить не так легко. Порядок «О-большое» вызова метода haystack.sort() зависит от кода, находящегося в методе Python sort() Найти этот код непросто, но в интернете можно поискать информацию о методе и узнать, что он выполняется с порядком O(n log n). (Все основные функции сорти- ровки выполняются в лучшем случае за время O(n log n).) Порядок «О-большое» для некоторых распространенных функций и методов Python описан в этой главе в разделе «Порядок “О-большое” для часто используемых функций». Цикл while анализируется несколько сложнее, чем показанные выше циклы for Чтобы определить, сколько итераций будет выполнено в цикле, необходимо пони- мать алгоритм бинарного поиска. До начала цикла startIndex и endIndex покрывают весь диапазон haystack , а midIndex устанавливается в середину этого диапазона. При каждой итерации цикла while происходит одно из двух. Если haystack[midIndex] == needle , искомое значение найдено и функция возвращает индекс needle в haystack Если needle < haystack[midIndex] или needle > haystack[midIndex] , диапазон, покрываемый startIndex и endIndex , сокращается вдвое — за счет изменения либо startIndex , либо endIndex . Число делений любого списка размера n надвое составляет log2(n). (К сожалению, это просто математический факт, который вы должны знать.) Таким образом, у цикла while порядок нотации «О-большое» со- ставляет O(log n). Но так как порядок O(n log n) строки haystack.sort() выше O(log n), более низкий порядок O(log n) исключается, а порядком всей функции binarySearch() становится O(n log n). Если мы можем гарантировать, что binarySearch() будет вызываться только с отсортированным списком haystack , строку haystack.sort() можно опустить и сделать binarySearch() функцией O(log n). Формально это улучшает эффективность функции, но не делает всю программу более эффек- тивной, потому что необходимая работа по сортировке просто перемещается в другую часть программы. Многие реализации бинарного поиска опускают шаг сортировки, поэтому говорят, что алгоритм бинарного поиска обладает логариф- мической сложностью O(log n). Порядок «О-большое» для часто используемых функций Анализ эффективности вашего кода должен учитывать порядок сложности всех вызываемых функций. Если вы сами написали функцию, вы сможете проанали- зировать собственный код. Но чтобы найти порядок «О-большое» для встроенных функций и методов Python, приходится обращаться к спискам вроде приведенного ниже. 284 Глава 13.Измерение быстродействия и анализ сложности алгоритмов В списке показаны порядки некоторых распространенных операций Python для типов последовательностей — таких как строки, кортежи и списки. s[i] reading и s[i] = value assignment — операции O(1). s.append(value) — операция O(1). s.insert(i, value) — операция O(n). Вставка значения в последовательность (особенно в начало) требует сдвига всех элементов с индексами выше i на одну позицию вверх в последовательности. s.remove(value) — операция O(n). Удаление значений из последовательности (особенно в начале) требует сдвига всех элементов с индексами выше i на одну позицию вниз в последовательности. s.reverse() — операция O(n), потому что необходимо переставить все эле- менты последовательности. s.sort() — операция O(n log n), потому что алгоритм сортировки Python имеет сложность O(n log n). value in s — операция O(n), потому что необходимо проверить каждый элемент. for value in s: — операция O(n). len(s) — операция O(1), потому что Python хранит количество элементов в последовательности, чтобы их не приходилось заново пересчитывать при каждом вызове len() В следующем списке приведены порядки «О-большое» для некоторых распростра- ненных операций Python для типов отображений (таких как словари, множества и фиксированные множества). m[key]reading и m[key] = value assignment — операции O(1). m.add(value) — операция O(1). value in m — операция O(1) для словарей; выполняется намного быстрее, чем для последовательностей. for key in m: — операция O(n). len(m) — операция O(1), потому что Python хранит количество элементов в отображении, чтобы их не приходилось заново пересчитывать при каждом вызове len() Если в списках элементы обычно приходится искать от начала до конца, словари ис- пользуют ключ для вычисления адреса, а время, необходимое для поиска значения Определение порядка сложности нотации «О-большое» вашего кода 285 по ключу, остается постоянным. Способ вычисления называется алгоритмом хеши- рования, а адрес — хеш-кодом. Тема хеширования выходит за рамки книги, но именно из-за него многие операции отображения выполняются с постоянным временем O(1). Множества также используют хеширование, потому что множества по сути являются словарями, содержащими только ключи (вместо пар «ключ — значение»). Но помните, что преобразование списка во множество является операцией O(n), так что преобразование списка во множество с последующим обращением к элементам множества не обеспечит никакого выигрыша. Моментальный анализ сложности Когда вы освоитесь с выполнением анализа «О-большое», вам не придется вы- полнять каждый из шагов. Через какое-то время вы сможете просто взглянуть на какие-то характерные особенности кода, чтобы быстро определить его порядок сложности. Если обозначить переменной n размер данных, с которыми работает код, можно воспользоваться рядом общих правил. Если код не обращается ни к каким данным, это O(1). Если код последовательно перебирает данные, это O(1). Если код содержит два вложенных цикла, каждый из которых перебирает данные, это O(n 2 ). Вызовы функций включаются в подсчеты не как один шаг, а как общее коли- чество шагов кода внутри функции. См. подраздел «Порядок “О-большое” для часто используемых функций», с. 283. Если код содержит операцию «разделяй и властвуй», которая многократно делит данные надвое, это O(log n). Если код содержит операцию «разделяй и властвуй», которая выполняется по одному разу для каждого элемента данных, это O(n log n). Если код перебирает все возможные комбинации значений в данных с раз- мером n, это O(2 n ) или другой экспоненциальный порядок. Если код перебирает все возможные перестановки (то есть варианты упоря- дочения) значений данных, это O(n!). Если код включает сортировку данных, это как минимум O(n log n). Эти правила станут хорошей отправной точкой для анализа, но они не заменят ре- ального анализа «О-большое». Помните, что порядок не является окончательным 286 Глава 13.Измерение быстродействия и анализ сложности алгоритмов критерием того, является ли код медленным, быстрым или эффективным. Рас- смотрим следующую функцию waitAnHour() : import time def waitAnHour(): time.sleep(3600) Формально функция waitAnHour() является функцией с постоянным временем O(1). Считается, что код с постоянным временем работает быстро, но на ее выпол- нение требуется целый час! Означает ли это, что код неэффективен? Нет. Трудно представить себе реализацию waitAnHour() , которая бы выполнялась быстрее одного часа. Анализ «О-большое» не заменит профилирования вашего кода. Его цель — дать представление о том, как поведет себя ваш код при возрастающем объеме входных данных. «О-большое» не имеет значения при малых n… а значения n обычно малы Когда вы вооружитесь знанием нотации «О-большое», у вас может возникнуть искушение анализировать каждый написанный вами фрагмент кода. Прежде чем с азартом лупить по каждому гвоздю, попавшему в поле зрения, следует учесть, что нотация «О-большое» полезна прежде всего при большом объеме обрабатываемых данных. В реальных ситуациях объем данных обычно невелик. В таких случаях проработка нетривиальных, хитроумных алгоритмов с низкими порядками «О-большое» может оказаться нерациональной. Разработчик языка программирования Go Роб Пайк (Rob Pike) сформулировал пять правил програм- мирования, одно из которых гласит: «Хитроумные алгоритмы медленно работают при малых n, а значения n обычно малы». Большинство разработчиков имеет дело не с программами для огромных центров обработки данных или для суперслож- ных вычислений, а с обычными повседневными программами. В таких ситуациях выполнение вашего кода под управлением профилировщика предоставит более конкретную информацию о быстродействии кода, чем анализ «О-большое». Итоги В стандартную библиотеку Python включены два модуля для профилирования: timeit и cProfile . Функция timeit.timeit() полезна для выполнения небольших фрагментов кода с целью сравнения времени их выполнения. Функция cProfile. run() компилирует подробный отчет по большим функциям и может выявить любые узкие места. Итоги 287 Важно измерять быстродействие вашего кода, а не делать предположения относи- тельно него. Хитроумные трюки для ускорения работы программы на самом деле могут замедлить ее. Или есть вероятность, что вы потратите много времени на оптимизацию фрагмента, который будет незначительно влиять на скорость вашей программы. Закон Амдала отражает этот факт в математическом виде: формула описывает, как ускорение работы одного компонента влияет на ускорение про- граммы в целом. Пожалуй, из всех концепций теории вычислений именно нотация «О-большое» находит наибольшее практическое применение. Для ее понимания необходимы определенные знания математики, но концепция определения закономерности замедления кода с ростом объема данных позволяет описывать алгоритмы без длинных формул. Известны семь основных порядков сложности нотации «О-большое». Низкие по- рядки: O(1), или постоянное время, описывает код, время выполнения которого не изменяется с увеличением размера данных n; O(log n), или логарифмическое время, описывает код, сложность которого увеличивается на один шаг при увеличении размера данных n вдвое; O(n), или линейное время, описывает код, который за- медляется пропорционально росту размера данных n; O(n log n), или время n-log-n, описывает код, который работает немного медленнее O(n) — многие алгоритмы со- ртировки относятся к этому порядку. Более высокие порядки работают медленнее, потому что их время выполнения растет намного быстрее размера входных данных: O(n 2 ), или полиномиальное время, описывает код, время выполнения которого растет в квадратичной зависимости от размера входных данных n; порядки O(2 n ), или экспоненциальное время, и O(n!), или факториальное время, встречаются не так часто — в основном там, где в вычислениях используются комбинации и пере- становки соответственно. Помните: хотя нотация «О-большое» является полезным аналитическим инстру- ментом, она не заменит выполнения кода в профилировщике для выявления узких мест. Однако если вы будете понимать нотацию «О-большое» и закономерности замедления кода с ростом данных, это позволит избежать написания кода, который работает значительно медленнее, чем мог бы. |