Обращение последовательностей может быть реализовано рекурсивно или итеративно, а также в виде функций или методов классов. В примере 18.23 представлена первая пробная реализация двух простых функций обращения.
Пример 18.23. PP4E\Dstruct\Classics\rev1.py
def reverse(list): # рекурсивная
if list == []:
return []
else:
return reverse(list[1:]) + list[:1]
def ireverse(list): # итеративная
res = [] for x in list: res = [x] + res return res
Обе функции обращения корректно обрабатывают списки. Но если попробовать обратить последовательности, не являющиеся списками (строки, кортежи и другие), функция ireverse всегда будет возвращать в качестве результата список независимо от того, какая последовательность ей передана:
>>> ireverse("spam")
[‘m’, ‘a’, ‘p’, ‘s’]
Что еще хуже, рекурсивная версия reverse вообще работает только со списками — с другими последовательностями она входит в бесконечный цикл. Такое поведение обусловлено весьма тонкой причиной: когда reverse добирается до пустой строки (""), последняя оказывается не равной пустому списку ([]), поэтому выбирается предложение else. Но срез пустой последовательности снова возвращает пустую последовательность (индексы увеличиваются): снова повторяется предложение else с пустой строкой без возбуждения исключения. В итоге функция попадает в бесконечный цикл, вызывая себя снова и снова, пока Python не исчерпает всю память.
• reverse использует оператор not для обнаружения конца последовательности и возвращает саму пустую последовательность, а не константу пустого списка. Поскольку пустая последовательность имеет тип исходного аргумента, операция + всегда строит последовательность правильного типа по мере развертывания рекурсии.
• ireverse использует то обстоятельство, что операция извлечения среза последовательности возвращает последовательность того же типа. Она сначала инициализирует результат срезом [:0] — новым пустым срезом того же типа, что и аргумент. Затем с помощью операций извлечения среза извлекаются последовательности из одного узла, добавляемые в начало результата, а не в константу списка.
Пример 18.24. PP4E\Dstruct\Classics\rev2.py
def reverse(list):
if not list: # пустая? (не всегда [])
return list # последов. того же типа
else:
return reverse(list[1:]) + list[:1] # добавить передн. элемент # в конец
def ireverse(list):
res = list[:0] # пустая, того же типа
for i in range(len(list)):
res = list[i:i+1] + res # добавить каждый элемент в начало
return res
Внесение этих изменений позволяет новым функциям работать с любыми последовательностями и возвращать новые последовательности того же типа, что и исходные. Если передать строку, в качестве результата получим новую строку. На самом деле они переворачивают любую последовательность объектов, которая поддерживает извлечение срезов, конкатенацию и len, — даже экземпляров классов Python и типов языка С. Иными словами, они могут переворачивать любые объекты, поддерживающие интерфейс последовательностей. Ниже приводится пример их работы со списками, строками и кортежами:
> >> from rev2 import *
> >> reverse([1, 2, 3]), ireverse([1, 2, 3])
([3, 2, 1], [3, 2, 1])
>>> reverse("spam"), ireverse("spam")
(‘maps’, ‘maps’)
> >> reverse((1.2, 2.3, 3.4)), ireverse((1.2, 2.3, 3.4))
((3.4, 2.3, 1.2), (3.4, 2.3, 1.2))
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
