Otimização do código de cifra de substituição em Python

Question

Aqui está meu código para testar minhas três funções diferentes que executam criptografia de substituição simples em 2.000 strings aleatórias de comprimento de até 500 com 2.000 chaves aleatórias.

A saída mostra que a melhor função é encrypt3então encrypt1e a mais lenta é encrypt2.

Quais são os outros métodos para realizar a substituição que seriam ainda mais rápidos encrypt3?

A substituição é realizada no alfabeto maiúsculo de "A" a "Z", nenhum outro caractere é permitido e nenhum teste é necessário para saber se as strings de entrada contêm apenas esses caracteres.

No final do código, há um teste para verificar se todas as funções produziram as mesmas saídas.

from random import randrange, seed, sample
from time import perf_counter

alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encrypt1(t,key):
    v=dict(zip(alphabet,key))
    return ''.join(v.get(n) for n in t)

def encrypt2(t,key):
    return ''.join(key[alphabet.index(n)] for n in t)

def encrypt3(t,key):
    return t.translate(str.maketrans(alphabet,key))
    
d=2000 # number of strings and keys to test
length=500 # biggest length of strings

strings=[''.join(chr(randrange(26)+65) for n in range(1,randrange(1,length))) for n in range(d)]

keys=[''.join(chr(n+65) for n in sample(range(26), 26)) for n in range(d)]

a=perf_counter()
en1=[encrypt1(strings[n],keys[n]) for n in range(d)]
b=perf_counter()
print('encrypt1 time:',b-a)

a=perf_counter()
en2=[encrypt2(strings[n],keys[n]) for n in range(d)]
b=perf_counter()
print('encrypt2 time:',b-a)

a=perf_counter()
en3=[encrypt3(strings[n],keys[n]) for n in range(d)]
b=perf_counter()
print('encrypt3 time:',b-a)

print("All encryptions outputs are same:",en1==en2==en3)

Resultado:

# encrypt1 time: 0.09787979999999999
# encrypt2 time: 0.16948359999999996
# encrypt3 time: 0.029016399999999998
# All encryptions outputs are same: True

Answer 1

Simplesmente comparando o tempo gasto por um join sem nenhuma operação e o translante/maketrans, você pode ver rapidamente que é impossível ter uma solução que use join e seja mais rápida do que a translante/maketransimplementação (consulte o código no final para implementação).

Encryption join only took: 0.006335399999999991s
Encryption translation function took: 0.004516500000000034s

E sabendo que as strings são imutáveis ​​em Python e a junção é uma das formas mais rápidas (se não a mais rápida) do puro Python de concatenar caracteres, pareceria difícil encontrar uma implementação de Python melhor.

No entanto, conforme mencionado por frank-yellin, uma implementação C pode ser feita para tornar o código executado mais rápido. O código C é executado mais rápido que o python para operações de baixo nível, como neste caso (substituição de caractere em uma string).

Para tentar escrever uma versão C, você pode usar cython, que o tornará muito mais fácil do que escrever todos os clichês de uma extensão sozinho.

Exemplo: Você precisará instalar o cython: pip install cythone compilar o código do cython rodando python setup.py build_ext --inplacena pasta que contém os 3 seguintes arquivos

# file cencrypt.pyx

# distutils: language = c++

from libcpp.string cimport string

cdef char char_A = 'A'

def encrypt(t, key):
    cdef string key_str = key.encode('UTF-8')
    cdef string result = t.encode('UTF-8')

    for i in range(len(result)):
        result[i] = key_str[result[i]-char_A]

    return result.decode('UTF-8')

# file main.py

from random import randrange, seed, sample
from time import perf_counter

from cencrypt import encrypt as encrypt_c

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encrypt_join_only(t, key):
    return ''.join(t)


def encrypt_dict(t, key):
    v = dict(zip(alphabet, key))
    return ''.join(v.get(n) for n in t)


def encrypt_array(t, key):
    ord_a = ord("A")
    return ''.join(key[n - ord_a] for n in map(ord, t))


def encrypt_translation(t, key):
    return t.translate(str.maketrans(alphabet, key))


d = 2000  # number of strings and keys to test
length = 500  # biggest length of strings

strings = [''.join(chr(randrange(26) + 65) for n in range(1, randrange(1, length))) for n in range(d)]
keys = [''.join(chr(n + 65) for n in sample(range(26), 26)) for n in range(d)]


def measure_perf(function, name):
    start = perf_counter()
    result = [function(strings[n], keys[n]) for n in range(d)]
    end = perf_counter()
    print(f'Encryption {name} took: {end - start}s', )
    return result


measure_perf(encrypt_join_only, "join only")
equal = (
    measure_perf(encrypt_dict, "dict lookup") ==
    measure_perf(encrypt_array, "array lookup") ==
    measure_perf(encrypt_translation, "translation function") ==
    measure_perf(encrypt_c, "cython implementation")
)

print("All encryptions outputs are same:", equal)

#file setup.py

from setuptools import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize("cencrypt.pyx")
)

Resultados I7:

Encryption join only took: 0.006335399999999991s
Encryption dict lookup took: 0.044010700000000014s
Encryption array lookup took: 0.0479598s
Encryption translation function took: 0.004516500000000034s
Encryption cython implementation took: 0.002248700000000048s
All encryptions outputs are same: True