ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 388
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
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!), или факториальное время, встречаются не так часто — в основном там, где в вычислениях используются комбинации и пере- становки соответственно.
Помните: хотя нотация «О-большое» является полезным аналитическим инстру- ментом, она не заменит выполнения кода в профилировщике для выявления узких мест. Однако если вы будете понимать нотацию «О-большое» и закономерности замедления кода с ростом данных, это позволит избежать написания кода, который работает значительно медленнее, чем мог бы.
1 ... 26 27 28 29 30 31 32 33 ... 40
14
Проекты для тренировки
До настоящего момента в этой книге я рассказывал о при- емах написания удобочитаемого питонического кода. Теперь настало время применить эти приемы на практике; рассмо- трим исходный код двух игр командной строки: «Ханойская башня» и «Четыре в ряд».
Это небольшие проекты, и они работают в текстовом режиме, чтобы не переусложнять задачу, но они неплохо демонстрируют принципы, о которых я рассказал ранее. Для форматирования кода я использовал программу Black, описанную в разделе «Black: бескомпромиссная система форматирования кода», с. 79. Имена переменных были выбраны в соответствии с рекомендациями из главы 4. Код написан в питоническом стиле, о котором шла речь в главе 6. Кроме того, я написал комментарии и doc-строки по правилам из главы 11. Так как программы невелики, а объектно-ориентированное программирование (ООП) в книге еще не рассматривалось, я написал эти два проекта без классов — о них я расскажу чуть позже, в главах 15–17.
В этой главе приведен полный исходный код этих двух проектов — с полным ана- лизом. Объяснения относятся не столько к тому, как работает код (для понимания этого достаточно базового понимания синтаксиса Python), а скорее к тому, почему этот код написан именно так, а не иначе. Тем не менее разные разработчики могут иметь разные мнения относительно того, как писать код и какой код следует счи- тать питоническим. Безусловно, ничто не мешает вам оспаривать и критиковать исходники, представленные в этих проектах.
После того как вы прочитаете код проекта в книге, я рекомендую вам самостоятель- но ввести этот код и несколько раз выполнить программы, чтобы понять, как они работают. Затем попытайтесь заново реализовать их с нуля. Ваш код не обязательно должен полностью повторять тот, что приведен в книге, но переписывая его, вы
Головоломка «Ханойская башня»
289
получите представление о принимаемых решениях и компромиссах, на которые приходится идти программисту.
Головоломка «Ханойская башня»
Даны три стержня, на один из которых нанизаны диски, причем диски отличаются размером и лежат меньший на большем. Задача состоит в том, чтобы перенести пирамиду из дисков на другой стержень за наименьшее число ходов (рис. 14.1).
При этом действуют три ограничения.
1. Диски можно перемещать по одному.
2. Игрок может перекладывать диски только с верха стопки на верх другой стопки.
3. Нельзя переложить больший диск на меньший.
Рис. 14.1. Головоломка «Ханойская башня»
Решение головоломки часто используется в компьютерной науке как задача для изучения рекурсивных алгоритмов. Наша программа не будет решать головоломку; она будет выводить изображение головоломки, чтобы пользователь мог решить ее.
За дополнительной информацией о головоломке «Ханойская башня» обращайтесь на https://ru.wikipedia.org/wiki/Ханойская_башня.
Вывод результатов
Программа рисует башни в ASCII-графике, для изображения дисков используются текстовые символы. Приложение выглядит примитивно по сравнению с современ- ными программами, но такой подход сохраняет простоту реализации, потому что
290
Глава 14.Проекты для тренировки для взаимодействия с пользователем достаточно вызовов print()
и input()
. Ниже показан примерный результат запуска программы. Текст, введенный игроком, обо- значен жирным шрифтом.
THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
Move the tower of disks, one disk at a time, to another tower. Larger disks cannot rest on top of a smaller disk.
More info at https://en.wikipedia.org/wiki/Tower_of_Hanoi
|| || ||
@_1@ || ||
@@_2@@ || ||
@@@_3@@@ || ||
@@@@_4@@@@ || ||
@@@@@_5@@@@@ || ||
A B C
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
> AC
|| || ||
|| || ||
@@_2@@ || ||
@@@_3@@@ || ||
@@@@_4@@@@ || ||
@@@@@_5@@@@@ || @_1@
A B C
Enter the letters of "from" and "to" towers, or QUIT.
(e.g., AB to moves a disk from tower A to tower B.)
--snip--
|| || ||
|| || @_1@
|| || @@_2@@
|| || @@@_3@@@
|| || @@@@_4@@@@
|| || @@@@@_5@@@@@
A B C
You have solved the puzzle! Well done!
Для n дисков решение головоломки требует минимум 2
n
– 1 ходов. Таким образом, решение для башни с пятью дисками состоит из 31 хода: AC, AB, CB, AC, BA, BC, AC,
AB, CB, CA, BA, CB, AC, AB, CB, AC, BA, BC, AC, BA, CB, CA, BA, BC, AC, AB, CB,
AC, BA, BC и AC. Если вам понадобится усложнить пример для самостоятельного решения, увеличьте переменную
TOTAL_DISKS
в программе с 5 до 6.
Головоломка «Ханойская башня»
291
Исходный код
Откройте в редакторе или IDE новый файл и введите приведенный ниже код. Со- храните файл с именем towerofhanoi.py
"""THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
Головоломка с перемещением дисков."""
import copy import sys
TOTAL_DISKS = 5 # Чем больше дисков, тем сложнее головоломка.
# Изначально все диски находятся на стержне A:
SOLVED_TOWER = list(range(TOTAL_DISKS, 0, -1))
def main():
"""Проводит одну игру Ханойская башня."""
print(
"""THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
Move the tower of disks, one disk at a time, to another tower. Larger disks cannot rest on top of a smaller disk.
More info at https://en.wikipedia.org/wiki/Tower_of_Hanoi
"""
)
"""Словарь towers содержит ключи "A", "B" и "C", и значения - списки,
представляющие стопку дисков. Список содержит целые числа, представляющие диски разных размеров, а начало списка представляет низ башни. Для игры с 5 дисками список [5, 4, 3, 2, 1] представляет заполненную башню. Пустой список list [] представляет башню без дисков. В списке [1, 3] больший диск находится на меньшем диске, такая конфигурация недопустима. Список [3, 1]
допустим, так как меньшие диски могут размещаться на больших."""
towers = {"A": copy.copy(SOLVED_TOWER), "B": [], "C": []}
while True: # Один ход для каждой итерации цикла.
# Вывести башни и диски:
displayTowers(towers)
# Запросить ход у пользователя:
fromTower, toTower = getPlayerMove(towers)
# Переместить верхний диск с fromTower на toTower:
disk = towers[fromTower].pop()
towers[toTower].append(disk)
# Проверить, решена ли головоломка:
if SOLVED_TOWER in (towers["B"], towers["C"]):
displayTowers(towers) # Вывести башни в последний раз.
292
Глава 14.Проекты для тренировки print("You have solved the puzzle! Well done!")
sys.exit()
def getPlayerMove(towers):
"""Запрашивает ход у пользователя. Возвращает (fromTower, toTower)."""
while True: # Пока пользователь не введет допустимый ход.
print('Enter the letters of "from" and "to" towers, or QUIT.')
print("(e.g., AB to moves a disk from tower A to tower B.)")
print()
response = input("> ").upper().strip()
if response == "QUIT":
print("Thanks for playing!")
sys.exit()
# Убедиться в том, что пользователь ввел допустимые обозначения башен:
if response not in ("AB", "AC", "BA", "BC", "CA", "CB"):
print("Enter one of AB, AC, BA, BC, CA, or CB.")
continue # Снова запросить ход.
# Более содержательные имена переменных:
fromTower, toTower = response[0], response[1]
if len(towers[fromTower]) == 0:
# Башня fromTower не может быть пустой:
print("You selected a tower with no disks.")
continue # Снова запросить ход.
elif len(towers[toTower]) == 0:
# На пустую башню можно переместить любой диск:
return fromTower, toTower elif towers[toTower][-1] < towers[fromTower][-1]:
print("Can't put larger disks on top of smaller ones.")
continue # Снова запросить ход.
else:
# Допустимый ход, вернуть выбранные башни:
return fromTower, toTower def displayTowers(towers):
"""Выводит три башни с дисками."""
# Вывести три башни:
for level in range(TOTAL_DISKS, -1, -1):
for tower in (towers["A"], towers["B"], towers["C"]):
if level >= len(tower):
displayDisk(0) # Вывести пустой стержень без диска.
else:
displayDisk(tower[level]) # Вывести диск.
print()
# Вывести обозначения башен A, B и C:
Головоломка «Ханойская башня»
293
emptySpace = " " * (TOTAL_DISKS)
print("{0} A{0}{0} B{0}{0} C\n".format(emptySpace))
def displayDisk(width):
"""Выводит диск заданной ширины. Ширина 0 означает отсутствие диска."""
emptySpace = " " * (TOTAL_DISKS - width)
if width == 0:
# Вывести сегмент стержня без диска:
print(f"{emptySpace}||{emptySpace}", end="")
else:
# Вывести диск:
disk = "@" * width numLabel = str(width).rjust(2, "_")
print(f"{emptySpace}{disk}{numLabel}{disk}{emptySpace}", end="")
# Если программа была запущена (а не импортирована), начать игру:
if __name__ == "__main__":
main()
Запустите программу и сыграйте несколько раз, чтобы получить представление о том, что она делает, прежде чем читать объяснения исходного кода. Чтобы про- верить возможные опечатки, скопируйте код в сетевую программу diff по адресу
https://inventwithpython.com/beyond/diff/.
Написание кода
А теперь рассмотрим исходный код и посмотрим, как в нем применяются приемы и шаблоны, описанные в книге.
Начало программы:
"""THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
Головоломка с перемещением дисков."""
Программа начинается с многострочного комментария, который служит doc- строкой для модуля towerofhanoi
. Встроенная функция help()
использует эту информацию для описания модуля:
>>> import towerofhanoi
>>> help(towerofhanoi)
Help on module towerofhanoi:
NAME
towerofhanoi
DESCRIPTION
THE TOWER OF HANOI, by Al Sweigart al@inventwithpython.com
Головоломка с перемещением дисков.