0

Имеется задача. Во время шифрования алгоритм принимает символы шифруемого текста по одному и заменяет этот символ на один другой символ. Кодировка состоит из m символов, поэтому можно считать, что текст представляет собой последовательность натуральных чисел, не превосходящих. Во время работы алгоритм шифрования поддерживает перестановку натуральных чисел от 1 до m. В начале работы перестановка тождественна. Когда алгоритму на вход поступает символ x, алгоритм заменяет его на номер позиции в перестановке (в 1-индексации), на которой находится символ x, а также переносит x в начало перестановки. Например, если в некоторый момент работы алгоритма перестановка символов в нём равна [3, 1, 2], а на вход подаётся символ 1, то символ 1 будет заменён на символ 2, поскольку 1 стоит в перестановке на второй позиции, а перестановка примет вид [1, 3, 2].

Я написал код:

def encrypt(disp):
    res = []
    for i in input().split():
        pos = disp.index(int(i))
        res.append(pos + 1)
        disp = [disp[pos]] + disp[:pos] + disp[pos + 1:]
    return res

На вход поступает начальное состояние перестановки. Например [1, 2, 3, 4]. Пример работы алгоритма: 2 1 2 3 1 3 1 -> 2 2 2 3 3 2 2. Проблема в том, что мой алгоритм не укладывается в отведенный лимит времени. Может, есть способы ускорить работу? Работа алгоритма станет понятней если его показать таблицей. Зашифруем слово 2 3 1 2 1 1 1. Пусть x - входная буква, p - состояние перестановки на момент вхождения, y - результат.

c[

2
  • После неоднократного чтения условия понятнее не стало. Так и в задаче сформулировано?
    – rokitoker
    1 апр 2020 в 15:32
  • @rokitoker Добавил схему работы алгоритма
    – exeynod
    1 апр 2020 в 16:23

1 ответ 1

0

Ну, как минимум.

input().split() вынести за цикл, после ввода определять количество введенных знаков, порождать res сразу нужного размера а потом работать с ним не как с списком динамически изменяемого размера, а как с массивом.

3
  • Это незначительно ускорит работу
    – exeynod
    1 апр 2020 в 19:34
  • @exeynod значит вы не очень понимаете, на сколько ресурсоемкая процедура добавления элемента в динамический список и на сколько операции над массивами быстрее операций со списками.
    – passant
    2 апр 2020 в 12:37
  • что вы понимаете под статическим массивом в python тогда? Numpy использовать нельзя
    – exeynod
    2 апр 2020 в 16:20

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.