ИТ Блог. Администрирование серверов на основе Linux (Ubuntu, Debian, CentOS, openSUSE)

Проблемы с практикой Python. Приготовьтесь к следующему собеседованию. Шифр Цезаря. Часть 2

Проблемы с практикой Python. Приготовьтесь к следующему собеседованию

Практическая задача Python 3: Caesar Cipher Redux

Для третьей практической задачи вы снова решите шифр Цезаря, но на этот раз вы сделаете это без использования .translate().

 

Описание проблемы

Описание этой проблемы такое же, как и у предыдущей проблемы. Прежде чем погрузиться в решение проблемы, вы можете спросить, почему вы повторяете одно и то же упражнение, просто без помощи .translate().

Отличный вопрос. В обычной жизни, когда ваша цель – получить работающую, поддерживаемую программу, переписывание частей стандартной библиотеки – плохой выбор. Стандартная библиотека Python будет упаковано с работой, хорошо проверенные и быстрые решения проблем, больших и малых. Воспользоваться этим в полной мере – признак хорошего программиста.

Тем не менее, это не рабочий проект или программа, которую вы строите для удовлетворения потребности. Это обучающее упражнение, и именно такие вопросы можно задать во время собеседования. Цель обоих – увидеть, как вы можете решить проблему и какие интересные дизайнерские компромиссы вы придете при этом.

Итак, в духе обучения, давайте попробуем решить шифр Цезаря без .translate().

 

Проблема Решение

Для этой проблемы у вас будет два разных решения, когда вы будете готовы расширить раздел ниже.

Для этой проблемы предлагаются два различных решения. Проверьте оба и посмотрите, какой из них вы предпочитаете!

 

Решение 1

Для первого решения вы внимательно следите за описанием проблемы, добавляя сумму к каждому символу и переворачивая его обратно в начало алфавита, когда он идет дальше по ту сторону z:

 1 # caesar.py
 2 import string
 3 
 4 def shift_n(letter, amount):
 5     if letter not in string.ascii_lowercase:
 6         return letter
 7     new_letter = ord(letter) + amount
 8     while new_letter > ord("z"):
 9         new_letter -= 26
10     while new_letter < ord("a"):
11         new_letter += 26
12     return chr(new_letter)
13 
14 def caesar(message, amount):
15     enc_list = [shift_n(letter, amount) for letter in message]
16     return "".join(enc_list)

 

Начиная с строки 14, вы можете видеть, что caesar() делает ли а понимание списка, вызывая вспомогательную функцию для каждой буквы в message. Затем он делает .join() чтобы создать новую закодированную строку. Это коротко и мило, и вы увидите аналогичную структуру во втором решении. Самое интересное происходит в shift_n().

Здесь вы можете увидеть другое применение для string.ascii_lowercase, на этот раз отфильтровывая любую букву, которая не входит в эту группу. Как только вы будете уверены, что отфильтровали все не-буквы, вы можете перейти к кодированию. В этой версии кодирования вы используете две функции из стандартной библиотеки Python:

  1. ord()
  2. chr()

 

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

ord() выполняет работу по преобразованию Буквы в число, и chr() преобразует его обратно в букву. Это удобно, так как позволяет делать арифметику по буквам, что и нужно для этой задачи.

Первый шаг вашего кодирования в строке 7 получает числовое значение закодированной буквы с помощью ord() чтобы получить числовое значение исходной буквы. ord() возвращает значение Кодовая точка Юникода символа, который оказывается значением ASCII.

Для многих букв с небольшими значениями сдвига вы можете преобразовать букву обратно в символ, и все будет готово. Но рассмотрим начальную букву, z.

Сдвиг одного символа должен привести к появлению буквы a. Чтобы достичь этого, вы находите разницу от закодированной буквы к букве z. Если эта разница положительна, то вам нужно вернуться к началу.

Вы делаете это в строках с 8 по 11, многократно добавляя 26 к символу или вычитая его из него, пока он не окажется в диапазоне символов ASCII. Обратите внимание, что это довольно неэффективный метод для устранения этой проблемы. Вы увидите лучшее решение в следующем ответе.

Наконец, в строке 12 ваша функция преобразования shift принимает числовое значение новой буквы и преобразует его обратно в букву, чтобы вернуть ее.

Хотя это решение использует буквальный подход к решению проблемы шифра Цезаря, вы также можете использовать другой подход, смоделированный после .translate() решение в практической задаче 2.

 

Решение 2

