Optimización del código de cifrado de sustitución en Python

Question

Aquí está mi código para probar mis tres funciones diferentes que realizan un cifrado de sustitución simple en 2000 cadenas aleatorias de hasta 500 con 2000 claves aleatorias.

La salida muestra que la mejor función es encrypt3entonces encrypt1y la más lenta encrypt2.

¿Cuáles son otros métodos para realizar la sustitución que serían incluso más rápidos que encrypt3?

La sustitución se realiza en letras mayúsculas de la "A" a la "Z", no se permiten otros caracteres y no es necesario comprobar si las cadenas de entrada contienen solo esos caracteres.

Al final del código hay una prueba de si todas las funciones produjeron los mismos resultados.

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)

Salida:

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

Answer 1

Simplemente comparando el tiempo que toma una combinación sin ninguna operación y el translante/maketrans, puede ver rápidamente que es imposible tener una solución que use combinación y sea más rápida que la translante/maketransimplementación (consulte el código al final para la implementación).

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

Y sabiendo que las cadenas son inmutables en Python y que la combinación es una de las formas de Python puro más rápidas (si no la más rápida) de concatenar caracteres, parecería difícil encontrar una mejor implementación de Python.

Sin embargo, como lo menciona frank-yellin, se puede realizar una implementación en C para que el código se ejecute más rápido. El código C se ejecuta más rápido que Python para operaciones de bajo nivel como en este caso (reemplazando un carácter en una cadena).

Para probar a escribir una versión C, puede usar cython, lo que lo hará mucho más fácil que escribir todo el texto estándar de una extensión usted mismo.

Ejemplo: deberá instalar cython: pip install cythony compilar el código cython ejecutando python setup.py build_ext --inplaceen la carpeta que contiene los 3 archivos siguientes

# 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