Второе решение этой проблемы имитирует поведение встроенного метода Python .translate(). Вместо того чтобы сдвигать каждую букву на заданную величину, он создает карту перевода и использует ее для кодирования каждой буквы:

 1 # caesar.py
 2 import string
 3 
 4 def shift_n(letter, table):
 5     try:
 6         index = string.ascii_lowercase.index(letter)
 7         return table[index]
 8     except ValueError:
 9         return letter
10 
11 def caesar(message, amount):
12     amount = amount % 26
13     table = string.ascii_lowercase[amount:] + string.ascii_lowercase[:amount]
14     enc_list = [shift_n(letter, table) for letter in message]
15     return "".join(enc_list)

 

Начнем с того, что caesar() в строке 11 вы начинаете с устранения проблемы amount быть больше, чем 26. В предыдущем решении цикл повторялся до тех пор, пока результат не оказывался в нужном диапазоне. Здесь вы используете более прямой и эффективный подход, используя оператор mod (%).

То оператор mod производит остаток от целочисленного деления. В этом случае вы делите на 26, что означает, что результаты гарантированно будут между 0 и 25, включающий.

Затем вы создадите таблицу перевода. Это изменение по сравнению с предыдущими решениями и заслуживает некоторого внимания. Вы увидите больше об этом ближе к концу этого раздела.

Как только вы создадите table, остальная часть caesar() идентично предыдущему решению: понимание списка для шифрования каждой буквы и .join() чтобы создать строку.

shift_n() находит индекс данной буквы в алфавите и затем использует его для извлечения буквы из алфавита. table. Блок try…except ловит те случаи, которые не найдены в списке строчных букв.

Теперь давайте обсудим вопрос создания таблицы. Для этого игрушечного примера это, вероятно, не имеет большого значения, но он иллюстрирует ситуацию, которая часто встречается в повседневной разработке: балансирование ясности кода против известных узких мест производительности.

Если вы еще раз изучите код, то увидите, что table используется только внутри shift_n(). Это указывает на то, что в нормальных обстоятельствах он должен был бы быть создан и, таким образом, иметь свое масштаб ограничивается, shift_n():

# caesar.py
import string

def slow_shift_n(letter, amount):
    table = string.ascii_lowercase[amount:] + string.ascii_lowercase[:amount]
    try:
        index = string.ascii_lowercase.index(letter)
        return table[index]
    except ValueError:
        return letter

def slow_caesar(message, amount):
    amount = amount % 26
    enc_list = [shift_n(letter, amount) for letter in message]
    return "".join(enc_list)

 

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

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

В конце концов, выбор между созданием table один раз авансом и придавая ему больший объем или просто создавая его для каждой буквы это то что называется а проектное решение. Вы должны выбрать дизайн, основанный на том, что вы знаете о реальной проблеме, которую вы пытаетесь решить.

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

Поскольку вы рассмотрели два решения, стоит уделить время обсуждению их сходства и различия.

 

Сравнение Решений

Вы видели два решения в этой части шифра Цезаря, и они довольно похожи во многих отношениях. Это примерно одинаковое количество строк. Две основные процедуры идентичны за исключением ограничения amount и создание table. Это только когда вы смотрите на две версии вспомогательной функции, shift_n(), что различия появляются.

Первый shift_n() это почти буквальный перевод того, о чем просит проблема: “сдвиньте букву вниз по алфавиту и оберните ее вокруг z.”. Это явно восходит к постановке проблемы, но у нее есть несколько недостатков.

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

Первая версия функции также специфична для решения этой конкретной задачи. Вторая версия shift_n(), как и стандартная библиотека .translate() то, что он смоделирован, является более универсальным и может быть использовано для решения большего набора проблем. Обратите внимание, что это не обязательно хорошая цель Дизайна.

Одна из мантр, которые вышли из экстремальное программирование движение – это “тебе это не понадобится ” (ЯГНИ). Часто разработчики программного обеспечения будут смотреть на такую функцию, как shift_n() и решить, что было бы лучше и более общего назначения, возможно, путем передачи параметра вместо использования string.ascii_lowercase.

Хотя это действительно сделало бы функцию более универсальной, это также сделало бы ее более сложной. Мантра ЯГНИ существует для того, чтобы напоминать вам не добавлять сложности, прежде чем у вас будет конкретный случай ее использования.

Чтобы завершить ваш раздел шифра Цезаря, есть явные компромиссы между двумя решениями, но второе shift_n() похоже, это немного лучше.

 

Начало:

Продолжение:

Exit mobile version